Σύστημα υπολειπόμενης τάξης - εισαγωγή

Αριθμο-θεωρητική βάση για την κατασκευή συστήματος υπολειπόμενων τάξεων

Θυμηθείτε τον ορισμό της διαίρεσης με υπόλοιπο.

Ορισμός

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

Για ακέραιους αριθμούς:

Ορισμός

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

Παράδειγμα:

48 κατά τη διαίρεση με 5 δίνει το υπόλοιπο 3 , επειδή . -48 κατά τη διαίρεση με 5 δίνει το υπόλοιπο 2 , επειδή , .

Συγκρίσεις και οι κύριες ιδιότητές τους

Ας πάρουμε έναν αυθαίρετο σταθερό φυσικό αριθμό και ας θεωρήσουμε τα υπόλοιπα όταν διαιρούνται με διάφορους ακέραιους αριθμούς.

Κατά την εξέταση των ιδιοτήτων αυτών των υπολοίπων και την εκτέλεση πράξεων σε αυτά, είναι βολικό να εισαγάγουμε την έννοια της σύγκρισης modulo.

Ορισμός

Δύο ακέραιοι και καλούνται συγκρίσιμο σε moduloαν η διαφορά τους διαιρείται ομοιόμορφα με .

Συμβολικά, η συγκρισιμότητα γράφεται ως τύπος ( συγκρίσεις):

Ο αριθμός καλείται μονάδα μέτρησηςσυγκρίσεις.

Αντίστοιχη διατύπωση:

Ορισμός

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

Η σχέση συγκρισιμότητας modulo έχει τις ιδιότητες της ανακλαστικότητας, της συμμετρίας και της μεταβατικότητας, δηλ. είναι μια σχέση ισοδυναμίας.

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

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

Θεώρημα διαίρεσης με υπόλοιπο. Ο αλγόριθμος του Ευκλείδη

Θεώρημα διαίρεσης με υπόλοιπο

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

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

Ο αλγόριθμος του Ευκλείδη για ακέραιους αριθμούς

Έστω και ακέραιοι όχι ίσοι ταυτόχρονα με το μηδέν, και μια ακολουθία αριθμών

ορίζεται από το γεγονός ότι καθένα είναι το υπόλοιπο της διαίρεσης του προηγούμενου αριθμού με τον προηγούμενο και ο προτελευταίος διαιρείται με τον τελευταίο, δηλαδή

Επειτα GCD, ο μεγαλύτερος κοινός διαιρέτης και ισούται με , το τελευταίο μη μηδενικό μέλος αυτής της ακολουθίας.

Υπαρξητέτοια , δηλαδή η δυνατότητα διαίρεσης με υπόλοιπο από για κάθε ακέραιο και ακέραιο , αποδεικνύεται με επαγωγή.

Ορθότητααυτός ο αλγόριθμος προκύπτει από τις ακόλουθες δύο δηλώσεις:

Θεώρημα κινεζικού υπολοίπου

Η θεμελιώδης θέση στην οποία βασίζεται η σπονδυλωτή αναπαράσταση των αριθμών είναι το Κινεζικό Θεώρημα Υπολειμμάτων (CRT). Για παράδειγμα, αυτό το θεώρημα εγγυάται ότι με τη σωστή επιλογή μονάδων RNS, κάθε αριθμός από τη δυναμική περιοχή έχει μια μοναδική αναπαράσταση στο RNS και από αυτήν την αναπαράσταση μπορεί να προσδιοριστεί ο αναπαριστώμενος αριθμός. Στην αρχική του διατύπωση, αυτό το θεώρημα αποδείχθηκε από τον Κινέζο μαθηματικό Sun Tzu γύρω στο 100 μ.Χ. Η σύγχρονη διατύπωση του θεωρήματος έχει ως εξής:

Θεώρημα

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

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

Θεωρήματα Euler και Fermat, ο ρόλος τους στον υπολογισμό των πολλαπλασιαστικών αντίστροφων στοιχείων modulo ένα δεδομένο

Ορισμός

Η συνάρτηση Euler είναι ο αριθμός των αριθμών από έως που είναι συμπρώτοι στο .

Εκείνοι. είναι ο αριθμός τέτοιων φυσικών αριθμών από το διάστημα , του οποίου ο μεγαλύτερος κοινός διαιρέτης (GCD) c είναι ίσος με ένα.

Θεώρημα Euler

Αν και είναι συμπρωτογενείς, τότε , πού είναι η συνάρτηση Euler.

Μια ειδική περίπτωση του θεωρήματος του Euler είναι το μικρό θεώρημα του Fermat.

Το Μικρό Θεώρημα του Φερμά

Αν είναι πρώτος αριθμός και είναι αυθαίρετος ακέραιος που δεν διαιρείται με , τότε .

Αριθμοί Mersenne, Fermat και πράξεις σε αυτούς

Όταν εξετάζουμε ξεχωριστές κατηγορίες πρώτων, το ζήτημα των ειδικών τύπων πρώτων, όπως οι αριθμοί Mersenne ή οι αριθμοί Fermat, είναι ενδιαφέρον.

Ορισμός

Αριθμοί Mersenne- αριθμοί του εντύπου , όπου είναι ένας φυσικός αριθμός. Έχουν πάρει το όνομά τους από τον Γάλλο μαθηματικό Marin Mersenne.

Μερικές φορές μόνο αριθμοί με περιττούς ή πρώτους δείκτες ονομάζονται αριθμοί Mersenne. n.

Τα σύνολα των πρώτων αριθμών σε αυτές τις ακολουθίες συμπίπτουν και επομένως η έννοια Πρώτος αριθμός Mersenneδεν εξαρτάται από το πώς ορίζονται οι αριθμοί Mersenne.

Για τις πρώτες τιμές n = p, ο αριθμός μπορεί να είναι πρώτος, αλλά μπορεί να είναι σύνθετος. Για παράδειγμα, όταν παίρνουμε πρώτους αριθμούς Mersenne: , και όταν οι αριθμοί είναι σύνθετοι.

Ορισμός

Αριθμοί φάρμας- αριθμοί του εντύπου , Οπου nείναι ένας μη αρνητικός ακέραιος αριθμός.

Όταν οι αριθμοί Fermat είναι απλοί: . Είναι γνωστό ότι οι αριθμοί είναι σύνθετοι. Από το 2014, δεν βρέθηκε ούτε ένας πρώτος αριθμός αυτού του είδους για .

Όλοι οι αριθμοί Mersenne και Fermat είναι συμπρώτοι. Επιπλέον, για ενότητες RNS της φόρμας , οι πράξεις μετατροπής και αριθμητικής υλοποιούνται εύκολα. Επομένως, είναι αποτελεσματικό να επιλέγετε μονάδες RNS με τη μορφή αριθμών Mersenne και Fermat.

Μαθηματικά Μοντέλα Αρθρωτής Αναπαράστασης και Παράλληλης Επεξεργασίας Πληροφοριών

Καθορισμός συστήματος υπολειπόμενης τάξης

Η αναπαράσταση των αριθμών ως ένα σύνολο υπολοίπων από τη διαίρεση σε επιλεγμένες φυσικές μονάδες - οι βάσεις του συστήματος ονομάζεται σύστημα υπολειπόμενων κλάσεων - RNS (σύστημα αριθμών υπολειμμάτων - RNS) ή αρθρωτό σύστημα αριθμών - MCC (modular system).

Η επιλογή του RNS ως αριθμητικού συστήματος

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

Οι ακόλουθες απαιτήσεις ισχύουν για οποιοδήποτε σύστημα κωδικών:

• τη δυνατότητα αναπαράστασης σε αυτό το σύστημα οποιασδήποτε τιμής στο εξεταζόμενο, προκαθορισμένο εύρος·
• μοναδικότητα αναπαράστασης - οποιοσδήποτε συνδυασμός κωδικών αντιστοιχεί σε έναν και μόνο έναν αριθμό σε μια δεδομένη περιοχή.
• ευκολία λειτουργίας με αριθμούς σε ένα δεδομένο σύστημα αριθμών.

Τα αριθμητικά συστήματα διακρίνονται σε θέσεις, μη θέσεις και μικτά. (Σημειογραφία)

Στα συστήματα αριθμών θέσης, το ίδιο αριθμητικό πρόσημο (ψηφίο) σε μια καταχώρηση αριθμού έχει διαφορετικές σημασίες ανάλογα με τον τόπο (ψηφίο) όπου βρίσκεται. Συνήθως χρησιμοποιείται το β-αρικό σύστημα αριθμών, το οποίο ορίζεται από έναν ακέραιο b>1, που ονομάζεται βάση του συστήματος αριθμών.

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

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

Οποιαδήποτε υπολογιστική δομή σχετίζεται στενά με το σύστημα αριθμών στο οποίο λειτουργεί.

Στο συμβατικό σύστημα αριθμών θέσης (PSS), η τιμή ενός ψηφίου οποιουδήποτε αριθμού, εκτός από το χαμηλότερο, που είναι το αποτέλεσμα μιας αριθμητικής πράξης δύο θέσεων, δεν εξαρτάται μόνο από την τιμή των τελεστών με το ίδιο όνομα. , αλλά και σε όλα τα κάτω ψηφία, δηλαδή, το PSS έχει μια αυστηρά διαδοχική δομή. Αντίθετα, οι μη θέσεις κώδικες με παράλληλη δομή καθιστούν δυνατή την υλοποίηση παραλληλισμού πράξεων στο επίπεδο εκτέλεσης στοιχειωδών αριθμητικών πράξεων.

Ως τέτοιο σύστημα μη θέσης, το σύστημα υπολειπόμενων κατηγοριών (RCS) είναι βολικό.

Οι βασικές αριθμητικές πράξεις στο RNS χωρίζονται σε δύο ομάδες: αρθρωτές και μη αρθρωτές.

• Αρθρωτές πράξεις που μπορούν να εκτελεστούν παράλληλα και ανεξάρτητα σε μεμονωμένα ψηφία αριθμών: πρόσθεση, πολλαπλασιασμός, ανυπόγραφη αφαίρεση.

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

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

Αρθρωτές πράξεις σε αριθμούς στο σύστημα υπολειπόμενων κλάσεων

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

Βασικές μέθοδοι και αλγόριθμοι για τη μετάβαση από αναπαράσταση θέσης σε υπολείμματα

Συνήθως, τα δεδομένα πηγής για τους υπολογισμούς παρουσιάζονται σε κάποια παραδοσιακή αναπαράσταση, δυαδική ή δεκαδική. Τα αποτελέσματα των υπολογισμών αναμένονται με την ίδια μορφή. Αυτό εξηγεί την ανάγκη να μεταφραστούν αριθμοί από αναπαράσταση θέσης σε αναπαράσταση RNS (άμεσος μετασχηματισμός) και αντίστροφα (αντίστροφος μετασχηματισμός). Μία από τις πρώτες μη αρθρωτές διαδικασίες είναι η άμεση μετατροπή των κωδικών θέσης σε κώδικα RNS.

