Αριθμητική υπολοίπων

Ο χρόνος περνά σε αυτό το ρολόι χρησιμοποιώντας την αριθμητική modulo 12.

Στα μαθηματικά, η αριθμητική υπολοίπων είναι ένα σύστημα αριθμητικής για ακέραιους αριθμούς, όπου οι αριθμοί «αναδιπλώνονται» έως την επίτευξη μιας ορισμένης τιμής — συντελεστή αναδίπλωσης (αναδιπλωτής: modulo πληθυντικός moduli). Η σύγχρονη προσέγγιση για την αριθμητική υπολοίπων αναπτύχθηκε από τον Καρλ Φρίντριχ Γκάους, στο βιβλίο του Disquisitiones Arithmeticae, που δημοσιεύθηκε το 1801.

Μία γνωστή χρήση της αριθμητικής υπολοίπων είναι το ρολόι 12 ωρών, κατά το οποίο η μέρα χωρίζεται σε δύο 12-ωρες περιόδους. Αν τώρα η ώρα είναι 7:00, τότε σε 8 ώρες αργότερα θα είναι 3:00. Επιπλέον, το συνηθισμένο θα ήταν ο μεταγενέστερος χρόνος να πρέπει να είναι 7 + 8 = 15, αλλά αυτό δεν είναι ορθό, διότι η ώρα του ρολογιού «αναδιπλώνεται» κάθε 12 ώρες: σε ένα 12-ωρο, δεν υπάρχει «η ώρα 15:00». Ομοίως, αν το ρολόι ξεκινά στις 12:00 (το μεσημέρι) και έχουν παρέλθει 21 ώρες, τότε ο χρόνος θα είναι 9:00 την επόμενη μέρα, αντί για 33:00. Επειδή η ώρα ξεκινά ξανά από την αρχή αφού φτάσει στις 12:00, αυτό είναι αριθμητική modulo 12. Σύμφωνα με τον ορισμό παρακάτω, το 12 είναι ισότιμο όχι μόνο με το 12, αλλά και με το 0, έτσι ώστε ο χρόνος που ονομάζεται "12:00" θα μπορούσε επίσης να ονομάζεται "0:00", αφού το 12 είναι ισότιμο με το 0 modulo 12.

Σχέση ισοτιμίας

Αυτή η ενότητα είναι για το ( mod n ) συμβολισμό. Για τη δυαδική mod λειτουργία , δείτε τη λειτουργία modulo .

Η αριθμητική υπολοίπων μπορεί να αντιμετωπιστεί στα μαθηματικά με την εισαγωγή μιας σχέσης ισοτιμίας στους ακέραιους αριθμούς που είναι συμβατή με τις πράξεις στους ακέραιους αριθμούς: πρόσθεση, αφαίρεση, καιπολλαπλασιασμό. Για έναν θετικό ακέραιο n, δύο ακέραιοι a και b είναι ισοδύναμοι modulo n και γράφουμε:

$a\equiv b{\pmod {n}},\,$

εάν η διαφορά τους a − b είναι ένα ακέραιο πολλαπλάσιο του n (ή το n διαιρεί το a − b). Ο αριθμός n ονομάζεται συντελεστής της ισοτιμίας.

Για παράδειγμα,

$38\equiv 14{\pmod {12}}\,$

επειδή 38 − 14 = 24, το οποίο είναι πολλαπλάσιο του 12.

Ο ίδιος κανόνας ισχύει και για αρνητικές τιμές:

${\begin{aligned}8&\equiv -7{\pmod {5}}\\2&\equiv -3{\pmod {5}}\\-3&\equiv -8{\pmod {5}}\,\end{aligned}}$

Aντίστοιχα, a ≡ b mod n μπορεί επίσης να εξηγηθεί, επιβεβαιώνοντας ότι τo υπόλοιπο της διαίρεσης των a και b από το n είναι το ίδιο. Για παράδειγμα:

$38\equiv 14{\pmod {12}}\,$

επειδή και το 38 και το 14 έχουν το ίδιο υπόλοιπο, το 2, όταν διαιρούνται από το 12. Επίσης το 38 − 14 = 24 είναι ένα ακέραιο πολλαπλάσιο του 12, το οποίο συμφωνεί με τον προηγούμενο ορισμό της σχέσης ισοτιμίας.

Μια παρατήρηση στο συμβολισμό: Επειδή είναι συνηθισμένο να θεωρούμε διάφορες σχέσεις ισοτιμίας για διαφορετικούς συντελεστές συγχρόνως, ο συντελεστής έχει ενσωματωθεί στο συμβολισμό. Παρά τον τριαδικό συμβολισμό, η σχέση ισοτιμίας για έναν δεδομένο συντελεστή είναι δυαδική. Αυτό θα ήταν σαφέστερο, εάν χρησιμοποιούσαμε τον συμβολισμό a ≡_n b, αντί του συνηθισμένου παραδοσιακού συμβολισμού.

Οι ιδιότητες που καθιστούν αυτή τη σχέση, μια σχέση ισοτιμίας (που σέβεται την πρόσθεση, την αφαίρεση και τον πολλαπλασιασμό) είναι οι ακόλουθες.

Εάν

$a_{1}\equiv b_{1}{\pmod {n}}$

και

$a_{2}\equiv b_{2}{\pmod {n}},$

τότε:

• $a_{1}+a_{2}\equiv b_{1}+b_{2}{\pmod {n}}\,$
• $a_{1}-a_{2}\equiv b_{1}-b_{2}{\pmod {n}}\,$

Οι δύο παραπάνω ιδιότητες θα ίσχυαν ακόμα αν η θεωρία είχε επεκταθεί για να περιλάβει όλους τους πραγματικούς αριθμούς, δηλαδή αν οι $\ a_{1},\ a_{2},\ b_{1},\ b_{2},\ n$ δεν ήταν κατ' ανάγκη όλοι ακέραιοι. Η επόμενη ιδιότητα όμως, δεν θα ίσχυε αν οι μεταβλητές αυτές δεν ήταν όλες ακέραιοι αριθμοί:

• $a_{1}a_{2}\equiv b_{1}b_{2}{\pmod {n}}.\,$

Υπόλοιπα

Η έννοια της αριθμητικής υπολοίπων αφορά το υπόλοιπο στην Ευκλείδεια διαίρεση. Η λειτουργία εύρεσης του υπολοίπου μερικές φορές αναφέρεται ως λειτουργία modulo και συμβολίζεται με το "mod" που χρησιμοποιείται ως ένθετος τελεστής. Για παράδειγμα, το υπόλοιπο της διαίρεσης του 14 από το 12 συμβολίζεται με 14 mod 12, καθώς αυτό το υπόλοιπο είναι 2, έτσι έχουμε 14 mod 12 = 2.

Η ισοτιμία, με την ένδειξη "≡", ακολουθούμενη από το "mod" ανάμεσα στις παρενθέσεις, σημαίνει ότι ο τελεστής "mod", εφαρμοσμένος και στα δύο μέλη, δίνει το ίδιο αποτέλεσμα. Αυτό είναι:

$A\equiv B{\pmod {n}}$

είναι ισοδύναμη με την

$A\!\!\!\!\mod n=B\!\!\!\!\mod n.$

Η θεμελιώδης ιδιότητα του πολλαπλασιασμού στην αριθμητική υπολοίπων μπορεί να γραφεί έτσι:

$(a\!\!\!\!\mod n)\,(b\!\!\!\!\mod n)\equiv ab{\pmod {n}},$

ή ισοδύναμα,

$((a\!\!\!\!\mod n)\,(b\!\!\!\!\mod n))\!\!\!\!\mod n=(ab)\!\!\!\!\mod n.$

