Προβολή πηγαίου κώδικα για τη σελίδα Μοδιακή αριθμητική

{{επιμέλεια|περιέχει συνδέσμους προς την αγγλική βικιπαίδεια}}[[Αρχείο:Clock_group.svg|μικρογραφία|250x250εσ|Ο χρόνος περνά σε αυτό το ρολόι χρησιμοποιώντας την αριθμητική modulo 12.]]
Στα [[μαθηματικά]],  η '''Μοδιακή αριθμητική'''<ref>{{Cite book|title=Αγγλοελληνικόν Λεξικόν των Θεωρητικών και Εφηρμοσμένων Μαθηματικών|first=Μ.|last=Κολαΐτης|publisher=ΤΕΕ|date=1976|url=https://www.itia.ntua.gr/en/docinfo/1318/}}</ref> ή '''με μέτρο'''<ref>{{Cite web|url=https://www.mas.ucy.ac.cy/georgios/bookfiles/dict1.pdf|title=Αγγλοελληνικό Λεξικό Μαθηματικής Ορολογίας - Πανεπιστήμιο Κύπρου}}</ref> είναι ένα σύστημα [[αριθμητική]]ς για [[Ακέραιος αριθμός|ακέραιους αριθμούς]], όπου οι αριθμοί «αναδιπλώνονται» έως την επίτευξη μιας ορισμένης τιμής. Η σύγχρονη προσέγγιση για την αριθμητική υπολοίπων αναπτύχθηκε από τον [[Καρλ Φρίντριχ Γκάους]], στο βιβλίο του ''[[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]] .''

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

:<math>a \equiv b \pmod n,\,</math>

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

Για παράδειγμα,
:<math>38 \equiv 14 \pmod {12}\,</math>

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

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

:<math> \begin{align}
8 &\equiv -7 \pmod 5\\
2 &\equiv -3 \pmod 5\\
 -3 &\equiv -8 \pmod 5\,
\end{align}</math>

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

:<math>38 \equiv 14 \pmod {12}\,</math>

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

Μια παρατήρηση στο συμβολισμό: Επειδή είναι συνηθισμένο να θεωρούμε διάφορες σχέσεις ισοτιμίας για διαφορετικούς συντελεστές συγχρόνως, ο συντελεστής έχει ενσωματωθεί στο συμβολισμό. Παρά τον τριαδικό συμβολισμό, η σχέση ισοτιμίας για έναν δεδομένο συντελεστή είναι  δυαδική.  Αυτό θα ήταν σαφέστερο, εάν χρησιμοποιούσαμε τον συμβολισμό {{math|''a'' ≡<sub>''n''</sub> ''b''}}, αντί του συνηθισμένου παραδοσιακού συμβολισμού.

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

Εάν

:<math>a_1 \equiv b_1 \pmod n</math>

και

:<math>a_2 \equiv b_2 \pmod n,</math>

τότε:

* <math>a_1 + a_2 \equiv b_1 + b_2 \pmod n\,</math>
* <math>a_1 - a_2 \equiv b_1 - b_2 \pmod n\,</math>

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

* <math> a_1 a_2 \equiv b_1 b_2 \pmod n.\,</math>

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

Η ισοτιμία, με την ένδειξη "{{math|≡}}", ακολουθούμενη από το "{{math|mod}}" ανάμεσα στις παρενθέσεις, σημαίνει ότι ο τελεστής "{{math|mod}}", εφαρμοσμένος και στα δύο μέλη, δίνει το ίδιο αποτέλεσμα. Αυτό είναι:
: <math>A\equiv B \pmod n</math>
είναι ισοδύναμη με την 
:<math>A\!\!\!\!\mod n = B \!\!\!\!\mod n.</math>

Η θεμελιώδης ιδιότητα του πολλαπλασιασμού στην αριθμητική υπολοίπων μπορεί να γραφεί έτσι:
:<math>(a \!\!\!\!\mod n)\,(b\!\!\!\!\mod n) \equiv ab \pmod n,</math>
ή ισοδύναμα,
:<math>((a \!\!\!\!\mod n)\,(b\!\!\!\!\mod n)) \!\!\!\!\mod n =  (ab) \!\!\!\!\mod n.</math>

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

== Συστήματα Υπολοίπων ==
Κάθε κλάση υπολοίπων modulo {{math|''n''}} μπορεί να εκπροσωπείται από οποιοδήποτε από τα μέλη της, αν και συνήθως αντιπροσωπεύουμε κάθε κλάση υπολοίπων από τον μικρότερο μη αρνητικό ακέραιο, ο οποίος ανήκει σε αυτήν την κλάση (αφού αυτό είναι το σωστό υπόλοιπο που προκύπτει από τη διαίρεση). Οποιαδήποτε δύο μέλη από διαφορετικές κλάσεις υπολοίπων modulo {{math|''n''}} είναι ασύμβατα modulo {{math|''n''}}. Επιπλέον, κάθε ακέραιος ανήκει σε μία και μόνο μία κλάση υπολοίπων modulo {{math|''n''}}.<ref>{{harvtxt|Pettofrezzo|Byrkit|1970|p=90}}</ref>

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

Είναι σαφές ότι το ελάχιστο σύστημα υπολοίπων είναι ένα πλήρες σύστημα υπολοίπων, και ένα πλήρες σύστημα υπολοίπων είναι απλά ένα σύνολο που περιέχει ακριβώς έναν εκπρόσωπο από κάθε κλάση υπολοίπων modulo {{math|''n''}}.<ref>{{harvtxt|Long|1972|p=78}}</ref> Το ελάχιστο σύστημα υπολοίπων 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) ακεραίων αριθμών, που είναι σχετικά πρώτοι στο {{math|''n''}} και οι οποίοι είναι αμοιβαία ασύμβατοι modulo {{math|''n''}}, όπου {{math|φ(''n'')}} δηλώνει τη [[Συνάρτηση Όιλερ]], ονομάζεται '''μειωμένο σύστημα υπoλοίπων modulo {{math|''n''}}'''<ref>{{harvtxt|Long|1972|p=85}}</ref>. Το παραπάνω παράδειγμα, {5,15} είναι ένα παράδειγμα ενός μειωμένου συστήματος υπολοίπων modulo 4.

== Κλάσεις ισοτιμίας ==
Όπως κάθε σχέση ισοτιμίας, η ισοτιμία modulo {{math|''n''}} είναι μία [[σχέση ισοδυναμίας]], και η [[κλάση ισοδυναμίας]] του ακέραιου {{math|''a''}}, που συμβολίζεται με <math>\bar{a_n}</math> είναι το σύνολο {{math|&#123;… ''a'' − 2''n'', ''a'' − ''n'', ''a'', ''a'' + ''n'', ''a'' + 2''n'', …&#125;}}. Αυτό το σετ, που αποτελείται από τους ακεραίους που είναι ισότιμοι με το {{math|''a''}}&nbsp;modulo&nbsp;{{math|''n''}}, ονομάζεται '''κλάση ισοτιμίας''' ή '''κλάση υπολοίπων''' ή απλά '''υπόλοιπο''' του ακέραιου {{math|''a''}}&nbsp;modulo&nbsp;{{math|''n''}}. Όταν ο συντελεστής {{math|''n''}} είναι γνωστός από το περιεχόμενο, '''το υπόλοιπο''' μπορεί επίσης να συμβολίζεται {{math|[''a'']}}.

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

:<math>\mathbb{Z}/n\mathbb{Z} = \left\{ \overline{a}_n | a \in \mathbb{Z}\right\}. </math>

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

:<math>\mathbb{Z}/n\mathbb{Z} = \left\{ \overline{0}_n, \overline{1}_n, \overline{2}_n,\ldots, \overline{n-1}_n \right\}.</math>

Όταν {{math|''n'' {{=}} 0}}, <math>\mathbb{Z}/n\mathbb{Z}</math> δεν έχει μηδενικά στοιχεία: μάλλον, είναι [[Ισομορφισμός|ισομορφικό]] στο <math>\mathbb{Z}</math>, όταν <math> \bar{a_0} = \{a\}</math>.

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

* <math>\overline{a}_n + \overline{b}_n = \overline{(a + b)}_n</math>
* <math>\overline{a}_n - \overline{b}_n = \overline{(a - b)}_n</math>
* <math>\overline{a}_n \overline{b}_n = \overline{(ab)}_n.</math>

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

Με τον τρόπο αυτό, <math>\mathbb{Z}/n\mathbb{Z}</math> γίνεται ένας [[Αντιμεταθετικός δακτύλιος|αντιμεταθετικός δαχτύλιος]]. Για παράδειγμα, στο δακτύλιο <math>\mathbb{Z}/24\mathbb{Z}</math>, έχουμε
:<math>\overline{12}_{24} + \overline{21}_{24} = \overline{9}_{24}</math>
όπως και στην αριθμητική για το 24-ωρο ρολόι.

Ο συμβολισμός <math>\mathbb{Z}/n\mathbb{Z}</math> χρησιμοποιείται, επειδή είναι ο [[δαχτύλιος πηλίκο]] του <math>\mathbb{Z}</math> από το [[Ιδεώδες (μαθηματικά)|ιδεώδες]] <math>n\mathbb{Z}</math> που περιέχει όλους τους ακεραίους που διαιρούνται με το {{math|''n''}}, όπου <math>0\mathbb{Z}</math> είναι το [[μονοσύνολο]] {{math|&#123;0&#125;}}. Έτσι, το <math>\mathbb{Z}/n\mathbb{Z}</math> είναι ένα [[Σώμα (άλγεβρα)|σώμα]] όταν <math>n\mathbb{Z}</math> είναι ένα [[μεγιστοτικό ιδεώδες]], αυτό συμβαίνει, όταν το {{math|''n''}} είναι πρώτος.

Όσον αφορά τις ομάδες, η κλάση  υπολοίπων <math>\bar{a_n}</math> είναι το [[σύμπλοκο]] της {{math|''a''}} στην [[ομάδα πηλίκου]] <math>\mathbb{Z}/n\mathbb{Z}</math>, μια [[:en:Cyclic group|κυκλική ομάδα]].<ref>Sengadir T., {{Google books|id=nglisrt9IewC|page=293|text=Zn is generated by 1|title=Discrete Mathematics and Combinatorics}}</ref>.

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

Αντί να εξαιρείται η ειδική περίπτωση για {{math|''n'' {{=}} 0}}, είναι πιο χρήσιμο να περιλαμβάνει το <math>\mathbb{Z}/0\mathbb{Z}</math> (το οποίο, όπως προαναφέρθηκε, είναι ισομορφικό με το δακτύλιο <math>\mathbb{Z}</math> των ακεραίων), για παράδειγμα, όταν συζητάμε για το [[:en:Characteristic (algebra)|χαρακτηριστικό]] ενός [[Δακτύλιος (άλγεβρα)|δακτυλίου]].

Ο δακτύλιος των ακεραίων modulo {{math|''n''}} είναι ένα [[πεπερασμένο σώμα]] , αν και μόνο αν ο {{math|''n''}} είναι [[πρώτος αριθμός]]. Αν ο {{math|''n''}} δεν είναι ένας πρώτος με [[:en:Prime power|πρωταρχική δύναμη]], υπάρχει ένα μοναδικό (μέχρι ισομορφισμό) πεπερασμένο σώμα {{math|GF(''n'')}} με {{math|''n''}} στοιχεία, τα οποία δεν πρέπει να συγχέονται με τον δακτύλιο των ακεραίων modulo {{math|''n''}}, αν και έχουν τον ίδιο αριθμό στοιχείων.

== Εκθετοποίηση υπολοίπων ==
Είναι πολύ χρήσιμο το γεγονός ότι η τιμή {{math|''y'' ≡ ''a''<sup>''x''</sup> (mod ''n'')}} μπορεί να υπολογιστεί πολύ αποτελεσματικά, ακόμη και όταν ο αριθμός {{math|''a''<sup>''x''</sup>}} είναι πολύ μεγάλος για να υπολογιστεί (βλέπε [[:en:Modular exponentiation|εκθετοποίηση υπολοίπων]] για λεπτομέρειες.) Το {{math|''y''}} μπορεί να υπολογιστεί χωρίς κάθε φορά να ασχολούμαστε με νούμερα μεγαλύτερα από το {{math|''n''<sup>2</sup>}}.

== Εφαρμογές ==
Η αριθμητική υπολοίπων αναφέρεται στη [[θεωρία αριθμών]], [[θεωρία ομάδων]], [[θεωρία δακτυλίων]], [[θεωρία κόμβων]], [[:en:Abstract algebra|αφηρημένη άλγεβρα]], [[:en:Computer algebra|άλγεβρα υπολογιστών]], [[Κρυπτογραφία|την κρυπτογραφία]], την [[πληροφορική]], [[Χημεία|τη χημεία]] και τις [[:en:Visual arts|εικαστικές]] και [[Μουσική|μουσικές]] τέχνες.

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

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

Στην κρυπτογραφία, η αριθμητική υπολοίπων άμεσα στηρίζει τα συστήματα [[Κρυπτογράφηση Δημόσιου Κλειδιού|δημοσίων κλειδιών]] όπως το [[RSA]] και [[Πρωτόκολλο Diffie-Hellman|Diffie–Hellman]] και παρέχει [[Πεπερασμένο σώμα|πεπερασμένα πεδία]] που αποτελούν το θεμέλιο των [[:en:Elliptic curve|ελλιπτικών καμπυλών]], και χρησιμοποιείται σε μια ποικιλία [[Κρυπτογράφηση Συμμετρικού Κλειδιού|αλγορίθμων συμμετρικών κλειδιών]] συμπεριλαμβανομένης ''του [[Προηγμένο πρότυπο κρυπτογράφησης|Προηγμένου Πρότυπου Κρυπτογράφησης]]'' [[:en:Advanced Encryption Standard|en]] (AES), ''του [[Διεθνής Αλγόριθμος Κρυπτογράφησης. Δεδομένων|Διεθνή Αλγόριθμου Κρυπτογράφησης. Δεδομένων]] [[:en:International Data Encryption Algorithm|en]] (IDEA), και [[:en:RC4|RC4]]. RSA και Diffie–Hellman χρησιμοποιούν [[:en:Modular exponentiation|modular ύψωση σε δύναμη]].''

Στην άλγεβρα υπολογιστών, η αριθμητική υπολοίπων συνήθως χρησιμοποιείται για να περιορίζει το μέγεθος των ακέραιων συντελεστών σε ενδιάμεσους υπολογισμούς και δεδομένα. Χρησιμοποιείται στην [[:en:Polynomial factorization|παραγοντοποίηση πολυωνύμου]], ένα πρόβλημα για το οποίο όλοι οι γνωστοί αποδοτικοί αλγόριθμοι χρησιμοποιούν αριθμητική υπολοίπων. Χρησιμοποιείται από τις πιο αποδοτικές υλοποιήσεις του [[:en:Polynomial greatest common divisor|μέγιστου κοινού διαιρέτη πολυωνύμου]] , ακριβή [[γραμμική άλγεβρα]] και [[:en:Gröbner basis|Gröbner βάση]] αλγορίθμους πάνω στους ακέραιους και στους ρητούς αριθμούς.

Στην επιστήμη των υπολογιστών, η αριθμητική υπολοίπων συχνά εφαρμόζεται σε [[:en:Bitwise operation|bitwise πράξεις]] και άλλες πράξεις που αφορούν σταθερού πλάτους, κυκλικές [[Δομή δεδομένων|δομές δεδομένων]]. Η [[:en:Modulo operation|λειτουργία modulo]], όπως εφαρμόζεται σε πολλές [[Γλώσσα προγραμματισμού|γλώσσες προγραμματισμού]] και [[Αριθμομηχανή|αριθμομηχανές]], είναι μια εφαρμογή της αριθμητικής υπολοίπων που χρησιμοποιείται συχνά σε αυτό το πλαίσιο. [[:en:XOR|XOR]] είναι το άθροισμα των 2 bits, modulo 2.

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

Στη μουσική, το modulo 12 χρησιμοποιείται στην εξέταση του συστήματος του [[:en:Twelve-tone equal temperament|δωδεκάτονου ίσου τέμπου]], όπου προκύπτει η [[:en:Octave|οκτάβα]] και η [[:en:Enharmonic|εναρμόνια]] ισοδυναμία (δηλαδή, τόνος σε 1∶2 ή 2∶1 αναλογία είναι ισοδύναμα, και η C-[[Δίεση]] θεωρείται η ίδια ως D-[[:en:Flat (music)|ύφεση]]).

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

Το modulo 7 χρησιμοποιείται σε αλγορίθμους που προσδιορίζουν την ημέρα της εβδομάδας για μια συγκεκριμένη ημερομηνία. Ειδικότερα, [[:en:Zeller's congruence|η συνεκτικότητα Zeller]] και ο [[:en:Doomsday algorithm|αλγόριθμος της ημέρας της κρίσεως]] κάνουν μεγάλη χρήση του modulo-7.

Γενικότερα, η αριθμητική υπολοίπων, επίσης, έχει εφαρμογή σε κλάδους όπως το [[δίκαιο]] (βλέπε, για παράδειγμα, [[:en:Apportionment (politics)|κατανομή]]), τα [[οικονομικά]], (βλέπε, για παράδειγμα, [[Θεωρία παιγνίων|τη θεωρία παιγνίων]]) και σε άλλους τομείς των [[Κοινωνικές επιστήμες|κοινωνικών επιστημών]], όπου [[:en:Proportional (fair division)|η αναλογική]] κατανομή και η κατανομή των πόρων αποτελεί κεντρικό μέρος της ανάλυσης.

== Υπολογιστική πολυπλοκότητα ==
Από τη στιγμή που η αριθμητική υπολοίπων έχει ένα τέτοιο ευρύ φάσμα εφαρμογών, είναι σημαντικό να γνωρίζουμε πόσο δύσκολο είναι να λύσουμε ένα σύστημα ισοτιμίας. Ένα γραμμικό σύστημα ισοτιμίας μπορεί να λυθεί σε [[:en:Polynomial time|πολυωνυμικό χρόνο]] με μια μορφή [[Γκαουσιανή απαλοιφή|απαλοιφής Gauss]], για περισσότερες λεπτομέρειες βλέπε [[:en:Linear congruence theorem|θεώρημα γραμμικής ισοτιμίας]] . Αλγόριθμοι, όπως η [[:en:Montgomery reduction|αναγωγή Μοντγκόμερι]] , υπάρχουν, επίσης,  για να επιτρέπουν απλές αριθμητικές πράξεις, όπως ο πολλαπλασιασμός και η [[:en:Modular exponentiation|εκθετοποίηση ή ύψωση σε δύναμη modulo ''n'']], να εκτελούνται αποτελεσματικά σε μεγάλους αριθμούς.

Ορισμένες λειτουργίες, όπως η εύρεση ενός [[:en:Discrete logarithm|διακριτού λογαρίθμου]] ή οι [[:en:Quadratic congruences|δευτεροβάθμιες ισοτιμίες]] φαίνεται να είναι τόσο δύσκολες όσο η [[:en:Integer factorization|παραγοντοποίηση ακεραίων]] και, επομένως, το σημείο εκκίνησης είναι η [[Κρυπτογραφία|Κρυπτογραφία αλγορίθμων]] και η [[:en:Encryption|Κρυπτογράφηση]]. Αυτά τα προβλήματα είναι [[:en:NP-intermediate|NP-ενδιάμεσα]].

Η επίλυση του συστήματος των μη-γραμμικών εξισώσεων αριθμητικής υπολοίπων είναι [[:en:NP-complete|NP-πλήρης]].<ref>{{cite book |first=M. R. |last=Garey |first2=D. S. |last2=Johnson |title=Computers and Intractability, a Guide to the  Theory of NP-Completeness |publisher=W. H. Freeman |year=1979 |isbn=0716710447 }}</ref>

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

Οι περισσότερες γλώσσες προγραμματισμού υποστηρίζουν τον υπολογισμό υπολοίπων. Για παράδειγμα, στην C/C++/Java έχουν την πράξη <syntaxhighlight lang="c" inline>%</syntaxhighlight>, που επιτρέπει να γράψουμε
<syntaxhighlight lang="c++">
int a = 53;
int b = 23;
int m = 100;
int res = (a * b) % m; // res=19.
</syntaxhighlight>
Ένα πιθανό πρόβλημα με αυτή την υλοποίηση είναι ότι ο τύπος int, κρατάει αριθμούς με περιορισμένο πλήθος δυαδικών ψηφίων (συνήθως 16 ή 32). Αυτό σημαίνει ότι αν ο <syntaxhighlight lang="c" inline>a</syntaxhighlight> και ο <syntaxhighlight lang="c" inline>b</syntaxhighlight> είναι αρκετά μεγάλοι, τότε το γινόμενο τους μπορεί να [[Αριθμητική υπερχείλιση|υπερχειλίσει]], παρόλο που το αποτέλεσμα χωράει σε int (πχ όταν <math>a = 2^{31} - 1</math>).

Παρακάτω δίνονται δύο αρκετά γρήγορες υλοποιήσεις [[C (γλώσσα προγραμματισμού)|C]] για την εκτέλεση πολλαπλασιασμού υπολοίπων στους μη προσημασμένους ακεραίους όχι μεγαλύτερους από 63 bits, αποφεύγοντας κάποια πιθανή [[Αριθμητική υπερχείλιση|υπερχείλιση]] στις ενδιάμεσες πράξεις. Ο πρώτος είναι ο εξής:<ref>{{cite journal |last=Shoup |first=Victor |title=A New Polynomial Factorization Algorithm and its Implementation |journal=Journal of Symbolic Computation |year=1995 |volume=20 |issue=4 |pages=363–397 |doi=https://doi.org/10.1006/jsco.1995.1055}}</ref>{{rp|24}}<ref>{{cite web |title=Modular multiplication |url=https://cs.stackexchange.com/questions/77016/modular-multiplication |publisher=CS Stackexchange |accessdate=22 Ιουλίου 2022}}</ref><ref>{{cite web |last=Ivanov |first=Mikhail |title=Fast Modular Multiplication |url=https://codeforces.com/blog/entry/96759 |publisher=Codeforces |accessdate=22 Ιουλίου 2022}}</ref>
<syntaxhighlight lang="c++">
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;
}
</syntaxhighlight>

Στις αρχιτεκτονικές των υπολογιστών, όπου μια [[:en:Extended precision#x86 Extended Precision Format|εκτεταμένης ακριβείας]] μορφή, με τουλάχιστον 64 bits mantissa, είναι διαθέσιμη (όπως ο [[:en:Long double|long double]] τύπος των περισσοτέρων x86 C compilers), η παρακάτω συνάρτηση μπορεί να χρησιμοποιηθεί. Κάνει χρήση του πολλαπλασιασμού [[:en:Floating point|κινητής υποδιαστολής]] και ότι το αποτέλεσμα διατηρεί τα πιο σημαντικά bits του γινομένου, τα οποία θα χανόντουσαν αν χρησιμοποιούσαμε τον αντίστοιχο πολλαπλασιασμό ακεραίων (λόγω της υπερχείλισης).
<syntaxhighlight lang="c++">
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;
}
</syntaxhighlight>
Ωστόσο, και για τις δύο ρουτίνες για να λειτουργήσουν, το {{math|''m''}} δεν πρέπει να υπερβαίνει τα 63 bits.

== Δείτε επίσης ==
{{Div col||25em}}
* [[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 function|Carmichael's theorem]]
** [[Κινεζικό Θεώρημα Υπολοίπων]]
** [[Θεώρημα του Όιλερ]]
** [[Μικρό θεώρημα του Φερμά]] 
** [[Lagrange's theorem (group theory)|Lagrange's theorem]]
** [[Thue's lemma]]
{{Div col end}}

==Πηγές==
* 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"
* [[:en:Thomas H. Cormen|Thomas H. Cormen]], [[:en:Charles E. Leiserson|Charles E. Leiserson]], [[:en:Ronald L. Rivest|Ronald L. Rivest]], and [[:en:Clifford Stein|Clifford Stein]]. ''[[:en:Introduction to Algorithms|Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001.[[:en:Special:BookSources/0262032937|ISBN 0-262-03293-7]]. Section 31.3: Modular arithmetic, pp.&nbsp;862–868.
* Anthony Gioia, ''Number Theory, an Introduction''Reprint (2001) Dover. [[:en:Special:BookSources/0486414493|ISBN 0-486-41449-3]]
* Long, Calvin T. (1972), ''Elementary Introduction to Number Theory'' (2nd ed.{{citation|last=Long|first=Calvin T.|title=Elementary Introduction to Number Theory|year=1972|edition=2nd|location=Lexington|publisher=[[D. C. Heath and Company]]|lccn=77171950}}
* {{citation|title=Elements of Number Theory|year=1970|last1=Pettofrezzo|last2=Byrkit|first1=Anthony J.|first2=Donald R.|location=Englewood Cliffs|publisher=[[Prentice Hall]]|lccn=71081766}}
* Sengadir, T. (2009). {{cite book|title=Discrete Mathematics and Combinatorics|last=Sengadir|first=T.|publisher=Pearson Education India|year=2009|isbn=978-81-317-1405-8|location=Chennai, India|oclc=778356123}}[[:en:OCLC|OCLC]]&nbsp;778356123.

==Παραπομπές==
<references />

== Εξωτερικοί σύνδεσμοι ==
*[https://www.itia.ntua.gr/en/docinfo/1318/ English - Greek Dictionary of Pure and Applied Mathematics] Εθνικό Μετσόβιο Πολυτεχνείο
*[https://www.mas.ucy.ac.cy/georgios/bookfiles/dict1.pdf Αγγλοελληνικό Λεξικό Μαθηματικής Ορολογίας - Πανεπιστήμιο Κύπρου]
* {{springer|title=Congruence|id=p/c024850}}
* In this modular art article, one can learn more about applications of modular arithmetic in art.
* [[:en:Eric W. Weisstein|Weisstein, Eric W.]], "Modular Arithmetic", ''[[:en:MathWorld|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.

{{Portal bar|Μαθηματικά}}

{{DEFAULTSORT:Αριθμητική υπολοίπων}}
[[Κατηγορία:Αριθμητική|*]]
[[Κατηγορία:Θεωρία ομάδων]]