Η μετατροπή ενός αριθμού σε ένα σύστημα υπολειπόμενων κλάσεων μπορεί να γίνει απευθείας με τη μέθοδο της διαίρεσης, με διαιρέτες RNS modules. Ωστόσο, λόγω της πολυπλοκότητας της λειτουργίας διαίρεσης, η τεχνική εφαρμογή αυτής της μεθόδου είναι αναποτελεσματική. Ως εκ τούτου, εξετάζονται άλλες μέθοδοι. Για παράδειγμα, χρησιμοποιείται συχνά μια μέθοδος μετατροπής ενός αριθμού από ένα σύστημα αριθμών θέσης σε ένα RNS, η οποία δεν περιέχει πράξεις διαίρεσης, που ονομάζεται μέθοδος άμεσης άθροισης των αρθρωτών τιμών των ψηφίων του αριθμού θέσης.

Επαναφορά της αναπαράστασης θέσης ενός αριθμού από τα υπόλοιπα του

Το σύστημα υπολειπόμενων κλάσεων έχει ένα χαρακτηριστικό που μπορεί να αποδοθεί στα μειονεκτήματα αυτού του συστήματος: είναι αδύνατο να προσδιοριστεί οπτικά η τιμή του αριθμού που αντιπροσωπεύεται στο RNS και επομένως είναι επίσης δύσκολο να εκτελεστούν λειτουργίες όπως η σύγκριση αριθμών, ο προσδιορισμός το πρόσημο ενός αριθμού. Ένας τρόπος για να λυθεί αυτό το πρόβλημα είναι η μετατροπή αριθμών από RNS σε σύστημα αριθμών θέσης. Ας αξιολογήσουμε τις υπάρχουσες μεθόδους μετάφρασης ως παραδοσιακές: η μέθοδος των ορθογώνιων βάσεων. η μετάφραση ενός αριθμού σε ένα γενικευμένο σύστημα θέσης (GPS), καθώς και οι πρόσφατα εμφανιζόμενες μέθοδοι μετάφρασης διαστήματος.

Μέθοδος ορθογώνιων βάσεων

Η μέθοδος ανάκτησης ενός αριθμού από τα λείψανά του βρέθηκε στην Κίνα πριν από δύο χιλιάδες χρόνια. Η βάση αυτής της μεθόδου είναι ένα θεώρημα που ονομάζεται Κινεζικό Θεώρημα Υπόλοιπων (CRT).

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

Μετατροπή αριθμού από RNS σε γενικευμένο σύστημα θέσης (OPS)

Μια άλλη μέθοδος για τον προσδιορισμό του μεγέθους ενός αριθμού σχετίζεται με τη μεταφορά ενός αριθμού από το σύστημα υπολειπόμενων κλάσεων στο OPS. Για να εξετάσουμε αυτή τη μέθοδο, θα αποκαλύψουμε τη σχέση μεταξύ της αναπαράστασης ενός συγκεκριμένου αριθμού σε αυτά τα δύο συστήματα.

Έστω, όπως πριν, το RNS να δίνεται με βάσεις και να είναι ένας αριθμός σε αυτό το σύστημα. Και ας είναι επίσης οι βάσεις του OPS, τότε ο αριθμός μπορεί να αναπαρασταθεί ως

όπου είναι οι συντελεστές (αριθμοί) του Ο.Π.Σ.

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

Αυτή η ισότητα μπορεί να ξαναγραφτεί ως εξής:

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

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

Μέθοδοι διαλειμματικής μετάφρασης

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

Επέκταση του εύρους αναπαράστασης αριθμών

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

Το πρόβλημα της επέκτασης του συστήματος βάσεων μπορεί να διατυπωθεί ως εξής: βρείτε την υπολειπόμενη αναπαράσταση ενός αριθμού με μια νέα βάση (νέες βάσεις), εάν είναι γνωστή η αναπαράσταση ενός αριθμού από άλλες βάσεις (υπολείμματα από τη διαίρεση με άλλους αριθμούς). Ένας τρόπος επέκτασης του βασικού συστήματος είναι να μετατρέψετε τον αριθμό σε σύστημα αριθμών θέσης και να υπολογίσετε το υπόλοιπο μετά τη διαίρεση με μια νέα μονάδα. Αυτή η διαδρομή δεν είναι ορθολογική ως προς τον αριθμό των πράξεων.

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

Βιβλιογραφία

Bukhshtab A. A. Θεωρία αριθμών - M: Nauka, 1975

Ιρλανδία Κ. Κλασική εισαγωγή στη σύγχρονη θεωρία αριθμών. Μ: Μιρ, 1987.

Akushinsky I. L., Yuditsky D. I. Αριθμητική μηχανής σε υπολειπόμενες τάξεις. - Μ. Σοβιετικό ραδιόφωνο, 1968.

Amerbaev V. M. Θεωρητικά θεμέλια της αριθμητικής μηχανής, - Alma-Ata: Science, 1976.

Επιπροσθέτως:

Siziy SV Διαλέξεις για τη θεωρία αριθμών. Εγχειρίδιο για μαθηματικές ειδικότητες. Αικατερινούπολη, Κρατικό Πανεπιστήμιο Ουραλίων. A.M. Gorky, 1999.

Έστω m κάποιος φυσικός αριθμός. Δεν διαιρούνται όλοι οι φυσικοί αριθμοί με το m. Πιθανά υπόλοιπα από τη διαίρεση είναι 1, 2, ..., m - 1, 0 (το τελευταίο όταν διαιρείται με ακέραιο). Modulo m, κάθε φυσικός αριθμός λαμβάνεται ως το υπόλοιπο της διαίρεσης αυτού του αριθμού με το m: $25\,mod\,3 = 1, \\ 9\,mod\,7=2, \\ 100\,mod\,26 =22 , \\ 100\, mod\,32=4$$, κ.λπ.

Καλούνται δύο αριθμοί α και β modulo m, αν όταν διαιρεθούν με m δίνουν το ίδιο υπόλοιπο, δηλ. αν %%a\,mod\,m=b\,mod \,m%%.

Σε αυτήν την περίπτωση, γράψτε %%a≡b (mod\,m)%% ("a είναι συγκρίσιμη με %%b%% modulo %%m%%"). Έτσι, για παράδειγμα, $$5\equiv11(mod\,3),\\ 25\equiv0(mod\,5), \\ 48\equiv6(mod \,7).$$

Στο σύνολο των αριθμών %%1, 2, ..., m - 1%%, %%0%%, συντελεστής πρόσθεσης %%m%% εισάγεται: το αποτέλεσμα είναι το υπόλοιπο της διαίρεσης του συνηθισμένου αθροίσματος όρων με το μέτρο %%m% %, δηλ. %%a+_m b=(a+b)mod\, m%%. Για παράδειγμα, η προσθήκη του modulo 2 δίνει %%0+_2 0=1+_2 1=0%% και %%0+_21=1+_20=1%%. Ας φτιάξουμε έναν πίνακα προσθήκης modulo 3:

Όπως μπορείτε να δείτε, %%2+_32 = (2+2)mod\,3 = 4\,mod\,3 = 1%%.

Κατά την αφαίρεση του modulo m για τους αντίστοιχους αριθμούς, πραγματοποιείται η συνήθης αφαίρεση και, εάν το αποτέλεσμα είναι αρνητικός αριθμός, προστίθεται m σε αυτόν. Για παράδειγμα, modulo 5 έχουμε: %%1 –_5\,4 = -3\,mod\,5 = 2%%.

Εάν κάποιο αλφάβητο έχει καρδινάλιο m (δηλαδή έχει m γράμματα), τότε το modulo m πρόσθεσης και αφαίρεσης μπορεί να ερμηνευθεί ως πρόσθεση και αφαίρεση γραμμάτων με αντίστοιχους αριθμούς. Άρα, για m=32 (ρωσικό αλφάβητο) έχουμε: $$Y - C = 10 -_(32) 23 = -13\,mod\,32 = 19 = T,$$ $$T + T = 19 + _ (32) 19= 38\,mod\,32=6=E $$, κ.λπ.

Με αυτήν την ερμηνεία των σπονδυλωτών πράξεων πρόσθεσης και αφαίρεσης, η κρυπτογράφηση Vigenère είναι η προσθήκη ενός μπλοκ απλού κειμένου με ένα κλειδί που καθορίζει την αυθεντικότητα του αλφαβήτου. Για παράδειγμα, ας κρυπτογραφήσουμε το απλό κείμενο με τον κρυπτογράφηση Vigenère στο κλειδί του προβλήματος. Το μήκος των μπλοκ (και του κλειδιού) είναι 6. Το κείμενο χωρίζεται σε δύο μπλοκ:

(ciphervi) (γενή),

καθένα από τα οποία προστίθεται γράμμα προς γράμμα στο κλειδί:

$$(cipherwi) + (πρόβλημα) = (25,9,21,17,3,9) +_(32) (8,1,5,1,24,1) =\\ (33,10,26 ,18,27,10)mod\,32 = (1,10,26,18,27,10) = AISCH,$$

$$(γενικό) + (εργασία) = (7,6,14,6,17,1) +_(32) (8,1,5,1,24,1) =\\ (15,7,19 ,7,9,2)=OZHTZIB$$

Το τελικό κρυπτόγραμμα: AISCHS'YOZHTZHIB.

Κατά την αποκρυπτογράφηση, το κλειδί αφαιρείται γράμμα προς γράμμα από το μπλοκ κρυπτογραφήματος. Έτσι, γνωρίζοντας ότι το κρυπτόγραμμα LAGZJEUUXRTJE λήφθηκε στο κλειδί Vigenère p r o b l e m («εργασία»), μπορούμε εύκολα να επαναφέρουμε το απλό κείμενο. Αρχικά, αφαιρούμε το κλειδί γράμμα προς γράμμα από το πρώτο μπλοκ του κρυπτογράμματος:

$$LAVGZJE – ΠΡΟΒΛΗΜΑ = (12,1,22,7,26,10,5) –_(26) (16,18,15,2,12,5,13) = \\ (-4, -17 ,7,5,14,5,-8)mod\, 26 = (22,9,7,5,14,5,18) = vigener$$

τότε το κλειδί αφαιρείται γράμμα προς γράμμα από το δεύτερο μπλοκ του κρυπτογραφήματος:

$$UUXRTJE - ΠΡΟΒΛΗΜΑ = (21,21,24,18,20,10,5) -_(26)(16,18,15,2,12,5,13) =\\ (5,3,9 ,16,8,5,-8)mod \,26=(5,3,9,16,8,5,18)= ecipher.$$

Απλό κείμενο: κρυπτογράφηση Vigenere.

Στο μέλλον, θα χρειαστούμε επίσης συντελεστή πολλαπλασιασμού m: εκτελείται παρόμοια με την πρόσθεση - το αποτέλεσμα είναι το υπόλοιπο της διαίρεσης με m του συνηθισμένου γινομένου των παραγόντων. Για παράδειγμα, για το modulo πολλαπλασιασμού 4, έχουμε τον ακόλουθο πίνακα:

Σημειώστε την ασυνήθιστη ισότητα %%2 ×_4 2=0%%, και οι δύο παράγοντες είναι διαφορετικοί από το μηδέν και το γινόμενο τους είναι ίσο με μηδέν.

αντίγραφο