Στην επιστήμη των υπολογιστών, είναι το υπόλοιπο του τελεστή, που συνήθως αναφέρεται είτε με το "%" (για παράδειγμα, στις C, C++, Java, JavaScript, Perl, Python και Scala) ή "mod" (για παράδειγμα, σε Pascal, BASIC, SQL, Haskell, ABAP, και MATLAB), με εξαιρέσεις (για παράδειγμα, το Excel). Οι εν λόγω τελεστές συχνά προφέρονται ως "mod", αλλά αυτό συγκεκριμένα είναι ένα υπόλοιπο που υπολογίζεται (αφού στη C++ ένας αρνητικός αριθμός θα επιστραφεί αν το πρώτο επιχείρημα είναι αρνητικό, και στη Python ένας αρνητικός αριθμός θα επιστραφεί αν το δεύτερο επιχείρημα είναι αρνητικό). Η λειτουργία modulo αντί mod, όπως 38 ≡ 14 (modulo 12) μερικές φορές χρησιμοποιείται για να δείξει το κοινό υπόλοιπο και όχι ένα υπόλοιπο (για παράδειγμα, στη Ruby). Για λεπτομέρειες σχετικά με τις ειδικές λειτουργίες που ορίζονται σε διαφορετικές γλώσσες, ανατρέξτε στην λειτουργία modulo της σελίδας.

Συστήματα Υπολοίπων

Κάθε κλάση υπολοίπων modulo n μπορεί να εκπροσωπείται από οποιοδήποτε από τα μέλη της, αν και συνήθως αντιπροσωπεύουμε κάθε κλάση υπολοίπων από τον μικρότερο μη αρνητικό ακέραιο, ο οποίος ανήκει σε αυτήν την κλάση (αφού αυτό είναι το σωστό υπόλοιπο που προκύπτει από τη διαίρεση). Οποιαδήποτε δύο μέλη από διαφορετικές κλάσεις υπολοίπων modulo n είναι ασύμβατα modulo n. Επιπλέον, κάθε ακέραιος ανήκει σε μία και μόνο μία κλάση υπολοίπων modulo n.

Το σύνολο των ακεραίων {0, 1, 2, …, n − 1} λέγεται το ελάχιστο σύστημα υπολοίπων modulo n. Οποιοδήποτε σύνολο n ακεραίων, δύο εκ των οποίων δεν είναι ισότιμοι modulo n, ονομάζεται πλήρης σύστημα υπολοίπων modulo n.

Είναι σαφές ότι το ελάχιστο σύστημα υπολοίπων είναι ένα πλήρες σύστημα υπολοίπων, και ένα πλήρες σύστημα υπολοίπων είναι απλά ένα σύνολο που περιέχει ακριβώς έναν εκπρόσωπο από κάθε κλάση υπολοίπων modulo n. Το ελάχιστο σύστημα υπολοίπων modulo 4 είναι το {0, 1, 2, 3}. Κάποια άλλα πλήρη συστήματα υπολοίπων modulo 4 είναι:

• {1, 2, 3, 4}
• {13, 14, 15, 16}
• {−2, −1, 0, 1}
• {−13, 4, 17, 18}
• {−5, 0, 6, 21}
• {27, 32, 37, 42}

Μερικά σύνολα τα οποία δεν είναι πλήρη συστήματα υπολοίπων modulo 4 είναι:

• {-5, 0, 6, 22} αφού το 6 είναι ισότιμο με το 22 modulo 4.
• {5, 15} αφού ένα πλήρες σύστημα υπολοίπων modulo 4 πρέπει να έχει ακριβώς 4 ασύμβατες κλάσεις υπολοίπων.

Μειωμένα συστήματα υπολοίπων

Κύριο άρθρο: Reduced residue system

