Στα μαθηματικά, η αρθρωτή αριθμητική είναι ένα σύστημα υπολογισμού για ακέραιους αριθμούς, με τη βοήθεια του οποίου «γυρίζουν» όταν φτάσουν σε μια ορισμένη τιμή - τη μονάδα (ή τον πληθυντικό τους). Η σύγχρονη προσέγγιση σε αυτό το είδος της επιστήμης αναπτύχθηκε από τον Carl Friedrich Gauss στο Disquisitiones Arithmeticae που δημοσιεύτηκε το 1801. Οι επιστήμονες υπολογιστών λατρεύουν πολύ να χρησιμοποιούν αυτή τη μέθοδο, καθώς είναι πολύ ενδιαφέρουσα και ανοίγει ορισμένες νέες δυνατότητες σε πράξεις με αριθμούς.
Essence
Επειδή ο αριθμός των ωρών ξεκινά ξανά αφού φτάσει τις 12, είναι αριθμητικό modulo 12. Σύμφωνα με τον παρακάτω ορισμό, το 12 αντιστοιχεί όχι μόνο στο 12, αλλά και στο 0, επομένως μπορεί κανείς να ονομάσει και την ώρα που ονομάζεται " 12:00". "0:00". Τελικά, το 12 είναι το ίδιο με το 0 modulo 12.
Η αρθρωτή αριθμητική μπορεί να επεξεργαστεί μαθηματικά εισάγοντας μια συνεπή σχέση με ακέραιους που είναι συμβατή με πράξεις σε ακέραιους αριθμούςαριθμοί: πρόσθεση, αφαίρεση και πολλαπλασιασμός. Για έναν θετικό ακέραιο n, δύο αριθμοί a και b λέγονται ότι είναι ίσοι modulo n εάν η διαφορά τους a - b είναι πολλαπλάσιο του n (δηλαδή, εάν υπάρχει ένας ακέραιος k τέτοιος ώστε a - b=kn).
Παρεκπτώσεις
Στα θεωρητικά μαθηματικά, η αρθρωτή αριθμητική είναι ένα από τα θεμέλια της θεωρίας αριθμών, επηρεάζοντας σχεδόν όλες τις πτυχές της μελέτης της, και χρησιμοποιείται επίσης ευρέως στη θεωρία των ομάδων, των δακτυλίων, των κόμβων και της αφηρημένης άλγεβρας. Στον τομέα των εφαρμοσμένων μαθηματικών, χρησιμοποιείται στην άλγεβρα υπολογιστών, την κρυπτογραφία, την επιστήμη των υπολογιστών, τη χημεία, τις εικαστικές τέχνες και τη μουσική.
Πρακτική
Μια πολύ πρακτική εφαρμογή είναι ο υπολογισμός των αθροισμάτων ελέγχου σε αναγνωριστικά σειριακού αριθμού. Για παράδειγμα, ορισμένα κοινά πρότυπα βιβλίων χρησιμοποιούν το αριθμητικό modulo 11 (εάν κυκλοφόρησε πριν από την 1η Ιανουαρίου 2007) ή το modulo 10 (αν κυκλοφόρησε πριν ή μετά την 1η Ιανουαρίου 2007). Ομοίως, για παράδειγμα, στους Διεθνείς Αριθμούς Τραπεζικών Λογαριασμών (IBAN). Αυτό χρησιμοποιεί την αριθμητική modulo 97 για τον εντοπισμό σφαλμάτων εισαγωγής χρήστη στους αριθμούς τραπεζικών λογαριασμών.
Στη χημεία, το τελευταίο ψηφίο του αριθμού καταχώρισης CAS (ο μοναδικός αριθμός αναγνώρισης για κάθε χημική ένωση) είναι το ψηφίο ελέγχου. Υπολογίζεται παίρνοντας το τελευταίο ψηφίο των δύο πρώτων μερών του αριθμού εγγραφής CAS πολλαπλασιασμένο επί 1, το προηγούμενο ψηφίο 2 φορές, το προηγούμενο ψηφίο 3 φορές κ.λπ., αθροίζοντας τα όλα και υπολογίζοντας το modulo αθροίσματος 10.
Τι είναι η κρυπτογραφία; Γεγονός είναι ότιέχει πολύ ισχυρή σχέση με το θέμα που συζητείται. Στην κρυπτογραφία, οι νόμοι της αρθρωτής αριθμητικής αποτελούν άμεσα τη βάση των συστημάτων δημόσιου κλειδιού όπως το RSA και το Diffie-Hellman. Εδώ παρέχει τα πεπερασμένα πεδία που βρίσκονται κάτω από τις ελλειπτικές καμπύλες. Χρησιμοποιείται σε διάφορους αλγόριθμους συμμετρικών κλειδιών, όπως το Advanced Encryption Standard (AES), τον International Data Encryption Algorithm και τον RC4.
Αίτηση
Αυτή η μέθοδος χρησιμοποιείται σε περιοχές όπου πρέπει να διαβάζετε αριθμούς. Αναπτύχθηκε από μαθηματικούς και το χρησιμοποιούν όλοι, ειδικά επιστήμονες υπολογιστών. Αυτό είναι καλά τεκμηριωμένο σε βιβλία όπως το Modular Arithmetic for Dummies. Ωστόσο, ορισμένοι ειδικοί συνιστούν να μην παίρνετε στα σοβαρά μια τέτοια βιβλιογραφία.
Στην επιστήμη των υπολογιστών, η αρθρωτή αριθμητική χρησιμοποιείται συχνά σε bitwise και άλλες πράξεις που περιλαμβάνουν κυκλικές δομές δεδομένων σταθερού πλάτους. Οι αναλυτές λατρεύουν να το χρησιμοποιούν. Η λειτουργία modulo υλοποιείται σε πολλές γλώσσες προγραμματισμού και αριθμομηχανές. Σε αυτή την περίπτωση, είναι ένα παράδειγμα τέτοιας εφαρμογής. Σύγκριση μονάδων, διαίρεση με υπόλοιπο και άλλα κόλπα χρησιμοποιούνται επίσης στον προγραμματισμό.
Στη μουσική, το αριθμητικό modulo 12 χρησιμοποιείται όταν εξετάζουμε ένα σύστημα ίσης ιδιοσυγκρασίας δώδεκα τόνων, στο οποίο η οκτάβα και η εναρμονική είναι ισοδύναμες. Με άλλα λόγια, τα κλειδιά στην αναλογία 1-2 ή 2-1 είναι ισοδύναμα. Στη μουσική και σε άλλες ανθρωπιστικές επιστήμες, η αριθμητική παίζει μάλλον σημαντικό ρόλο, αλλά στα σχολικά βιβλίαοι επιστήμονες υπολογιστών συνήθως δεν γράφουν γι' αυτό.
Μέθοδος μείωσης των εννιά
Η μέθοδος μετατροπής 9s προσφέρει έναν γρήγορο έλεγχο των μη αυτόματων δεκαδικών αριθμητικών υπολογισμών. Βασίζεται στο αρθρωτό αριθμητικό modulo 9 και συγκεκριμένα στην αποφασιστική ιδιότητα 10 10 1.
υπάρχουν και άλλα παραδείγματα. Το αριθμητικό modulo 7 χρησιμοποιείται σε αλγόριθμους που καθορίζουν την ημέρα της εβδομάδας για μια συγκεκριμένη ημερομηνία. Συγκεκριμένα, η συνάφεια του Zeller και ο αλγόριθμος Doomsday κάνουν μεγάλη χρήση του αριθμητικού modulo 7.
Άλλες εφαρμογές
Έχουν ήδη ειπωθεί για την αρθρωτή αριθμητική στην κρυπτογραφία. Σε αυτόν τον τομέα είναι απλά αναντικατάστατη. Γενικότερα, η αρθρωτή αριθμητική βρίσκει επίσης εφαρμογές σε κλάδους όπως το δίκαιο, τα οικονομικά (όπως η θεωρία παιγνίων) και άλλους τομείς των κοινωνικών επιστημών. Με άλλα λόγια, όπου η αναλογική κατανομή και κατανομή των πόρων παίζει σημαντικό ρόλο.
Επειδή η αρθρωτή αριθμητική έχει τόσο μεγάλο εύρος χρήσεων, είναι σημαντικό να γνωρίζουμε πόσο δύσκολο είναι να λύσουμε ένα σύστημα συγκρίσεων. Ένα γραμμικό σύστημα ευθυγράμμισης μπορεί να λυθεί σε πολυωνυμικό χρόνο με τη μορφή γκαουσιανής εξάλειψης. Αυτό περιγράφεται λεπτομερέστερα από το θεώρημα της γραμμικής συμφωνίας. Αλγόριθμοι όπως η μείωση Montgomery υπάρχουν επίσης για να επιτρέπουν την αποτελεσματική εκτέλεση απλών αριθμητικών πράξεων. Για παράδειγμα, modulo πολλαπλασιασμού και εκθέσεως n, για μεγάλους αριθμούς. Αυτό είναι πολύ σημαντικό να το γνωρίζετε για να καταλάβετε τικρυπτογράφηση. Σε τελική ανάλυση, λειτουργεί απλώς με παρόμοιες λειτουργίες.
Συμφωνία
Ορισμένες πράξεις, όπως η εύρεση του διακριτού λογάριθμου ή της τετραγωνικής συνάφειας, φαίνεται να είναι τόσο περίπλοκες όσο η παραγοντοποίηση ακεραίων και επομένως αποτελούν το σημείο εκκίνησης για κρυπτογραφικούς αλγόριθμους και κρυπτογράφηση. Αυτά τα προβλήματα μπορεί να είναι NP-intermediate.
Παραδείγματα
Ακολουθούν τρεις αρκετά γρήγορες συναρτήσεις C - δύο για την εκτέλεση αρθρωτού πολλαπλασιασμού και μία για την αύξηση σε αρθρωτούς αριθμούς για ανυπόγραφους ακέραιους αριθμούς έως και 63 bit, χωρίς παροδική υπερχείλιση.
Λίγο μετά την ανακάλυψη των ακεραίων αριθμών (1, 2, 3, 4, 5…) γίνεται φανερό ότι χωρίζονται σε δύο ομάδες:
- Ζυγό: διαιρείται με το 2 (0, 2, 4, 6..).
- Περίον: δεν διαιρείται με το 2 (1, 3, 5, 7…).
Γιατί είναι σημαντική αυτή η διάκριση; Αυτή είναι η αρχή της αφαίρεσης. Παρατηρούμε τις ιδιότητες του αριθμού (π.χ. ζυγό ή περιττό) και όχι μόνο τον ίδιο τον αριθμό ("37").
Μας επιτρέπει να εξερευνήσουμε τα μαθηματικά σε βαθύτερο επίπεδο και να βρούμε σχέσεις μεταξύ τύπων αριθμών και όχι συγκεκριμένων.
Ιδιότητες ενός αριθμού
Το να είσαι "τρία" είναι απλώς μια άλλη ιδιότητα ενός αριθμού. Ίσως όχι τόσο άμεσα χρήσιμο όσο το ζυγό/μονό, αλλά είναι εκεί. Μπορούμε να δημιουργήσουμε κανόνες όπως "δεκατρία x τρεις φλέβα=δεκατρία" και ούτω καθεξής. Αλλά είναι τρελό. Δεν μπορούμε να κάνουμε νέες λέξεις συνέχεια.
Η λειτουργία modulo (συντομογραφία mod ή "%" σε πολλές γλώσσες προγραμματισμού) είναι το υπόλοιπο ότανδιαίρεση. Για παράδειγμα, "5 mod 3=2", που σημαίνει ότι το 2 είναι το υπόλοιπο όταν διαιρείτε το 5 με το 3.
Όταν μετατρέπετε καθημερινούς όρους σε μαθηματικά, ένας "ζυγός αριθμός" είναι όπου είναι "0 mod 2", που σημαίνει ότι το υπόλοιπο είναι 0 όταν διαιρείται με το 2. Ένας περιττός αριθμός είναι "1 mod 2" (έχει ένα υπόλοιπο από 1).
Ζυγοί και περιττοί αριθμοί
Τι είναι άρτιο x άρτιο x περιττό x περιττό; Λοιπόν, είναι 0 x 0 x 1 x 1=0. Στην πραγματικότητα, μπορείτε να δείτε αν ένας ζυγός αριθμός πολλαπλασιάζεται οπουδήποτε, όπου το συνολικό αποτέλεσμα θα είναι μηδέν.
Το κόλπο με τα αρθρωτά μαθηματικά είναι ότι το έχουμε ήδη χρησιμοποιήσει για την αποθήκευση του χρόνου - μερικές φορές ονομάζεται "αριθμητική του ρολογιού".
Για παράδειγμα: 7:00 π.μ. (π.μ./μ.μ. - δεν έχει σημασία). Πού θα είναι ο ωροδείκτης σε 7 ώρες;
Modulations
(7 + 7) mod 12=(14) mod 12=2 mod 12 [2 είναι το υπόλοιπο όταν το 14 διαιρείται με το 12. Η εξίσωση 14 mod 12=2 mod 12 σημαίνει 14 ώρες και 2 ώρες δείτε το το ίδιο σε ένα ρολόι 12 ωρών. Είναι ίσα, υποδεικνύονται με ένα τριπλό πρόσημο ίσου: 14 ≡ 2 mod 12.
Άλλο παράδειγμα: είναι 8:00 π.μ. Πού θα είναι το μεγάλο χέρι σε 25 ώρες;
Αντί να προσθέσετε 25 στο 8, μπορείτε να καταλάβετε ότι οι 25 ώρες είναι απλώς "1 ημέρα + 1 ώρα". Η απάντηση είναι απλή. Έτσι, το ρολόι θα τελειώσει 1 ώρα μπροστά - στις 9:00.
(8 + 25) mod 12 ≡ (8) mod 12 + (25) mod 12 ≡ (8) mod 12 + (1) mod 12 ≡ 9 mod 12. Μετατρέψατε διαισθητικά το 25 σε 1 και το προσθέσατε έως 8.
Χρησιμοποιώντας το ρολόι ως αναλογία, μπορούμε να καταλάβουμε αν τοοι κανόνες της αρθρωτής αριθμητικής και λειτουργούν.
Προσθήκη/Αφαίρεση
Ας πούμε ότι δύο φορές είναι ίδιες στο ρολόι μας ("2:00" και "14:00"). Αν προσθέσουμε τις ίδιες x ώρες και στις δύο, τι συμβαίνει; Λοιπόν, αλλάζουν για το ίδιο ποσό στο ρολόι! 2:00 + 5 ώρες ≡ 14:00 + 5 ώρες - και οι δύο θα εμφανίζονται στις 7:00.
Γιατί; Μπορούμε απλά να προσθέσουμε 5 στα 2 υπόλοιπα που έχουν και οι δύο και προχωρούν με τον ίδιο τρόπο. Για όλους τους ίσους αριθμούς (2 και 14), η πρόσθεση και η αφαίρεση έχουν το ίδιο αποτέλεσμα.
Είναι πιο δύσκολο να γνωρίζουμε αν ο πολλαπλασιασμός παραμένει ίδιος. Αν 14 ≡ 2 (mod 12), μπορούμε να πολλαπλασιάσουμε και τους δύο αριθμούς και να έχουμε το ίδιο αποτέλεσμα; Ας δούμε τι συμβαίνει όταν πολλαπλασιάζουμε με το 3.
Λοιπόν, 2:003 × 6:00. Αλλά τι είναι 14:003;
Να θυμάστε, 14=12 + 2. Έτσι μπορούμε να πούμε
143=(12 + 2)3=(123) + (23)
Το πρώτο μέρος (123) μπορεί να αγνοηθεί! Η υπερχείλιση των 12 ωρών που μεταφέρει 14 απλώς επαναλαμβάνεται αρκετές φορές. Αλλά ποιός νοιάζεται? Αγνοούμε την υπερχείλιση ούτως ή άλλως.
Πολλαπλασιασμός
Κατά τον πολλαπλασιασμό, σημασία έχουν μόνο το υπόλοιπο, δηλαδή οι ίδιες 2 ώρες για τις 14:00 και τις 2:00. Διαισθητικά, έτσι βλέπω τον πολλαπλασιασμό να μην αλλάζει τη σχέση με τα αρθρωτά μαθηματικά (μπορείτε να πολλαπλασιάσετε και τις δύο πλευρές μιας σπονδυλωτής σχέσης και να πάρετε το ίδιο αποτέλεσμα).
Το κάνουμε διαισθητικά, αλλά είναι ωραίο να του δίνουμε ένα όνομα. Έχετε μια πτήση που φτάνει στις 3 μ.μ. Αυτόςκαθυστέρηση 14 ωρών. Τι ώρα θα προσγειωθεί;
14 ≡ 2 mod 12. Έτσι, σκεφτείτε το ως 2 η ώρα, έτσι το αεροπλάνο θα προσγειωθεί στις 5 η ώρα το πρωί. Η λύση είναι απλή: 3 + 2=5 π.μ. Αυτό είναι λίγο πιο περίπλοκο από την απλή λειτουργία modulo, αλλά η αρχή είναι η ίδια.