1 ΑΡΘΡΩΤΙΚΗ ΑΡΙΘΜΗΤΙΚΗ Σε ορισμένες εφαρμογές, είναι βολικό να εκτελούνται αριθμητικές πράξεις σε ακέραιους αριθμούς που δίνονται στη λεγόμενη αρθρωτή αναπαράσταση.Αυτή η αναπαράσταση προϋποθέτει ότι ο ακέραιος αριθμός αντιπροσωπεύεται από υπολείμματα (υπολείμματα) modulo ενός συνόλου συνπρώτων αριθμών κατά ζεύγη. Η αφαίρεση ενός Ο αριθμός modulo m συμβολίζεται με mod m Για παράδειγμα, mod 5 ; 8 mod mod Σε αυτήν την ενότητα, από τη διάσταση του προβλήματος, δεν θα κατανοήσουμε τον αριθμό των αριθμών στην είσοδο του αλγορίθμου, όπως, για παράδειγμα, στο πρόβλημα ταξινόμησης, αλλά τον αριθμό των bit που χρησιμοποιούνται για την εγγραφή του αριθμού. Ένας αλγόριθμος που λαμβάνει ακέραιους αριθμούς ως είσοδο ονομάζεται πολυώνυμος εάν ο χρόνος εκτέλεσης του είναι περιορισμένος ένα πολυώνυμο σε log, log, log, αυτά ένα πολυώνυμο στα μήκη των αρχικών δεδομένων (στο δυαδικό σύστημα αριθμών), όπου u u mod, Συνήθως γράφεται u (u, u, u) Η πρόσθεση, η αφαίρεση και ο πολλαπλασιασμός είναι εύκολο να γίνουν εάν τα αποτελέσματά τους περιέχονται μεταξύ και, δηλαδή, εάν μπορούν να θεωρηθούν ως υπολογισμοί συντελεστών. Ας δίνονται δύο ακέραιοι u και v από τα υπολειμματικά τους σύνολα , αυτές είναι u (u, u, u) και v (v, v, v) Τότε οι πράξεις πρόσθεσης, πολλαπλασιασμού και αφαίρεσης ορίζονται ως εξής: u + v (w, w, w), όπου w (u + v ) mod ; () u v (,), όπου (u v) mod ; () uv (y, y, y), όπου y uv mod () Εξετάστε το παράδειγμα Έστω, 5, 7 Παίρνουμε Τότε 6 (,6), αφού 6 mod, 6 mod5, 6 mod 7 6 Ομοίως, 9 (, ) , 5 (,) Λόγω () (,), αφού (+) mod, (+) mod5, (6 +) mod 7 αλλά είναι εύκολο να δούμε ότι 5 (,) Σύμφωνα με () και () get: 6 9 (,) είναι η σπονδυλωτή αναπαράσταση του 6 9 (,5) είναι η αρθρωτή παράσταση του 5 Η πράξη διαίρεσης δεν ορίζεται στην αρθρωτή αριθμητική. Οι υπολογισμοί εκτελούνται ανεξάρτητα για κάθε συντελεστή Το ακόλουθο θεώρημα αποδεικνύει ότι η αντιστοιχία u ( u, u, u) είναι ένα προς ένα. αριθμοί u in

2 διάστημα [,) και σύνολα της μορφής (u, u, u), u< при <, взаимно однозначно Доказательство Очевидно, что для каждого числа u найдется соответствующий членный набор, так как в интервале [,) заключено ровно значений переменной u и допустимых членных наборов также ровно, так как Достаточно показать, что каждый набор соответствует не более, чем одному числу u Допустим, что два числа u и v, u < v <, соответствуют набору (u, u, u) Тогда разность u v должна делиться на каждое из чисел, так как все взаимно простые, то разность u v должна делиться и на Но u v и u v делится на, те u и v должны отличаться не менее, чем на, а значит не могут оба принадлежать интервалу [,) Результаты аналогичные результатам для целых чисел, справедливы и для полиномов Пусть), () это попарно взаимно простые полиномы, (Тогда любой полином u () такой, что deg(u) < deg(()) можно однозначно представить последовательностью u, u, u ()) остатков от деления (u () на каждый полином () Полином u () это тот единственный полином, для которого deg(u) < deg() и u q + u для некоторого полинома q () Мы в этом случае будем использовать обозначение u u() mod аналогично модульной записи целых чисел По аналогии с целыми числами можно показать, что соответствие u () (u, u(), u ()) взаимно однозначное Пример Пусть, + +, + 5 Рассмотрим u Получаем u mod 6, u mod, u mod +, u mod, таким образом, u (6, +,) Для того, чтобы можно было пользоваться модульной арифметикой, нужны алгоритмы, осуществляющие переход от позиционного представления к модульному и обратно Один из методов перехода от позиционного представления к модульному состоит в том, чтобы разделить число u на каждый из модулей, < Допустим, что каждое из чисел представлении Тогда произведение модулей содержит b разрядов в двоичном требует порядка b двоичных разрядов для записи двоичного представления, а деление u на каждое из чисел, где u <, могло бы потребовать делений b -битового числа на b -битовое число Разбив каждое деление на делений b -битовых чисел на b - битовые, можно перейти к модульному представлению за время O (D(b)), где D (n)

3 χρόνος για τη διαίρεση ενός δυαδικού ακέραιου αριθμού n-bit με έναν ακέραιο n-bit, όπως φαίνεται στα A Aho, J Hopcraft, J Ullman Κατασκευή και ανάλυση υπολογιστικών αλγορίθμων D (n) O(n log n log log n) Η αρθρωτή αναπαράσταση ενός αριθμού μπορεί να υπολογιστεί πολύ πιο γρήγορα , εάν χρησιμοποιήσετε την ακόλουθη μέθοδο Προφανώς, εάν πρέπει να βρείτε τα υπολείμματα, για παράδειγμα, τους αριθμούς modulo 8, 5, 7, τότε μπορείτε πρώτα να βρείτε 8 mod5 5 και 8 mod 77, και μετά 5 mod, 5 mod5, mod 7 και mod αντί για υπολογισμό των 8 mod, 8 mod5, 8 mod 7, και 8 mod // +, αντίστοιχα Τώρα το πρόβλημα του υπολογισμού u mod μειώνεται σε δύο προβλήματα μισού μεγέθους, δηλαδή , u mod u mod για< /, и u mod u mod для / < Далее вычисляем вычеты u и u числа u по модулям / и / / + / и вычеты u, u числа u по модулям / / + / и / / + Таким образом, в свою очередь каждая из подзадач может быть сведена к двум задачам половинного размера, а именно, u mod u mod для < /, и u mod u mod для / < /, u mod u mod для / < / и u mod u mod для / < Время выполнения этого алгоритма можно оценить следующим образом: D (b /) + D(b /) + + D(b) (b/)log (b/)log log (b/) + (b/)log (b/)log log (b/) (b)log blog log b (blog log (b) b(log) /)log log (b) blog log b Выигрыш по времени по сравнению с делением на каждый модуль приблизительно равен blog b blog log b log Блок-схема быстрого алгоритма нахождения модульного представления числа приведена на Рис Вход: Модули (I), I, и целое число u, выход: вычеты t M (I), I, целого числа u по модулям (I) Заметим, что Пример работы алгоритма Пусть, те t Заданы модули, Вычисляем произведения модулей и запоминаем их в массиве q Индекс I номер произведения, индекс J номер шага q q q q q q q q q q u mod q u mod q

4 q u mod mod mod q mod q mod q mod q q M M M M

5 I: q (I,) (I) J: t I: : J q(I, J) q(I, J) * q(I + J, J) (, t) u J t: : I: : J (I, J) (I, J) mod q(I, J) (I + J, J) (I, J) mod q(I, J) I: M (I) (I,) αλγόριθμος για εύρεση της αρθρωτής αναπαράστασης ενός αριθμού

6 ΕΦΑΡΜΟΓΗ ΤΟΥ ΚΙΝΕΖΙΚΟΥ ΘΕΩΡΗΜΑΤΟΣ REMAID Εξετάστε το πρόβλημα της μετατροπής της αρθρωτής αναπαράστασης ενός ακέραιου αριθμού στη θέση του. το θεώρημα του κινεζικού υπολοίπου u, u, όπου u u, u, u) Έστω (Λήμμα Έστω c το γινόμενο όλων των d t, να βρούμε έναν ακέραιο αριθμό u τέτοιο ώστε, εκτός από αυτά τα c mod, αυτά τα d c mod και d< Тогда Число c делится на при Так как c d mod u c d u mod, где c / Доказательство, так что c d u mod, Следовательно, то c d u c d u c d u u mod mod Так как делит, то эти соотношения выполняются и тогда, когда все арифметические операции производятся по модулю Таким образом, Лемма доказана Пример Пусть, 5, 7, 5 и модульное представление числа имеет вид (,) Восстановим число по его модульному представлению Для этого вычислим c 5, c и c 5 Нетрудно проверить, что d так как 5 mod, d так как mod5 и d, 5 mod 7 Тогда по теореме получаем u c d u mod mod 59 Задача состоит в эффективном вычислении c du mod В рассмотренном примере d мы вычисляли перебором Ниже будет показано, как это можно сделать непереборным методом НАИБОЛЬШИЕ ОБЩИЕ ДЕЛИТЕЛИ И АЛГОРИТМ ЕВКЛИДА Пусть и положительные целые числа Положительное целое число g называется наибольшим общим делителем чисел и, обозначается HOD (,), если: g делит и, Всякий общий делитель и делит g Можно показать, что для положительных целых и такое число g единственно Например, HOD (57,)

7 Ο αλγόριθμος του Ευκλείδη για τον υπολογισμό του HOD (,) είναι να υπολογίσει μια ακολουθία υπολοίπων όπου, είναι ένα μη μηδενικό υπόλοιπο μετά τη διαίρεση με και διαιρεί ομοιόμορφα, αυτά + Τότε HOD (,) Με άλλα λόγια, αυτός ο αλγόριθμος υπολογίζει + q για<, где q / Рассмотрим пример Пусть 57, а, следовательно HOD (57,) Блок-схема алгоритма Евклида приведена на Рис ТЕОРЕМА Алгоритм Евклида правильно находит значение HOD,) (Доказательство Алгоритм вычисляет + q для < q / Так как + < при, то алгоритм сходится, те заканчивает работу Из формулы + q следует, что HOD(,) делит +, но так как + + q, то HOD (+,) делит Таким образом, получаем, что HOD (,) HOD (,) HOD(,) Алгоритм Евклида можно расширить так, чтобы он находил не только HOD (,), но и целые числа и y, такие, что + y HOD(,) Блок-схема расширенного алгоритма Евклида показана на Рис, где

8 A, A Q A / A A A Q A A; Ναι Όχι Εκτύπωση A AA AA Εικόνα Αλγόριθμος Ευκλείδη

9 A, A, / A A Q A Q A A A; Εκτύπωση A, Ναι A A A A Q Q Εικόνα Εκτεταμένος αλγόριθμος του Ευκλείδη

10 Παράδειγμα Για το 57 και παίρνουμε q 57 q y y yq 9 y () 9 6 () y y 5 (5) Έτσι, HOD (57,) 57 () + 7 Για + Έστω η ισότητα () ισχύει για και Ας δείξουμε ότι () ισχύει για + Σύμφωνα με τον εκτεταμένο ευκλείδειο αλγόριθμο + q, y + y qy Συνεπάγεται ότι + + y+ + y q(+ y) (5) Με την υπόθεση + + y+ q, αλλά σύμφωνα με τον ευκλείδειο αλγόριθμο q +, έχουμε + + y+ +, το λήμμα αποδεικνύεται Παραπάνω, όταν εξετάζουμε το ζήτημα της επαναφοράς ενός αριθμού από τη σπονδυλωτή αναπαράστασή του, βρήκαμε τους αριθμούς d c mod, Μέχρι στιγμής το κάναμε αυτό με απαρίθμηση Εξετάστε πώς ένας εκτεταμένος αλγόριθμος Ευκλείδειος μπορεί να εφαρμοστεί για να βρεθεί το αντίστροφο ενός δεδομένου αριθμού modulo μια εξίσωση της μορφής b mod, όπου, b και ακέραιοι ονομάζονται γραμμική Διοφαντική εξίσωση Προφανώς, στην περίπτωσή μας, αυτή η εξίσωση έχει τη μορφή mod (6) Είναι γνωστό ότι στη συγκεκριμένη περίπτωση, εάν HOD (,), τότε η εξίσωση έχει μια μοναδική λύση, και αυτή η λύση είναι το στοιχείο αντίστροφο του modulo n Η εξίσωση (6) μπορεί να ξαναγραφτεί ως + y, (7) όπου y είναι κάποιος ακέραιος αριθμός

11 Είναι εύκολο να δούμε ότι αν HOD (,), τότε το (7) είναι μια αποσύνθεση του HOD (,), η οποία μπορεί να βρεθεί χρησιμοποιώντας τον εκτεταμένο ευκλείδειο αλγόριθμο Έτσι, το στοιχείο αντίστροφο προς το modulo μπορεί να βρεθεί χρησιμοποιώντας τον εκτεταμένο αλγόριθμο Ευκλείδη Παράδειγμα Έστω , 5, 7, 5 και η σπονδυλωτή αναπαράσταση του αριθμού έχει τη μορφή (,) Επαναφέρετε τον αριθμό από τη σπονδυλωτή του αναπαράσταση Για να το κάνετε αυτό, υπολογίστε c 5, c και c >) 5 y y () Από εδώ παίρνουμε 5 () +, και το επιθυμητό d mod Ομοίως, βρίσκουμε, d και d Τέλος παίρνουμε, u c d u mod mod 5 6