Κάθε σύνολο φ(n) ακεραίων αριθμών, που είναι σχετικά πρώτοι στο n και οι οποίοι είναι αμοιβαία ασύμβατοι modulo n, όπου φ(n) δηλώνει τη Συνάρτηση Όιλερ, ονομάζεται μειωμένο σύστημα υπoλοίπων modulo n. Το παραπάνω παράδειγμα, {5,15} είναι ένα παράδειγμα ενός μειωμένου συστήματος υπολοίπων modulo 4.

Κλάσεις ισοτιμίας

Όπως κάθε σχέση ισοτιμίας, η ισοτιμία modulo n είναι μία σχέση ισοδυναμίας, και η κλάση ισοδυναμίας του ακέραιου a, που συμβολίζεται με ${\bar {a_{n}}}$ είναι το σύνολο {… a − 2n, a − n, a, a + n, a + 2n, …}. Αυτό το σετ, που αποτελείται από τους ακεραίους που είναι ισότιμοι με το a modulo n, ονομάζεται κλάση ισοτιμίας ή κλάση υπολοίπων ή απλά υπόλοιπο του ακέραιου a modulo n. Όταν ο συντελεστής n είναι γνωστός από το περιεχόμενο, το υπόλοιπο μπορεί επίσης να συμβολίζεται [a].

Ακέραιοι modulo n

Το σύνολο όλων των κλάσεων ισοτιμίας των ακεραίων για ένα συντελεστή n ονομάζεται το σύνολο των ακεραίων modulo n, και συμβολίζεται $\mathbb {Z} /n\mathbb {Z}$, $\mathbb {Z} /n$ ή $\mathbb {Z} _{n}$. Ο συμβολισμός $\mathbb {Z} _{n}$, ωστόσο, δεν συνιστάται επειδή μπορεί να συγχέεται με το σύνολο των [[n-adic ακεραίων]]. Το σύνολο ορίζεται ως εξής.

$\mathbb {Z} /n\mathbb {Z} =\left\{{\overline {a}}_{n}|a\in \mathbb {Z} \right\}.$

Όταν n ≠ 0, $\mathbb {Z} /n\mathbb {Z}$ έχει n στοιχεία και μπορεί να γραφεί ως:

$\mathbb {Z} /n\mathbb {Z} =\left\{{\overline {0}}_{n},{\overline {1}}_{n},{\overline {2}}_{n},\ldots ,{\overline {n-1}}_{n}\right\}.$

Όταν n = 0, $\mathbb {Z} /n\mathbb {Z}$ δεν έχει μηδενικά στοιχεία: μάλλον, είναι ισομορφικό στο $\mathbb {Z}$, όταν ${\bar {a_{0}}}=\{a\}$.

Μπορούμε να ορίσουμε πρόσθεση, αφαίρεση και πολλαπλασιασμό στο σύνολο $\mathbb {Z} /n\mathbb {Z}$ με τους ακόλουθους κανόνες:

• ${\overline {a}}_{n}+{\overline {b}}_{n}={\overline {(a+b)}}_{n}$
• ${\overline {a}}_{n}-{\overline {b}}_{n}={\overline {(a-b)}}_{n}$
• ${\overline {a}}_{n}{\overline {b}}_{n}={\overline {(ab)}}_{n}.$

Η επαλήθευση ότι αυτός είναι ένας σωστός ορισμός χρησιμοποιεί τις ιδιότητες που δόθηκαν πριν.

Με τον τρόπο αυτό, $\mathbb {Z} /n\mathbb {Z}$ γίνεται ένας αντιμεταθετικός δαχτύλιος. Για παράδειγμα, στο δακτύλιο $\mathbb {Z} /24\mathbb {Z}$, έχουμε

${\overline {12}}_{24}+{\overline {21}}_{24}={\overline {9}}_{24}$

όπως και στην αριθμητική για το 24-ωρο ρολόι.

