Χρήστης:Elisabeth521/Πρόχειρο

Σχέση Ισοτιμίας[Επεξεργασία | επεξεργασία κώδικα]

Η αριθμητική υπολοίπων μπορεί να αντιμετωπιστεί στα μαθηματικά με την εισαγωγή μιας σχέσης ισοτιμίας στους ακέραιους αριθμούς που είναι συμβατή με τις πράξεις στους ακέραιους αριθμούς: πρόσθεση, αφαίρεση, και πολλαπλασιασμό. Για έναν θετικό ακέραιο 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 \equiv b mod n$ μπορεί επίσης να εξηγηθεί, επιβεβαιώνοντας ότι τo υπόλοιπο της διαίρεσης και των δύο $a$ και $b$ από το $n$ είναι το ίδιο. Για παράδειγμα:

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

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

Μια παρατήρηση για το συμβολισμό: Επειδή είναι συνηθισμένο να θεωρούμε διάφορες σχέσεις ισοτιμίας για τους διαφορετικούς συντελεστές συγχρόνως, ο συντελεστής έχει ενσωματωθεί στο συμβολισμό. Παρά την τριαδική σημείωση, η σχέση ισοτιμίας για έναν δεδομένο συντελεστή είναι δυαδική. Αυτό θα ήταν σαφέστερο, εάν χρησιμοποιούσαμε τον συμβολισμό $a \equiv 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 $n$ μπορεί να εκπροσωπείται από ένα από τα μέλη της, αν και συνήθως αντιπροσωπεύουμε κάθε κλάση υπολοίπων από τον μικρότερο μη αρνητικό ακέραιο, ο οποίος ανήκει σε αυτήν την κλάση (αφού αυτό είναι το σωστό υπόλοιπο που προκύπτει από τη διαίρεση). Οποιαδήποτε δύο μέλη των διαφόρων κλάσεων υπολοίπων modulo $n$ είναι ασύμβατα modulo $n$ . Επιπλέον, κάθε ακέραιος ανήκει σε μία και μόνο μία κλάση υπολοίπων modulo $n$ .^[1]

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

Είναι σαφές ότι το ελάχιστο σύστημα υπολοίπων είναι ένα πλήρες σύστημα υπολοίπων, και ένα πλήρες σύστημα υπολοίπων είναι απλά ένα σύνολο που περιέχει ακριβώς έναν εκπρόσωπο από κάθε κλάση υπολοίπων modulo $n$ .^[2] Το ελάχιστο σύστημα υπολοίπων 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 ασύμβατες κλάσεις υπολοίπων.

Κλάσεις ισοτιμίας[Επεξεργασία | επεξεργασία κώδικα]

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

Εφαρμογές[Επεξεργασία | επεξεργασία κώδικα]

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

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

Η αριθμητική υπολοίπων συχνά χρησιμοποιείται για να υπολογίσει τα αθροίσματα ελέγχου που χρησιμοποιούνται μέσα σε αναγνωριστικά. Διεθνείς Αριθμοί Τραπεζικών λογαριασμών (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.

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

Παράδειγμα υλοποίησης[Επεξεργασία | επεξεργασία κώδικα]

Παρακάτω είναι δύο αρκετά γρήγορες C λειτουργίες για την εκτέλεση πολλαπλασιασμού υπολοίπων στους ανυπόγραφους ακεραίους όχι μεγαλύτερους από 63 bits, χωρίς υπερχείλιση από τις παροδικές πράξεις. Ένα αλγοριθμικό τρόπο για να υπολογίσουμε $a \times 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 \times 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.

Δείτε επίσης[Επεξεργασία | επεξεργασία κώδικα]

Σημειώσεις[Επεξεργασία | επεξεργασία κώδικα]

Αναφορές[Επεξεργασία | επεξεργασία κώδικα]

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.

[[Κατηγορία:Θεωρία ομάδων]]

[1] «Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elements of Number Theory, Englewood Cliffs: Prentice Hall, LCCN 71081766».

[2] «Long (1972, p. 78)».

[1]

[2]