ΕΦΑΡΜΟΣΜΕΝΗ ΑΛΓΕΒΡΑ. Μέρος Ι: Πεπερασμένα πεδία (πεδία Galois). II 1 / 78 Μέρος Ι Πεπερασμένα πεδία (πεδία Galois). II ΕΦΑΡΜΟΣΜΕΝΗ ΑΛΓΕΒΡΑ. Μέρος Ι: Πεπερασμένα πεδία (πεδία Galois). II 2 / 78 Πεδία υπολειμμάτων modulo prime

6. Αλγόριθμοι γρήγορης διαίρεσης Διαίρεση αριθμών με τη μέθοδο του Νεύτωνα Για λόγους βεβαιότητας, θα υποθέσουμε ότι το μέρισμα a = (a, am) και ο διαιρέτης b = (b, b) γράφονται στο σύστημα αριθμών θέσης με βάση το ().

ΕΦΑΡΜΟΣΜΕΝΗ ΑΛΓΕΒΡΑ. Μέρος I: Πεπερασμένα πεδία ή πεδία Galois. II 1 / 78 Μέρος Ι Πεπερασμένα ή Galois πεδία. II ΕΦΑΡΜΟΣΜΕΝΗ ΑΛΓΕΒΡΑ. Μέρος I: Πεπερασμένα πεδία ή πεδία Galois. II 2 / 78 Πεδία υπολειμμάτων Modulo

ΔΙΑΛΕΞΗ 6 Υπολείμματα ισχύος Ας δοθεί το δομοστοιχείο n και κάποιος αριθμός a συμπρωτάρης με το δομοστοιχείο n. Θεωρήστε μια ακολουθία μοιρών a, a 2, a t. Βρείτε τον μικρότερο αριθμό k έτσι ώστε a k 1 mod n. Ορισμός.

4 Θεωρία αριθμών 4 Ακέραιοι 7 Ορισμός Έστω, b Z Στη συνέχεια διαιρεί το b αν υπάρχει ακέραιος τέτοιος ώστε b (συμβολίζεται με b) 73 Θεώρημα (διαίρεση με υπόλοιπο) Αν, b Z και b, τότε υπάρχουν τέτοιοι ακέραιοι αριθμοί

ΕΦΑΡΜΟΣΜΕΝΗ ΑΛΓΕΒΡΑ. Μέρος Ι: Πεπερασμένα πεδία (πεδία Galois). I 1 / 67 Μέρος Ι Πεπερασμένα πεδία (πεδία Galois). ΕΦΑΡΜΟΣΩ ΑΛΓΕΒΡΑ. Μέρος Ι: Πεπερασμένα πεδία (πεδία Galois). I 2 / 67 Υπολειμματικά πεδία modulo prime

Http://vk.ucoz.et/ Πράξεις σε πολυώνυμα k a k Ένα πολυώνυμο (πολυώνυμο) βαθμού k είναι συνάρτηση της μορφής a, όπου μεταβλητή, a είναι αριθμητικοί συντελεστές (=,.k) και. Μπορεί να ληφθεί υπόψη οποιοσδήποτε αριθμός μη μηδενικός

Διάλεξη 4. ΠΡΟΤΥΠΟ Α.Ε.Σ. ΑΛΓΟΡΙΘΜΟΣ RIJNDAEL. Το AES (Advnced Encrypton Stndrd) είναι ένα νέο πρότυπο κρυπτογράφησης ενός κλειδιού που έχει αντικαταστήσει το πρότυπο DES. Αλγόριθμος Rjndel (rhine-dal)

ΚΡΑΤΙΚΟ ΠΑΝΕΠΙΣΤΗΜΙΟ ΑΕΡΟΔΙΑΣΤΗΜΑΤΙΚΗΣ ΟΡΓΑΝΟΠΟΙΗΣΗΣ, Τμήμα Πληροφοριακών Συστημάτων VKOLESNIK ΦΡΟΝΤΙΣΤΗΡΙΟ ΓΙΑ ΤΟ ΜΑΘΗΜΑ "ΚΩΔΙΚΟΠΟΙΗΣΗ ΚΑΙ ΑΠΟΚΩΔΙΚΟΠΟΙΗΣΗ ΜΗΝΥΜΑΤΩΝ (Αλγεβρική θεωρία κωδικών μπλοκ)"

ΔΙΑΛΕΞΗ 3 ΥΠΟΛΟΓΙΣΜΟΣ ΤΕΤΡΑΓΩΝΙΚΩΝ ΡΙΖΩΝ ΑΡΘΡΩΤΙΚΗ Περίπτωση απλής ενότητας Εξετάστε τη σύγκριση x a mod p, () όπου ο αριθμός p είναι πρώτος και ο ακέραιος a δεν διαιρείται με το p Υπολογισμός της λύσης x αυτής της εξίσωσης είναι

Ugra Physics and Mathematics Lyceum VP Chuvakov ΒΑΣΙΚΕΣ ΘΕΩΡΙΑΣ ΑΡΙΘΜΩΝ Σημειώσεις διάλεξης (0)(mod) (0)(mod) Φυσικοί αριθμοί N, - το σύνολο των φυσικών αριθμών που χρησιμοποιούνται για μέτρηση ή απαρίθμηση