Ο συμβολισμός $\mathbb {Z} /n\mathbb {Z}$ χρησιμοποιείται, επειδή είναι ο δαχτύλιος πηλίκο του $\mathbb {Z}$ από το ιδεώδες $n\mathbb {Z}$ που περιέχει όλους τους ακεραίους που διαιρούνται με το n, όπου $0\mathbb {Z}$ είναι το μονοσύνολο {0}. Έτσι, το $\mathbb {Z} /n\mathbb {Z}$ είναι ένα σώμα όταν $n\mathbb {Z}$ είναι ένα μεγιστοτικό ιδεώδες, αυτό συμβαίνει, όταν το n είναι πρώτος.

Όσον αφορά τις ομάδες, η κλάση υπολοίπων ${\bar {a_{n}}}$ είναι το σύμπλοκο της a στην ομάδα πηλίκου $\mathbb {Z} /n\mathbb {Z}$, μια κυκλική ομάδα..

Το σύνολο $\mathbb {Z} /n\mathbb {Z}$ έχει μια σειρά από σημαντικές μαθηματικές ιδιότητες που είναι θεμελιώδεις για τους διάφορους κλάδους των μαθηματικών.

Αντί να εξαιρείται η ειδική περίπτωση για n = 0, είναι πιο χρήσιμο να περιλαμβάνει το $\mathbb {Z} /0\mathbb {Z}$ (το οποίο, όπως προαναφέρθηκε, είναι ισομορφικό με το δακτύλιο $\mathbb {Z}$ των ακεραίων), για παράδειγμα, όταν συζητάμε για το χαρακτηριστικό ενός δακτυλίου.

Ο δακτύλιος των ακεραίων modulo n είναι ένα πεπερασμένο σώμα , αν και μόνο αν ο n είναι πρώτος αριθμός. Αν ο n δεν είναι ένας πρώτος με πρωταρχική δύναμη, υπάρχει ένα μοναδικό (μέχρι ισομορφισμό) πεπερασμένο σώμα GF(n) με n στοιχεία, τα οποία δεν πρέπει να συγχέονται με τον δακτύλιο των ακεραίων modulo n, αν και έχουν τον ίδιο αριθμό στοιχείων.

Εκθετοποίηση υπολοίπων

Είναι πολύ χρήσιμο το γεγονός ότι η τιμή y ≡ a^x (mod n) μπορεί να υπολογιστεί πολύ αποτελεσματικά, ακόμη και όταν ο αριθμός a^x είναι πολύ μεγάλος για να υπολογιστεί (βλέπε εκθετοποίηση υπολοίπων για λεπτομέρειες.) Το y μπορεί να υπολογιστεί χωρίς κάθε φορά να ασχολούμαστε με νούμερα μεγαλύτερα από το n².

Εφαρμογές

Η αριθμητική υπολοίπων αναφέρεται στη θεωρία αριθμών, θεωρία ομάδων, θεωρία δακτυλίων, θεωρία κόμβων, αφηρημένη άλγεβρα, άλγεβρα υπολογιστών, την κρυπτογραφία, την πληροφορική, τη χημεία και τις εικαστικές και μουσικές τέχνες.

Είναι ένα από τα θεμέλια της θεωρίας αριθμών, που αγγίζει σχεδόν κάθε πτυχή της μελέτης, και παρέχει βασικά παραδείγματα για τη θεωρία ομάδων, τη θεωρία δακτυλίων και την αφηρημένη άλγεβρα.

Η αριθμητική υπολοίπων συχνά χρησιμοποιείται για να υπολογίσει τα αθροίσματα ελέγχου που χρησιμοποιούνται μέσα σε αναγνωριστικά. Διεθνείς Αριθμοί Τραπεζικών λογαριασμών (IBANs), για παράδειγμα, κάνουν χρήση του modulo 97 για να εμποδίσουν λάθη του χρήστη κατά την είσοδο σε αριθμούς τραπεζικών λογαριασμών.

