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

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Ο χρόνος περνά σε αυτό το ρολόι χρησιμοποιώντας την αριθμητική μόντουλο 12.

Στα μαθηματικά, αριθμητική υπολοίπων είναι ένα σύστημα αριθμητικής για ακέραιους αριθμούς, όπου οι αριθμοί "αναδιπλώνονται" μετά την επίτευξη μιας ορισμένης τιμής— συντελεστής (πληθυντικός 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.

Υπόλοιπα[Επεξεργασία | επεξεργασία κώδικα]

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

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

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

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

ή ισοδύναμα,

Στην επιστήμη των υπολογιστών, είναι το υπόλοιπο του τελεστή, που συνήθως αναφέρεται είτε με το "%" (για παράδειγμα, 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 της σελίδας.

Μειωμένα συστήματα υπολοίπων[Επεξεργασία | επεξεργασία κώδικα]

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

Ακέραιοι modulo n[Επεξεργασία | επεξεργασία κώδικα]

Το σύνολο όλων των κλάσεων ισοτιμίας των ακεραίων για ένα συντελεστή n ονομάζεται το σύνολο των ακεραίων modulo n, και συμβολίζεται , ή . Ο συμβολισμός , ωστόσο, δεν συνιστάται επειδή μπορεί να συγχέεται με το σύνολο των n-adic αριθμούς. Το σύνολο ορίζεται ως εξής.

Όταν n ≠ 0, έχει n στοιχεία και μπορεί να γραφεί ως:

Όταν n = 0, δεν έχει μηδενικά στοιχεία, μάλλον, είναι ισομορφική στο , όταν a0 = {a}}}.

Μπορούμε να ορίσουμε πρόσθεση, αφαίρεση και πολλαπλασιασμό στο σύνολο με τους ακόλουθους κανόνες:

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

Με τον τρόπο αυτό, γίνεται ένας αντιμεταθετικός δαχτύλιος. Για παράδειγμα, στο δακτύλιο , έχουμε

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

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

Όσον αφορά τις ομάδες, η κλάση υπολοίπων an}} είναι το σύμπλοκο της a στην ομάδα πηλίκου , μια κυκλική ομάδα.[2].

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

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

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

Εκθετοποίηση υπολοίπων[Επεξεργασία | επεξεργασία κώδικα]

Είναι πολύ χρήσιμο το γεγονός ότι η τιμή yax (mod n) μπορεί να υπολογιστεί πολύ αποτελεσματικά, ακόμη και όταν ο αριθμός ax είναι πολύ μεγάλος για να υπολογίσει (βλ. εκθετοποίηση υπολοίπων για λεπτομέρειες.) το y μπορεί να υπολογιστεί χωρίς κάθε φορά να ασχολούμαστε με νούμερα μεγαλύτερο από το n2.

Υπολογιστική πολυπλοκότητα[Επεξεργασία | επεξεργασία κώδικα]

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

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

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

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

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

  1. «Long (1972, p. 85)». 
  2. Sengadir T., Discrete Mathematics and Combinatorics, σ. 293, στα Google Books
  3. Garey, M. R.· Johnson, D. S. (1979). Computers and Intractability, a Guide to the Theory of NP-Completeness. W. H. Freeman. ISBN 0716710447.