ΔΙΑΛΕΞΗ 3 ΣΧΕΣΗ ΣΥΓΚΡΙΣΙΜΟΤΗΤΑΣ Ας πάρουμε έναν φυσικό ακέραιο m, τον οποίο θα ονομάσουμε μέτρο. Ορισμός. Οι ακέραιοι αριθμοί a και b λέγονται ότι είναι ίσοι modulo m αν η διαφορά (a b) διαιρείται με το m (m a

Πρόσθετα υπολείμματα ισχύος υλικού Δίνεται συντελεστής n και κάποιος αριθμός σχετικά πρώτος στο μέτρο n Θεωρήστε μια ακολουθία δυνάμεων, 2, t, Βρείτε τον μικρότερο αριθμό k έτσι ώστε k mod n

Θέμα. Βασικές αρχές στοιχειώδους θεωρίας αριθμών και εφαρμογές - Θεωρητικό υλικό. Σύνολο υπολειμμάτων modulo, ιδιότητες ομοιομορφιών. Αφήνω να είναι φυσικός αριθμός μεγαλύτερος από . Με Ζ συμβολίζουμε το σύνολο όλων των κλάσεων

Ομοσπονδιακό Πανεπιστήμιο Ural, Ινστιτούτο Μαθηματικών και Επιστήμης Υπολογιστών, Τμήμα Άλγεβρας και Διακριτών Μαθηματικών Η έννοια ενός πολυωνύμου Ορισμοί Ένα πολυώνυμο σε μία μεταβλητή είναι μια έκφραση της μορφής

ΔΙΑΛΕΞΗ 1 ΜΕΡΙΚΑ ΣΤΟΙΧΕΙΑ ΘΕΩΡΙΑΣ ΑΡΙΘΜΩΝ

UDC 68. N.I. Τσερβιακόφ, Ι.Ν. Lavrinenko, S.V. Lavrinenko, O.S. Mezentseva ΜΕΘΟΔΟΙ ΚΑΙ ΑΛΓΟΡΙΘΜΟΙ ΓΙΑ ΣΤΡΟΓΓΥΛΛΩΣΗ, ΚΛΙΜΑΚΩΣΗ ΚΑΙ ΔΙΑΙΡΕΣΗ ΑΡΙΘΜΩΝ ΣΤΗΝ ΑΡΘΡΩΤΙΚΗ ΑΡΙΘΜΕΤΙΚΗ (Στρατιωτικό Ινστιτούτο Πυραυλικών Επικοινωνιών Σταυρούπολης

ΕΡΓΑΣΙΑ ΣΤΟΥΣ ΜΑΘΗΜΑΤΙΚΟΥΣ ΚΥΚΛΟΥΣ ΣΕ ΣΕΙΡΑ ΥΠΟΜΕΝΑ ΑΠΟ ΤΗ ΔΙΙΧΡΩΣΗ ΤΩΝ ΑΡΙΘΜΩΝ ΤΗΣ ΑΚΟΛΟΥΘΙΑΣ FIBONACCCI Μαθητής: Bezmenova Sasha Τάξη: 8 Επιβλέπων: Sgibnev A. I. Η ακολουθία Fibonacci, είναι μια ακολουθία,

Αριθμητικοί αλγόριθμοι Πρώτοι αριθμοί Κόσκινο του Ερατοσθένη Εύρεση διαιρετών (μικρότεροι και μεγαλύτεροι) Παραγοντοποίηση ενός αριθμού σε GCD και LCM Μετατροπή σε άλλο σύστημα αριθμών Αριθμητική υπολοίπων Απλή

ΔΙΑΛΕΞΗ 7 ΔΗΜΟΤΙΚΕΣ ΡΙΖΕΣ Ορισμός. Η κλάση [a], όπου (a, n) = 1, ονομάζεται πρωταρχική ρίζα modulo n αν ο εκθέτης ενός modulo n είναι ίσος με φ(n) την τιμή της συνάρτησης Euler για modulo n. Είναι γνωστό

Ανάλυση της εργασίας ελέγχου Γενικά σχόλια για τα αποτελέσματα του ελέγχου του ελέγχου: 1 Υπάρχει μεγάλος αριθμός αριθμητικών λαθών στους υπολογισμούς Η εμφάνιση αριθμητικών σφαλμάτων από μόνη της είναι αναπόφευκτη

ΥΠΟΥΡΓΕΙΟ ΠΑΙΔΕΙΑΣ ΚΑΙ ΕΠΙΣΤΗΜΗΣ ΤΗΣ ΡΩΣΙΚΗΣ ΟΜΟΣΠΟΝΔΙΑΣ ΚΡΑΤΙΚΟ ΠΑΝΕΠΙΣΤΗΜΙΟ NOVOSIBIRSK ΕΞΕΙΔΙΚΕΥΜΕΝΟ ΕΚΠΑΙΔΕΥΤΙΚΟ ΚΑΙ ΕΠΙΣΤΗΜΟΝΙΚΟ ΚΕΝΤΡΟ Μαθηματικά Βαθμός 8 Πολυώνυμα Πολυώνυμα Νοβοσιμπίρσκ Πολυώνυμα Ορθολογική

Διάλεξη 7 Μιγαδικοί αριθμοί και η αναπαράστασή τους στο επίπεδο Αλγεβρικές πράξεις σε μιγαδικούς αριθμούς Μιγαδική σύζευξη Μέτρο και όρισμα μιγαδικού αριθμού Αλγεβρικές και τριγωνομετρικές μορφές

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

Διάλεξη 2 Θέμα: Πρόσθεση και αφαίρεση διανυσμάτων

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

Επίλυση προβλημάτων στη θεωρία αριθμών 1 Συγκρίσεις πρώτου βαθμού με έναν άγνωστο άξονα b (mod m) Παράδειγμα 1. Λύστε τη σύγκριση O.V. Mitin 1287x447 (mod 516). (1) Λύση: 1) Αντικαταστήστε τους συντελεστές σύγκρισης (1)

Κεφάλαιο Ακέραιοι Θεωρία διαιρετότητας Ακέραιοι ονομάζονται αριθμοί, -3, -, -, 0, 3, αυτοί οι φυσικοί αριθμοί, 3, 4, καθώς και μηδενικοί και αρνητικοί αριθμοί -, -, -3, -4, Το σύνολο όλων των ακεραίων συμβολίζεται με

Οδηγίες, λύσεις, απαντήσεις ΕΞΙΣΩΣΕΙΣ ΣΕ ΑΚΡΑΙΟΥΣ. Εξίσωση με έναν άγνωστο Λύση. Ας το βάλουμε στην εξίσωση. Παίρνουμε την ισότητα (4a b 4) (a b 8) 0. Η ισότητα A B 0, όπου τα A και B είναι ακέραιοι, ικανοποιείται,

ΔΙΑΛΕΞΗ 2 ΥΠΟΛΟΓΙΣΜΟΣ ΤΗΣ ΜΕΓΑΛΥΤΕΡΗΣ ΚΟΙΝΗΣ ΔΙΑΙΡΕΣΗΣ Αλγόριθμος του Ευκλείδη Όταν εργάζεστε με μεγάλους σύνθετους αριθμούς, η αποσύνθεσή τους σε πρώτους παράγοντες, κατά κανόνα, είναι άγνωστη. Αλλά για πολλά εφαρμοσμένα προβλήματα της θεωρίας

Κεφάλαιο 2 Ακέραιοι, ρητοί και πραγματικοί αριθμοί 2.. Ακέραιοι αριθμοί Οι αριθμοί, 2, 3,... λέγονται φυσικοί. Το σύνολο όλων των φυσικών αριθμών συμβολίζεται με Ν, δηλ. Ν = (,2,3,...). Αριθμοί..., 3, 2,0,2,3,...

Παράρτημα 1 ΟΜΑΔΕΣ, ΔΑΚΤΥΛΙΟΙ, ΠΕΔΙΑ Για την κρυπτογραφία, η άλγεβρα είναι ένα από τα κύρια εργαλεία στη θεωρητική έρευνα και στην πρακτική κατασκευή κρυπτογραφικών μετασχηματισμών.

Διάλεξη 2 Ψηφιακές μέθοδοι παρουσίασης πληροφοριών. Ψηφιακούς κωδικούς. Δυαδικά και δεκαεξαδικά συστήματα αριθμών. Μετατροπή αριθμών από ένα σύστημα αριθμών σε άλλο. Δυαδική αριθμητική. Φόρμες παρουσίασης

Www.cryptolymp.ru XIX Διαπεριφερειακή Ολυμπιάδα για μαθητές στα Μαθηματικά και την Κρυπτογραφία (11η τάξη) Λύση του προβλήματος 1 Αρχικά, σημειώνουμε ότι αν N pq, όπου p και q είναι πρώτοι αριθμοί, τότε ο αριθμός των φυσικών αριθμών,

Αλγεβρικά πολυώνυμα. 1 Αλγεβρικά πολυώνυμα βαθμού n σε ένα πεδίο K Ορισμός 1.1 Ένα πολυώνυμο βαθμού n, n N (0), σε μια μεταβλητή z πάνω από έναν αριθμό πεδίου K είναι μια έκφραση της μορφής: fz = a n z n

1 Μιγαδικοί αριθμοί σε αλγεβρική μορφή 1Βασικές έννοιες Ορισμός 1 Ένας μιγαδικός αριθμός σε αλγεβρική μορφή είναι μια έκφραση της μορφής όπου και είναι πραγματικοί αριθμοί, και τα λεγόμενα

ΔΙΑΛΕΞΗ 12 ΣΥΓΚΡΙΣΕΙΣ ΔΕΥΤΕΡΟΥ ΒΑΘΜΟΥ ΣΕ ΑΠΛΕΣ ΑΡΘΡΩΤΕΣ ΚΑΙ ΤΕΤΑΡΧΟΥΣΕΣ ΚΑΤΑΛΟΙΠΕΣ Η γενική μορφή σύγκρισης του modulo p δεύτερου βαθμού έχει τη μορφή (1) c 0 x 2 + c 1 x + c 2 0 mod p. Εύρεση λύσης σύγκρισης (1)

XIX Διαπεριφερειακή Ολυμπιάδα για μαθητές στα Μαθηματικά και στην Κρυπτογραφία Εργασίες για την 11η τάξη Λύση του προβλήματος 1 Αρχικά, σημειώνουμε ότι αν N = pq, όπου p και q είναι πρώτοι αριθμοί, τότε ο αριθμός των φυσικών αριθμών μικρότερος από

ΕΦΑΡΜΟΣΜΕΝΗ ΑΛΓΕΒΡΑ. Μέρος I: Πεπερασμένα πεδία ή πεδία Galois. I 1 / 71 Μέρος I Πεπερασμένα ή πεδία Galois. ΕΦΑΡΜΟΣΩ ΑΛΓΕΒΡΑ. Μέρος I: Πεπερασμένα πεδία ή πεδία Galois. I 2 / 71 Υπολειμματικά πεδία modulo prime

Επίλυση μη γραμμικών εξισώσεων Δεν μπορούν πάντα να λυθούν επακριβώς αλγεβρικές ή υπερβατικές εξισώσεις Η έννοια της ακρίβειας λύσης συνεπάγεται:) τη δυνατότητα να γράψουμε έναν «ακριβή τύπο», ή μάλλον

20. Μη αναγώγιμα πολυώνυμα σε βασικά πεδία αριθμών Ural Federal University, Institute of Mathematics and Computer Science, Department of Algebra and Discrete Mathematics Θεμελιώδες Θεώρημα της Άλγεβρας Β

Διάλεξη. ΜΙΚΡΟΙ ΑΡΙΘΜΟΙ Αριθμητικό πεδίο. Αριθμητικό πεδίο είναι ένα σύνολο αριθμών στους οποίους οι αριθμητικές πράξεις είναι σωστές: πρόσθεση, αφαίρεση, πολλαπλασιασμός, διαίρεση με έναν μη μηδενικό αριθμό. Παραδείγματα αριθμητικών πεδίων:

ΔΙΑΛΕΞΗ 16 ΠΕΠΕΡΑΣΤΑ ΠΕΔΙΑ ΑΛΓΕΒΡΑΣ ΚΑΙ ΔΙΑΙΡΕΣΗ ΑΛΓΕΒΡΑ ΑΛΓΕΒΡΑ ΤΕΤΑΡΤΗΜΑΤΩΝ Θεώρημα Frobenius 1 ΠΕΠΕΡΑΣΤΑ ΠΕΔΙΑ Λήμμα 1. Εάν το πεδίο F αποτελείται από στοιχεία q, τότε κάθε στοιχείο του πεδίου F είναι μια ρίζα του πολυωνύμου

5 Πεπερασμένα πεδία 5.1 Πεπερασμένα πεδία Ορισμός 5.1. Ένας δακτύλιος R, + είναι ένα σύνολο R με δύο δυαδικές πράξεις + έτσι ώστε 1) το R, + να είναι μια αβελιανή ομάδα. 2) η πράξη είναι συνειρμική, δηλαδή (α β) γ = α

ΣΥΣΤΗΜΑ ΠΡΟΣΤΑΣΙΑΣ ΠΛΗΡΟΦΟΡΙΩΝ ΧΡΗΣΙΜΟΠΟΙΕΙ ΑΡΘΡΩΤΟ ΣΥΣΤΗΜΑ ΑΡΙΘΜΩΝ Kalmykov I.A., Naumenko D.O., Berezkina M.V., Makarova A.V., Kalmykov M.I. Ομοσπονδιακό Πανεπιστήμιο του Βορείου Καυκάσου. Ινστιτούτο

Αλγεβρικές εξισώσεις όπου Ορισμός. Η αλγεβρική είναι μια εξίσωση της μορφής 0, P () 0, μερικοί πραγματικοί αριθμοί. 0 0 Σε αυτήν την περίπτωση, η μεταβλητή ονομάζεται άγνωστη και οι αριθμοί 0 καλούνται

ΚΕΦΑΛΑΙΟ 3 ΔΑΚΤΥΛΙΟΙ ΠΟΛΥΩΝΥΜΩΝ 18. Πολυώνυμα σε μία μεταβλητή 18.1. Ορισμοί και βασικές ιδιότητες. Ένα πολυώνυμο σε μια μεταβλητή σε έναν δακτύλιο K είναι μια παράσταση f = f(x) = a 0 + a 1 x +... +

Πίνακας περιεχομένων Σύντομες θεωρητικές πληροφορίες... 3 Δυαδικό σύστημα αριθμών... 5 Οκταδικά και δεκαεξαδικά συστήματα αριθμών... 5 Μετατροπή αριθμού από ένα σύστημα αριθμών θέσης σε άλλο... 6

Εργαστηριακή εργασία 8 Υπολογισμός του μεγαλύτερου κοινού διαιρέτη για δύο αριθμούς χρησιμοποιώντας τον ευκλείδειο αλγόριθμο

Από την ιστορία των μαθηματικών Το πρώτο αρκετά ογκώδες βιβλίο στο οποίο η αριθμητική παρουσιάστηκε ανεξάρτητα από τη γεωμετρία ήταν η Εισαγωγή στην Αριθμητική (okne) του Νικομάχου.

FGOBU VPO "SibGUTI" Τμήμα Πληροφοριακών Συστημάτων Επιστημών "ΓΛΩΣΣΕΣ ΠΡΟΓΡΑΜΜΑΤΙΣΜΟΥ" "ΠΡΟΓΡΑΜΜΑΤΙΣΜΟΣ" Πρακτικό μάθημα Εργασία με δεκαδικά ψηφία Εισηγητής: Αναπληρωτής Καθηγητής Τμήματος VS, Ph.D. Πολιάκοφ