Στην κρυπτογραφία, η αριθμητική υπολοίπων άμεσα στηρίζει τα συστήματα δημοσίων κλειδιών όπως το RSA και Diffie–Hellman και παρέχει πεπερασμένα πεδία που αποτελούν το θεμέλιο των ελλιπτικών καμπυλών, και χρησιμοποιείται σε μια ποικιλία αλγορίθμων συμμετρικών κλειδιών συμπεριλαμβανομένης της Advanced Encryption Standard (AES), International Data Encryption Algorithm (IDEA), και RC4. RSA και Diffie–Hellman χρησιμοποιούν modular ύψωση σε δύναμη.

Στην άλγεβρα υπολογιστών, η αριθμητική υπολοίπων συνήθως χρησιμοποιείται για να περιορίζει το μέγεθος των ακέραιων συντελεστών σε ενδιάμεσους υπολογισμούς και δεδομένα. Χρησιμοποιείται στην παραγοντοποίηση πολυωνύμου, ένα πρόβλημα για το οποίο όλοι οι γνωστοί αποδοτικοί αλγόριθμοι χρησιμοποιούν αριθμητική υπολοίπων. Χρησιμοποιείται από τις πιο αποδοτικές υλοποιήσεις του μέγιστου κοινού διαιρέτη πολυωνύμου , ακριβή γραμμική άλγεβρα και Gröbner βάση αλγορίθμους πάνω στους ακέραιους και στους ρητούς αριθμούς.

Στην επιστήμη των υπολογιστών, η αριθμητική υπολοίπων συχνά εφαρμόζεται σε bitwise πράξεις και άλλες πράξεις που αφορούν σταθερού πλάτους, κυκλικές δομές δεδομένων. Η λειτουργία modulo, όπως εφαρμόζεται σε πολλές γλώσσες προγραμματισμού και αριθμομηχανές, είναι μια εφαρμογή της αριθμητικής υπολοίπων που χρησιμοποιείται συχνά σε αυτό το πλαίσιο. XOR είναι το άθροισμα των 2 bits, modulo 2.

Στη χημεία, το τελευταίο ψηφίο του CAS αριθμού μητρώου (ένας αριθμός ο οποίος είναι μοναδικός για κάθε χημική ένωση) είναι ένα ψηφίο ελέγχου, το οποίο υπολογίζεται επιλέγοντας το τελευταίο ψηφίο από τα δύο πρώτα μέρη του CAS αριθμού μητρώου 1 φορά, το προηγούμενο ψηφίο 2 φορές, το προηγούμενο ψηφίο 3 φορές κ.λ.π., προσθέτοντας σε όλα αυτά και τον υπολογισμό του ποσού modulo 10.

Στη μουσική, το modulo 12 χρησιμοποιείται στην εξέταση του συστήματος του δωδεκάτονου ίσου τέμπου, όπου προκύπτει η οκτάβα και η εναρμόνια ισοδυναμία (δηλαδή, τόνος σε 1∶2 ή 2∶1 αναλογία είναι ισοδύναμα, και η C-Δίεση θεωρείται η ίδια ως D-ύφεση).

Η μέθοδος casting out nines προσφέρει ένα γρήγορο έλεγχο των δεκαδικών αριθμητικών υπολογισμών που εκτελούνται με το χέρι. Βασίζεται στην αριθμητική υπολοίπων modulo 9, και συγκεκριμένα στην κρίσιμη ιδιότητα όπου 10 ≡ 1 (mod 9).

Το modulo 7 χρησιμοποιείται σε αλγορίθμους που προσδιορίζουν την ημέρα της εβδομάδας για μια συγκεκριμένη ημερομηνία. Ειδικότερα, η συνεκτικότητα Zeller και ο αλγόριθμος της ημέρας της κρίσεως κάνουν μεγάλη χρήση του modulo-7.

