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

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

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

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

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

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

Είναι πολύ χρήσιμο το γεγονός ότι η τιμή y ≡ aˣ (mod n) μπορεί να υπολογιστεί πολύ αποτελεσματικά, ακόμη και όταν ο αριθμός aˣ είναι πολύ μεγάλος για να υπολογιστεί (βλέπε εκθετοποίηση υπολοίπων για λεπτομέρειες.) Το 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 λειτουργίες για την εκτέλεση πολλαπλασιασμού υπολοίπων στους μη προσημασμένους ακεραίους όχι μεγαλύτερους από 63 bits, χωρίς υπερχείλιση από τις παροδικές πράξεις. Ένας αλγοριθμικό τρόπο για να υπολογίσουμε το a × b (mod m):
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 του προϊόντος, ενώ ο πολλαπλασιασμός ακεραίων οδηγεί στη διατήρηση των λιγότερο σημαντικών bits: Ένας αλγοριθμικός τρόπος για να υπολογίσουμε το a × b (mod m):                                                                                                                                         
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.