Εφαρμοσμένη Άλγεβρα 1 / 160 Εφαρμοσμένη Άλγεβρα Διαλέξεις για ομάδες 320 328 (ΙΙΙ ρεύμα) 5ο εξάμηνο 2013/2014 της χρονιάς Λέκτορας Gurov Sergey Isaevich Βοηθός Kropotov Dmitry Alexandrovich Σχολή Πληροφορικής

Λύση εξισώσεων σε ακέραιους αριθμούς Γραμμικές εξισώσεις. Μέθοδος άμεσης απαρίθμησης Παράδειγμα. Κουνέλια και φασιανοί κάθονται σε ένα κλουβί. Έχουν συνολικά 8 πόδια. Μάθετε πόσα από αυτά και άλλα είναι στο κελί. Καταγράψτε όλες τις λύσεις. Λύση.

2008 3 Πρακτικά FORA ΓΡΑΦΙΚΗ ΕΡΜΗΝΕΙΑ ΠΡΩΤΩΝ ΚΑΙ ΣΥΝΘΕΤΩΝ ΑΡΙΘΜΩΝ Kuban State University, Krasnodar Η εργασία είναι αφιερωμένη στην απόδειξη του μικρού θεωρήματος του Fermat. Προσφέρει ένα απλό

ΔΙΑΛΕΞΗ 2. Αλγόριθμοι κυκλικής δομής. Σκοπός της διάλεξης: Γνωριμία με την έννοια του αλγόριθμου κυκλικής δομής. Απόκτηση δεξιοτήτων κατασκευής αλγορίθμων για κυκλική δομή. 5. Αλγόριθμοι του κυκλικού

Math-Net.Ru All-russian mathematical portal EP Machikina, B. Ya. Ryabko, Μια γρήγορη μέθοδος για τη μετατροπή συνεχόμενων κλασμάτων σε συνηθισμένα, Diskr. Mat., 1999, τόμος 11, τεύχος 4, 152 156 DOI: http://dx.doi.org/10.4213/dm402

Συν Άλγεβρα Υπολογιστή 9. Επίλυση συστημάτων γραμμικών αλγεβρικών εξισώσεων πάνω από τον δακτύλιο ακεραίων 9.1. Παραλλαγές της μεθόδου Gauss στο πεδίο των ρητών αριθμών και πάνω από τον δακτύλιο των ακεραίων Ένα από τα πιο ευρέως

ΛΥΣΗ ΕΠΑΛΛΗΛΩΜΕΝΩΝ ΕΞΙΣΩΣΕΩΝ Δηλώστε με την τιμή κάποιας παράστασης όταν αντικαθίσταται σε αυτήν ένας ακέραιος Στη συνέχεια η εξάρτηση ενός μέλους ακολουθίας από τα μέλη της ακολουθίας F F με τιμές

Ugra Physics and Mathematics Lyceum VP Chuvakov Task C6 (The Number Theory on the Unified State Examination) Εκπαιδευτικός και Μεθοδολογικός Οδηγός Khanty-Mansiysk 0 VP Chuvakov Πρόβλημα C6 (Theory Number on the Unified State Examination): Οδηγός Σπουδών, - Khanty-Mansiy, - Khanty-Mansiy.

2.22. Βγάλτε τον κοινό παράγοντα (n είναι φυσικός αριθμός) από αγκύλες: 1) x n + 3 + x n ; 3) z 3n - z n ; 2) y n + 2 - y n - 2, n > 2; 4) 5n + 4 + 2 5n + 2-3 5n + 1. 2.23. Κάθε αριθμός εκχωρήθηκε

Διάλεξη 4 ΕΠΑΝΑΛΗΠΤΙΚΟΙ ΑΛΓΟΡΙΘΜΟΙ ΤΟ ΠΡΟΒΛΗΜΑ ΤΟΥ ΑΡΙΘΜΟΥ ΤΟΥ ΤΥΧΕΡΩΝ ΕΙΣΙΤΗΡΙΩΝ Σκεφτείτε το ακόλουθο πρόβλημα Υπάρχουν εισιτήρια με αριθμούς από 000000 έως 999999 Ένα εισιτήριο θεωρείται τυχερό εάν το άθροισμα των τριών πρώτων ψηφίων είναι

Θέμα 1-8: Μιγαδικοί αριθμοί A. Ya. Ovsyannikov Ural Federal University Institute of Mathematics and Computer Science Department of Algebra and Discrete Mathematics Algebra and Geometry for Mechanics (1 εξάμηνο)

Θέμα 1-9: Πολυώνυμα. Κατασκευή δακτυλίου πολυωνύμων. Θεωρία Διαιρετότητας. Παράγωγο A. Ya. Ovsyannikov Ural Federal University Institute of Mathematics and Computer Science Department of Algebra and Discrete

Διάλεξη: Μη αναγώγιμα και αναγώγιμα πολυώνυμα. Θεώρημα για την κατασκευή πεδίων από p n στοιχεία, όπου p είναι πρώτος αριθμός, n 2. Υπολογισμοί σε πεπερασμένα πεδία, αλγόριθμος του Ευκλείδη. Επεκτάσεις πεδίου. Πολλαπλασιαστική ομάδα

Θεωρία Galois, Διάλεξη 2: επεκτάσεις πεδίου Misha Verbitsky 25 Ιανουαρίου 2013 HSE Mathematical Faculty 1 Επεκτάσεις πεδίου ΟΡΙΣΜΟΣ: Μια επέκταση ενός πεδίου k είναι ένα πεδίο K που περιέχει το k. Η σχέση «να είναι επέκταση» συμβολίζεται

Σελίδα Σελίδα 1 από 18 Δυαδική Αριθμητική Οι αριθμοί που έχουμε συνηθίσει να χρησιμοποιούμε λέγονται δεκαδικοί και οι αριθμητικοί που χρησιμοποιούμε λέγονται και δεκαδικοί. Αυτό συμβαίνει επειδή κάθε αριθμός μπορεί να συντεθεί

Τίτλος Εισαγωγή. Βασικές έννοιες.... 4 1. Ολοκληρωμένες εξισώσεις Volterra... 5 Επιλογές εργασίας για το σπίτι.... 8 2. Επίλυση της εξίσωσης ολοκληρωτικού Volterra. 10 επιλογές για εργασίες για το σπίτι.... 11

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

0 1 2 3 4 5 6 7 8 9

θα μετατραπούν σε τιμές

0 1 2 3 4 5 6 0 1 2

Για να δηλώσετε το υπόλοιπο που προκύπτει με διαίρεση Χεπί Τ,συντομογραφία που χρησιμοποιείται συνήθως Χ(τροπ Μ),που διαβάζεται σαν "Χ modulo Μή μερικές φορές απλώς" x ενότητα m". Έτσι, το 9 (mod 7) είναι 2 επειδή το υπόλοιπο του 9 διαιρούμενο με το 7 είναι 2. Ομοίως, το 24 (mod 7) είναι 3 επειδή το 24 διαιρούμενο με το 7 δίνει ένα υπόλοιπο 3. και το 5 (mod 7) είναι ίσο με 5.

Δύο ακέραιοι αριθμοί που, όταν διαιρούνται με Τδίνουν το ίδιο υπόλοιπο ονομάζονται ισοδύναμα modulo Τ.Άρα, το 16 και το 23 είναι ισοδύναμα modulo 7, αφού 16 (mod 7) = 23 (mod 7). Πράγματι, όταν διαιρείται με το 7, τόσο η τιμή 16 όσο και η τιμή 23 δίνουν ένα υπόλοιπο 2. Για να υποδείξετε ότι η τιμή Χισοδυναμεί με στο modulo Τη συντομογραφία χρησιμοποιείται συχνά. Λοιπόν, 16 23 (mod 7).

Αφού μετατρέψουμε τις συνηθισμένες ακέραιες τιμές στο σύστημα modulo, μας μένουν μόνο οι τιμές 0, 1, 2, 3, ..., Μ- 1. Μπορούμε να εκτελέσουμε αριθμητικές πράξεις μέσα σε ένα περιορισμένο σύνολο αριθμών. για αυτό, η πράξη εκτελείται πρώτα με τον ίδιο τρόπο όπως στην παραδοσιακή αριθμητική, και στη συνέχεια η απάντηση, ας υποθέσουμε Χ,μεταφράζεται ξανά στο περιορισμένο εύρος αντικαθιστώντας το με μια τιμή Χ(τροπ Μ).Έτσι, στο modular σύστημα modulo 7, έχουμε μόνο τις τιμές 0, 1, 2, 3, 4, 5, και 6. Όταν προσθέτουμε 2 + 6, παίρνουμε την τιμή 1, αφού 2 + 6 = 8, που όταν διαιρεθεί με το 7 δίνει ένα υπόλοιπο 1. Πολλαπλασιάζοντας 2 x 6 θα προκύψει 5, αφού 2x6 = 12, και όταν διαιρεθεί με το 7, το υπόλοιπο είναι 5.

Η αριθμητική στο αρθρωτό σύστημα είναι μια παραμορφωμένη αντανάκλαση της αριθμητικής στο παραδοσιακό σύστημα. Είναι ένας προβληματισμός με την έννοια ότι αν Χ= ένα(τροπ Τ)Και στο= σι(τροπ Μ),Οτι x + ya + β(mod m). Μια παραμόρφωση σημαίνει ότι τα αθροίσματα και τα γινόμενα στα δύο συστήματα δεν είναι ίσα. Συγκεκριμένα, το γινόμενο δύο διαφορετικών ακεραίων στο αρθρωτό σύστημα μπορεί να είναι ίσο με 1, κάτι που σε καμία περίπτωση δεν είναι δυνατό στο παραδοσιακό σύστημα ακεραίων. Για παράδειγμα, σε ένα modulo συστήματος 7, έχουμε 3x5 = 1 (γιατί 3 x 5 = 15, και 15 7 είναι 1 στο υπόλοιπο).

Δύο αριθμοί που πολλαπλασιαζόμενοι δίνουν 1 ονομάζονται πολλαπλασιαστικοί αντίστροφοι ο ένας του άλλου. Στο παραδοσιακό ακέραιο σύστημα, η τιμή 3 δεν έχει πολλαπλασιαστικό αντίστροφο. Το παραδοσιακό πολλαπλασιαστικό αντίστροφο του 3, που είναι το 1/3, είναι έξω από το ακέραιο σύστημα αριθμών. Αλλά στο σύστημα ακεραίων modulo 7, η τιμή 3 έχει πολλαπλασιαστικό αντίστροφο ίσο με (όπως είδαμε) 5.

Πότε κάνει το νόημα Χυπάρχει μια πολλαπλασιαστική αντιστροφή στο modulo του συστήματος Μ?Οι μαθηματικοί λένε ότι αν ΧΚαι T -δύο θετικοί ακέραιοι τέτοιοι ώστε Χ< т Και ΧΚαι Τ coprime (αυτό σημαίνει ότι ο μόνος ακέραιος που διαιρείται χωρίς υπόλοιπο και Χ,Και Τ,ισούται με 1), τότε η τιμή Χθα υπάρξει μια πολλαπλασιαστική αντιστροφή στο modulo του αρθρωτού συστήματος Τ.Για παράδειγμα, το 6 είναι μικρότερο από το 13 και ο μόνος κοινός διαιρέτης αυτών των δύο τιμών είναι το 1. Επομένως, το 6 πρέπει να έχει πολλαπλασιαστικό αντίστροφο στο modulo του συστήματος 13. Πράγματι, το αντίστροφο είναι ο αριθμός 11, αφού 6 x 11 = 66, που όταν διαιρεθεί με το 13 δίνει το υπόλοιπο είναι 1. Άρα 6x11 = 1 (mod 13).