Γενικότερα, η αριθμητική υπολοίπων, επίσης, έχει εφαρμογή σε κλάδους όπως το δίκαιο (βλέπε, για παράδειγμα, κατανομή), τα οικονομικά, (βλέπε, για παράδειγμα, τη θεωρία παιγνίων) και σε άλλους τομείς των κοινωνικών επιστημών, όπου η αναλογική κατανομή και η κατανομή των πόρων αποτελεί κεντρικό μέρος της ανάλυσης.

Υπολογιστική πολυπλοκότητα

Από τη στιγμή που η αριθμητική υπολοίπων έχει ένα τέτοιο ευρύ φάσμα εφαρμογών, είναι σημαντικό να γνωρίζουμε πόσο δύσκολο είναι να λύσουμε ένα σύστημα ισοτιμίας. Ένα γραμμικό σύστημα ισοτιμίας μπορεί να λυθεί σε πολυωνυμικό χρόνο με μια μορφή απαλοιφής Gauss, για περισσότερες λεπτομέρειες βλέπε θεώρημα γραμμικής ισοτιμίας . Αλγόριθμοι, όπως η αναγωγή Μοντγκόμερι , υπάρχουν, επίσης, για να επιτρέπουν απλές αριθμητικές πράξεις, όπως ο πολλαπλασιασμός και η εκθετοποίηση ή ύψωση σε δύναμη modulo n, να εκτελούνται αποτελεσματικά σε μεγάλους αριθμούς.

Ορισμένες λειτουργίες, όπως η εύρεση ενός διακριτού λογαρίθμου ή οι δευτεροβάθμιες ισοτιμίες φαίνεται να είναι τόσο δύσκολες όσο η παραγοντοποίηση ακεραίων και, επομένως, το σημείο εκκίνησης είναι η Κρυπτογραφία αλγορίθμων και η Κρυπτογράφηση. Αυτά τα προβλήματα είναι NP-ενδιάμεσα.

Η επίλυση του συστήματος των μη-γραμμικών εξισώσεων αριθμητικής υπολοίπων είναι NP-πλήρης.

Παράδειγμα υλοποίησης

Οι περισσότερες γλώσσες προγραμματισμού υποστηρίζουν τον υπολογισμό υπολοίπων. Για παράδειγμα, στην C/C++/Java έχουν την πράξη %, που επιτρέπει να γράψουμε

int a = 53;
int b = 23;
int m = 100;
int res = (a * b) % m; // res=19.

Ένα πιθανό πρόβλημα με αυτή την υλοποίηση είναι ότι ο τύπος int, κρατάει αριθμούς με περιορισμένο πλήθος δυαδικών ψηφίων (συνήθως 16 ή 32). Αυτό σημαίνει ότι αν ο a και ο b είναι αρκετά μεγάλοι, τότε το γινόμενο τους μπορεί να υπερχειλίσει, παρόλο που το αποτέλεσμα χωράει σε int (πχ όταν $a=2^{31}-1$).

Παρακάτω δίνονται δύο αρκετά γρήγορες υλοποιήσεις C για την εκτέλεση πολλαπλασιασμού υπολοίπων στους μη προσημασμένους ακεραίους όχι μεγαλύτερους από 63 bits, αποφεύγοντας κάποια πιθανή υπερχείλιση στις ενδιάμεσες πράξεις. Ο πρώτος είναι ο εξής:

uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m) {
   uint64_t d = 0, mp2 = m >> 1;
   int i;
   if (a >= m) a %= m;
   if (b >= m) b %= m;
   for (i = 0; i < 64; ++i) {
      d = (d > mp2) ? (d << 1) - m : d << 1;
      if (a & 0x8000000000000000ULL) d += b;
      if (d > m) d -= m;
      a <<= 1;
   }
   return d;
}