Το ότι ορισμένοι ακέραιοι αριθμοί έχουν πολλαπλασιαστικές αντίστροφες σε αρθρωτά συστήματα μπορεί να φαίνεται περίεργο με την πρώτη ματιά. Συγκεκριμένα, δεδομένου ότι το 6 και το 11 είναι πολλαπλασιαστικές αναστροφές στο modulo του συστήματος 13, βρίσκουμε ότι το 6 x 11 x x = xγια οποιαδήποτε αξία Χ.Πράγματι, 6x11x Χ=(6x 11) x Χ = Χ

Επιστροφή στην κρυπτογράφηση.Σημειώστε ότι εάν η τιμή Χμη αρνητικό και μικρότερο από το συντελεστή Τ,Οτι Χ(τροπ Μ)ισοδυναμεί Χ.Αυτό σημαίνει ότι κατά την εκτέλεση αριθμητικών πράξεων, τα συνήθη αποτελέσματα των οποίων βρίσκονται στην περιοχή από 0 έως Τ- 1, σε ένα αρθρωτό σύστημα θα έχουμε τα ίδια αποτελέσματα. Έτσι, αν πάρουμε μια πολύ μεγάλη τιμή της ενότητας, τότε μπορούμε να εκτελέσουμε συνηθισμένους αριθμητικούς υπολογισμούς χωρίς καν να γνωρίζουμε αν βρισκόμαστε στο παραδοσιακό αριθμητικό σύστημα ή στο αρθρωτό σύστημα. Συγκεκριμένα, δεδομένου ότι το άθροισμα όλων των τιμών στη λίστα

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

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

όπου η αξία κάθε καταχώρισης στη λίστα είναι μεγαλύτερη από το άθροισμα των τιμών που προηγούνται. Επομένως, όσον αφορά αυτή τη λίστα, το πρόβλημα του σακιδίου λύνεται εύκολα. Ας πάρουμε το module Τ,μεγαλύτερο από το άθροισμα όλων των τιμών στη λίστα και πάρτε δύο άλλες τιμές ΧΚαι y,οι οποίες είναι πολλαπλασιαστικές αναστροφές στο modular system modulo Τ.

Αν πολλαπλασιάσουμε κάθε καταχώρηση στην αρχική λίστα επί Χ,τότε έχουμε μια λίστα

από την άποψη του οποίου το πρόβλημα του σακιδίου λύνεται επίσης εύκολα. (Κάθε καταχώριση εξακολουθεί να είναι μεγαλύτερη από το άθροισμα των προηγούμενων εγγραφών.) Αλλά τώρα αντικαταστήστε όλες τις εγγραφές της νέας λίστας με τιμές που είναι τα ισοδύναμα modulo τους Τ.Συγκεκριμένα, δίνουμε την αξία , στη θέση - νόημα ένα 2 x(τροπ Τ)κτλ. Παίρνουμε μια λίστα

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

Με τη σειρά του, οποιοδήποτε άθροισμα τιμών από αυτήν τη νέα λίστα πρέπει να είναι ισοδύναμο modulo Ττο άθροισμα των αντίστοιχων τιμών της λίστας

Ας υποθέσουμε ότι μας δίνεται ένας αριθμός ίσος με το άθροισμα , και πρέπει να επιλεγεί από τη λίστα

καταχωρήσεις που αθροίζονται σε αυτήν την αξία. Επειδή

Και στοείναι το πολλαπλασιαστικό αντίστροφο Χ,τότε το ξέρουμε

Αυτό σημαίνει ότι αν πολλαπλασιάσουμε το άθροισμα των τιμών που επιλέγονται από τη λίστα

επί y,χωρίστε την εργασία σε Μγράψτε το υπόλοιπο, τότε αυτό το υπόλοιπο θα είναι ίσο με το άθροισμα των αντίστοιχων εγγραφών στην αρχική λίστα

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

Σύντομη επιλογή από τη λίστα

τιμές που αποτελούν το άθροισμα των s, χρειάζεται μόνο να υπολογίσουμε την τιμή μικρόΧ στο(mod ha), βρείτε στη λίστα

καταχωρήσεις των οποίων το άθροισμα είναι ίσο με αυτήν την τιμή και, στη συνέχεια, επιλέξτε τις αντίστοιχες τιμές στη λίστα

Εξετάστε ένα παράδειγμα στη λίστα

1 4 6 12 25 51 105 210 421 850

από την άποψη του οποίου το πρόβλημα του σακιδίου λύνεται εύκολα. Δεδομένου ότι το άθροισμα όλων των τιμών είναι 1685, η τιμή 2311 είναι αρκετά μεγάλη για να παίξει κάποιο ρόλο Τ.Επιπλέον, το 642 και το 18 είναι πολλαπλασιαστικές αντιστροφές στο σύστημα modulo 2311, επομένως θα θεωρήσουμε το 642 ως τιμή Χ,και 18 - η τιμή y.Το πρώτο μας βήμα είναι να πολλαπλασιάσουμε κάθε καταχώρηση από την προηγούμενη λίστα με το 642 και να γράψουμε τα υπόλοιπα αφού διαιρέσουμε τα γινόμενα με το 2311. Παίρνουμε τη λίστα

Ας υποθέσουμε ότι τώρα βρισκόμαστε αντιμέτωποι με το καθήκον να επιλέξουμε από αυτήν τη λίστα τιμών των οποίων το άθροισμα είναι 4507. Πολλαπλασιάζουμε το 4507 με 18, παίρνουμε την τιμή 81126, τη διαιρούμε με το 2311 και γράφουμε το υπόλοιπο ίσο με 241. Στη συνέχεια, βρίσκουμε ότι στην αρχική λίστα το άθροισμα 241 δίνει τιμές 6, 25 και 210. Δεδομένου ότι αυτές είναι οι τρίτες, πέμπτες και όγδοες εγγραφές στην αντίστοιχη λίστα, συμπεραίνουμε ότι η τρίτη, η πέμπτη και η όγδοη εγγραφές στην λίστα

642 257 1541 771 2184 388 391 782 2206 304

αθροίστε το 4507. Πράγματι, οι τιμές 1541, 2184 και 782 λύνουν το αρχικό πρόβλημα του σακιδίου.

Έτσι, μπορούμε να δημιουργήσουμε ένα σύστημα κρυπτογράφησης δημόσιου κλειδιού, όπως φαίνεται στο Σχ. 2. Αρχικά, γράφουμε τη λίστα των τιμών από τις οποίες κατασκευάζονται απλά προβλήματα σακιδίου. Στη συνέχεια επιλέξτε τιμές t, xΚαι στοέτσι ώστε Τήταν μεγαλύτερο από το άθροισμα όλων των τιμών στη λίστα και Χ στοστο σύστημα modulo Τ.Στη συνέχεια πολλαπλασιάζουμε τις τιμές της αρχικής λίστας επί Χ,χωρίστε τις εργασίες σε Τκαι γράψε τα υπόλοιπα. Η λίστα των υπολειμμάτων θα είναι το δημόσιο κλειδί κρυπτογράφησης. Οποιοσδήποτε μπορεί να κρυπτογραφήσει ένα μήνυμα με τη μορφή μιας ακολουθίας εργασιών σακιδίου με βάση αυτή τη λίστα, αλλά μόνο εμείς μπορούμε εύκολα να αποκρυπτογραφήσουμε αυτές τις τιμές. Χρειάζεται μόνο να πολλαπλασιάσουμε κάθε δεδομένο ποσό επί y,χωρίστε την εργασία σε Τκαι γράψτε το υπόλοιπο. Στη συνέχεια, βρίσκουμε γρήγορα τις τιμές από την αρχική λίστα που αθροίζονται σε αυτό το υπόλοιπο και ανακτούμε τον συνδυασμό bit που σχηματίζει το μήνυμα.

1. Επιλέγουμε τιμές στις οποίες μπορούμε εύκολα να λύσουμε το πρόβλημα του σακιδίου.

Για παράδειγμα: 2 5 8 17

2. Επιλέξτε τρεις αριθμούς t, xΚαι στο, τέτοιο που Τυπερέβη το άθροισμα των τιμών του σακιδίου και Χήταν η πολλαπλασιαστική αντιστροφή στοσε ένα modular σύστημα modulo Τ.

Για παράδειγμα: t = 37, Χ= 25, στο = 3

3. Αντικαταστήστε κάθε τιμή ΕΝΑαρχική τιμή λίστας Χα(τροπ Μ).

Εικόνα 3 - Σχεδιασμός συστήματος κρυπτογράφησης δημόσιου κλειδιού

Πρέπει να προστεθεί μια τελευταία παρατήρηση. Ένας εισβολέας θα μπορούσε να προσπαθήσει να σπάσει το σύστημα κρυπτογράφησης προσπαθώντας να μαντέψει τις τιμές t, xΚαι y,αντί να λύνει σύνθετα προβλήματα σακιδίου. Επομένως, οι αριθμοί σε ένα πραγματικό σύστημα κρυπτογράφησης πρέπει να είναι πολύ μεγαλύτεροι από τις τιμές που χρησιμοποιήσαμε στα παραδείγματα. Εάν τα προβλήματα του σακιδίου είναι μεγάλα και οι βασικές τιμές είναι μεγάλες, τότε ο χρόνος που απαιτείται για την άμεση επίλυση των προβλημάτων του σακιδίου ή για την εικασία των μυστικών κλειδιών θα είναι επίσης σημαντικός.

Ερωτήσεις ελέγχου

1. Ποια είναι η βάση της πολιτικής ασφάλειας πληροφοριών;

2. Ποια είναι η βάση για την κατασκευή ενός συστήματος ασφάλειας πληροφοριών;

3. Προσδιορίστε τις βασικές έννοιες και τους ορισμούς ενός κρυπτογραφικού αλγορίθμου;

4. Τι σημαίνει ο όρος «κρυπτογράφηση δημόσιου κλειδιού»;

5. Στην παρακάτω λίστα, βρείτε τις τιμές που αθροίζονται σε 2200.

191 691 573 337 365 730 651

Βιβλιογραφία

Κύρια λογοτεχνία

1. Πληροφορική [Ηλεκτρονικός πόρος]: διαλέξεις για το μάθημα: Μέρος 1. / Gromov Yu.Yu. [και τα λοιπά.]. – Tambov: Tambov. κατάσταση τεχν. un-t, 2007. - Λειτουργία πρόσβασης http://window.edu.ru/window_catalog/files/r56885/k_Gromov2.pdf/.

2. Ζβέρεφ, Γ.Ν. Η θεωρητική πληροφορική και τα θεμέλιά της [Ηλεκτρονική πηγή]: σχολικό βιβλίο. εγχειρίδιο για φοιτητές ανώτατων εκπαιδευτικών ιδρυμάτων: σε 2 τόμους / Γ.Ν. Ζβέρεφ. - Μ.: Fizmatliz, 2008.- Τόμ.1,2. Λειτουργία πρόσβασης http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id=2386/.

3. Kudinov, Yu.I. Βασικές αρχές της σύγχρονης πληροφορικής. [Ηλεκτρονική πηγή]: σχολικό βιβλίο. επίδομα για φοιτητές. / Yu.I. Kudinov, F.F. Πασχένκο. - M.: Lan, 2011. Λειτουργία πρόσβασης http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id=2024/.

4. Kudinov Yu.I. Εργαστήριο για τα βασικά της σύγχρονης πληροφορικής. [Ηλεκτρονική πηγή]: σχολικό βιβλίο. επίδομα για φοιτητές. / Yu.I. Kudinov, F.F. Pashchenko, A.Yu. Kelin. - M.: Lan, 2011. Λειτουργία πρόσβασης http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id=1799/.

πρόσθετη βιβλιογραφία

1. Gladkov, L.A. Γενετικοί αλγόριθμοι. [Ηλεκτρονική πηγή]: σχολικό βιβλίο. / L.A. Gladkov, V.V. Kureichik, V.M. Kureichik. - M.: Fizmatliz, 2010. Λειτουργία πρόσβασης http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id=2163/.

2. Εισαγωγή στις αριθμητικές-θεωρητικές μεθόδους κρυπτογραφίας: σχολικό βιβλίο. επίδομα για φοιτητές. [Ηλεκτρονικός πόρος] / Glukhov M.M. [και τα λοιπά.]. - M.: Lan, 2007. Λειτουργία πρόσβασης http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id=1540/.

3. Dale, N. Προγραμματισμός σε C++. [Ηλεκτρονικός πόρος] / N. Dale, C. Wims, M. Headington. - M: DMK Press, 2007. Λειτουργία πρόσβασης http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id=1219/.

4. Dogadin N.B. Αρχιτεκτονική υπολογιστών. [Ηλεκτρονική πηγή]: σχολικό βιβλίο. επίδομα για φοιτητές. / N.B. Dogadin. - Μ.: ΜΠΙΝΟΜ. Εργαστήριο Γνώσης, 2008. - Λειτουργία πρόσβασης http://window.edu.ru/window_catalog/files/r64584/Dogadin_978-5-94774-728-7/1-2-3_cB728-7.pdf/.

5. Ibe, O. Δίκτυα υπολογιστών και υπηρεσίες απομακρυσμένης πρόσβασης. [Ηλεκτρονικός πόρος] / O. Ibe. - M.: DMK Press, 2007. Λειτουργία πρόσβασης http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id=1169/.

6. Ilyushechkin, V.M. Λειτουργικά συστήματα [Ηλεκτρονικός πόρος]: σχολικό βιβλίο. επίδομα για φοιτητές. / V.M. Ilyushechkin. - Μ.: ΜΠΙΝΟΜ. Εργαστήριο Γνώσης, 2009. - Λειτουργία πρόσβασης http://window.edu.ru/window_catalog/files/r65308/Ilyushechkin_978-5-94774-963-2/1-2-3_cB963-2.pdf/.

7. Kaufman, V.Sh. Γλώσσες προγραμματισμού. Έννοιες και αρχές. [Ηλεκτρονικός πόρος] / V.Sh. Κάουφμαν. - M: DMK Press, 2010. Λειτουργία πρόσβασης http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id=1270/.

8. Kuryachiy, G.V. Λειτουργικό σύστημα Linux. [Ηλεκτρονικός πόρος]: διαλέξεις για το μάθημα / G.V. Kuryachiy, K.A. Μασλίνσκι. - M: DMK Press, 2010. Λειτουργία πρόσβασης http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id=1202/.

9. Marchenkov, S.S. αναδρομικές συναρτήσεις. [Ηλεκτρονικός πόρος]: br. / Σ.Σ. Marchenkov. - M.: Fizmatliz, 2007. Λειτουργία πρόσβασης http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id=2260/.

10. Ναύτης, Δ.Σ. Θεωρία αλγορίθμων [Ηλεκτρονικός πόρος]: σχολικό βιβλίο. / Δ.Σ. Matros, G.B. Ποντνεμπέσοβα. - Μ.: ΜΠΙΝΟΜ. Εργαστήριο Γνώσης, 2008. Λειτουργία πρόσβασης http://window.edu.ru/window_catalog/files/r64609/Matros_978-5-94774-226-8/1-2-3_cB226-8.pdf/.

11. Ostreykovsky, V.A. Επιστήμη των υπολογιστών. Θεωρία και πράξη. [Ηλεκτρονική πηγή]: σχολικό βιβλίο. επίδομα για φοιτητές. / V.A. Ostreykovsky, I.V. Πολιάκοφ. - M.: Oniks, 2008. - Λειτουργία πρόσβασης http://www.knigafund.ru/books/42473/.

12. Parondzhanov, V.D. Φιλικοί αλγόριθμοι κατανοητοί σε όλους. [Ηλεκτρονικός πόρος] / V.D. Παροντζάνοφ. - M.: DMK Press, 2010. Λειτουργία πρόσβασης http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id=1083/.

13. Petrov, Α.Α. Ασφάλεια του υπολογιστή. Κρυπτογραφικές μέθοδοι προστασίας. [Ηλεκτρονικός πόρος] / Α.Α. Πετρόφ. - M.: DMK Press, 2008. Λειτουργία πρόσβασης http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id=3027/.

14. Petrushin, V.N. Ευαισθησία πληροφοριών αλγορίθμων υπολογιστών. [Ηλεκτρονική πηγή]: σχολικό βιβλίο. επίδομα για φοιτητές. / V.N. Petrushin, M.V. Ουλιάνοφ. - M.: Fizmatliz, 2007. Λειτουργία πρόσβασης http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id=2275/.

15. Potopakhin, V.I. Η τέχνη του αλγορίθμου. [Ηλεκτρονικός πόρος] / V.I. Ποτοπάχιν. M: DMK Press, 2011. Λειτουργία πρόσβασης http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id=1269/.

16. Ουλιάνοφ, Μ.Β. Αλγόριθμοι υπολογιστών αποδοτικών πόρων. Ανάπτυξη και ανάλυση. [Ηλεκτρονική πηγή]: σχολικό βιβλίο. επίδομα για φοιτητές. / M.V. Ουλιάνοφ. - M.: Fizmatliz, 2008. Λειτουργία πρόσβασης http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id=2354/.

17. Chekmarev Yu.V. Τοπικά δίκτυα υπολογιστών. [Ηλεκτρονική πηγή]: σχολικό βιβλίο. επίδομα για φοιτητές. / Yu.V. Τσεκμάρεφ. - M.: DMK Press, 2010. Λειτουργία πρόσβασης http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id=1147/.

18. Chekmarev Yu.V. Υπολογιστικά συστήματα, δίκτυα και τηλεπικοινωνίες. [Ηλεκτρονική πηγή]: σχολικό βιβλίο. επίδομα για φοιτητές. / Yu.V. Τσεκμάρεφ. - M.: DMK Press, 2010. Λειτουργία πρόσβασης http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id=1146/.

19. Shangin, V.F. Προστασία πληροφοριών υπολογιστή. [Ηλεκτρονικός πόρος] / V.F. Shangin. - M.: DMK Press, 2010. Λειτουργία πρόσβασης http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id=1122/.

20. Yudovich, V.I. Μαθηματικά μοντέλα φυσικών επιστημών. [Ηλεκτρονικός πόρος]: διαλέξεις για το μάθημα. / V.I. Yudovich. - M.: Lan, 2011. Λειτουργία πρόσβασης http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id=689/.

21. Yashin, V.M. Επιστήμη των υπολογιστών. [Ηλεκτρονική πηγή]: σχολικό βιβλίο. / V.M. Ο Γιασίν. - M.: INFRA - M, 2008. - Τρόπος πρόσβασης http://www.knigafund.ru/books/19100/

Περιοδικά

1. Περιοδικό CNews

2. Περιοδικό CIO

3. Περιοδικό "ITSpets"

4. Περιοδικό «ComputerPress»

Αρθρωτή αριθμητική

Στην κρυπτογραφία και την κρυπτανάλυση, είναι συχνά απαραίτητο να προσθέσουμε δύο ακολουθίες αριθμών ή να αφαιρέσουμε τη μία από την άλλη. Αυτή η πρόσθεση και αφαίρεση εκτελείται, κατά κανόνα, όχι με τη βοήθεια συνηθισμένων αριθμητικών πράξεων, αλλά με τη βοήθεια πράξεων που ονομάζονται αρθρωτή αριθμητική. Στην αρθρωτή αριθμητική, η πρόσθεση, η αφαίρεση εκτελείται σε σχέση με κάποιο σταθερό αριθμό, ο οποίος ονομάζεται συντελεστής. Οι τυπικές τιμές modulo που χρησιμοποιούνται στην κρυπτογραφία είναι 2, 10 και 26. Όποιο συντελεστή και αν πάρουμε, όλοι οι αριθμοί που εμφανίζονται αντικαθίστανται από το υπόλοιπο της διαίρεσης αυτών των αριθμών. Αν το υπόλοιπο είναι αρνητικός αριθμός, τότε προστίθεται η τιμή του συντελεστή ώστε το υπόλοιπο να γίνει μη αρνητικό. Για παράδειγμα, εάν χρησιμοποιείται modulo 26, τότε οι μόνοι δυνατοί αριθμοί είναι μεταξύ 0 και 25. Έτσι, εάν προσθέσετε το 17 στο 19, το αποτέλεσμα είναι 10, επειδή το 17 + 19 = 36, και το 36, όταν διαιρείται με το 26, φεύγει υπόλοιπο 10. Για να υποδείξετε ότι χρησιμοποιείται η ενότητα 26, γίνεται αποδεκτή η σημείωση:

17+19=10(mod26).

Εάν αφαιρέσετε το 19 από το 17, τότε το αποτέλεσμα (-2) είναι αρνητικό, οπότε προστίθεται 26 σε αυτό και το αποτέλεσμα είναι 24.

Όταν προσθέτουμε το modulo 26 δύο αριθμητικές ακολουθίες, οι διατυπωμένοι κανόνες πρόσθεσης εφαρμόζονται σε κάθε ζεύγος αριθμών χωριστά, χωρίς "μεταφορά" στο επόμενο ζεύγος. Ομοίως, κατά την αφαίρεση του modulo 26 μιας ακολουθίας αριθμών από μια άλλη, οι κανόνες αφαίρεσης εφαρμόζονται σε κάθε ζεύγος αριθμών ξεχωριστά, χωρίς να «δανείζονται» από το επόμενο ζεύγος.

Παράδειγμα 1.1

Προσθέστε το modulo 26 τις ακολουθίες 15 11 23 06 11 και 17 04 14 19 23

και το αποτέλεσμα είναι 06 15 11 25 08

Εάν ο συντελεστής είναι 10, τότε χρησιμοποιούνται αριθμοί από το 0 έως το 9. με την ενότητα 2 - μόνο 0 και 1

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

0 1 0 1 - 0 1 0 1

0 1 1 2 0 -1 1 0

0 1 1 0 0 1 1 0 (mod 2) και στις δύο περιπτώσεις.

Αρθρωτή πρόσθεση και αφαίρεση γραμμάτων

Ας δούμε ένα παράδειγμα αρθρωτής πρόσθεσης και αφαίρεσης που εφαρμόζεται στα γράμματα.

Προσθέστε ΣΗΜΕΡΑ στο ΠΟΤΕ modulo 26

Αφαιρέστε ΣΗΜΕΡΑ από το modulo ΠΟΤΕ 26

Λύση