Στις αρχιτεκτονικές των υπολογιστών, όπου μια εκτεταμένης ακριβείας μορφή, με τουλάχιστον 64 bits mantissa, είναι διαθέσιμη (όπως ο long double τύπος των περισσοτέρων x86 C compilers), η παρακάτω συνάρτηση μπορεί να χρησιμοποιηθεί. Κάνει χρήση του πολλαπλασιασμού κινητής υποδιαστολής και ότι το αποτέλεσμα διατηρεί τα πιο σημαντικά bits του γινομένου, τα οποία θα χανόντουσαν αν χρησιμοποιούσαμε τον αντίστοιχο πολλαπλασιασμό ακεραίων (λόγω της υπερχείλισης).

uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m) {
   long double x;
   uint64_t c;
   int64_t r;
   if (b >= m) b %= m;
   x = a;
   c = x * b / m;
   r = (int64_t)(a * b - c * m) % (int64_t)m;
   return r < 0 ? r + m : r;
}

Ωστόσο, και για τις δύο ρουτίνες για να λειτουργήσουν, το m δεν πρέπει να υπερβαίνει τα 63 bits.

Δείτε επίσης

• Boolean ring
• Circular buffer
• Congruence relation
• Διαίρεση
• Πεπερασμένο σώμα
• Legendre symbol
• Modular exponentiation
• Modular multiplicative inverse
• Modulo operation
• Θεωρία αριθμών
• Pisano period (Fibonacci sequences modulo n)
• Primitive root modulo n
• Quadratic reciprocity
• Quadratic residue
• Rational reconstruction (mathematics)
• Reduced residue system
• Serial number arithmetic (a special case of modular arithmetic)
• Two-element Boolean algebra
• Topics relating to the group theory behind modular arithmetic:
  • Cyclic group
  • Multiplicative group of integers modulo n
• Other important theorems relating to modular arithmetic:
  • Carmichael's theorem
  • Κινεζικό Θεώρημα Υπολοίπων
  • Θεώρημα του Όιλερ
  • Μικρό θεώρημα του Φερμά
  • Lagrange's theorem
  • Thue's lemma

Πηγές

• Encyclopædia Britannica. Modular Arithmetic.
• Πρότυπο:Apostol IANT. See in particular chapters 5 and 6 for a review of basic modular arithmetic.
• Maarten Bullynck "Modular Arithmetic before C.F. Gauss. Systematisations and discussions on remainder problems in 18th-century Germany"
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001.ISBN 0-262-03293-7. Section 31.3: Modular arithmetic, pp. 862–868.
• Anthony Gioia, Number Theory, an IntroductionReprint (2001) Dover. ISBN 0-486-41449-3
• Long, Calvin T. (1972), Elementary Introduction to Number Theory (2nd ed.Long, Calvin T. (1972), Elementary Introduction to Number Theory (2nd έκδοση), Lexington: D. C. Heath and Company 
• Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elements of Number Theory, Englewood Cliffs: Prentice Hall 
• Sengadir, T. (2009). Sengadir, T. (2009). Discrete Mathematics and Combinatorics. Chennai, India: Pearson Education India. ISBN 978-81-317-1405-8. OCLC 778356123. OCLC 778356123.

Εξωτερικοί σύνδεσμοι

• Hazewinkel, Michiel, επιμ.. (2001), «Congruence», Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4, http://www.encyclopediaofmath.org/index.php?title=p/c024850 
• In this modular art article, one can learn more about applications of modular arithmetic in art.
• Weisstein, Eric W., "Modular Arithmetic", MathWorld.
• An article on modular arithmetic on the GIMPS wiki
• Modular Arithmetic and patterns in addition and multiplication tables
• Whitney Music Box—an audio/video demonstration of integer modular math

Αυτοματοποιημένη αριθμητική υπολοίπων θεώρημα provers

• Spear
• AAProver - Simple C++ - πλαίσιο εύκολο στη χρήση σε εφαρμογές, υποστηρίζοντας, μεταξύ άλλων, όλους τους ακέραιους φορείς που είναι παρόντες σε γλώσσες όπως οι C/C++/Java και αυθαίρετου πλάτους bit.