Θυμίζω ότι δύο αριθμοί a και p λέγονται σχετικά πρώτοι αν δεν έχουν κανέναν κοινό διαιρέτη και συμβολίζονται (a,p)=1. Αν οι αριθμοί a και p είναι πρώτοι αριθμοί τότε είναι και σχετικά πρώτοι. Αν ο ένας τους είναι πρώτος και ο άλλος σύνθετος, αρκεί ο πρώτος να μην είναι διαιρέτης του σύνθετου. Τέλος αν και οι δύο είναι σύνθετοι δεν πρέπει στην ανάλυσή τους σε όρους πρώτων παραγόντων, να έχουν κανένα κοινό όρο.
Έστω λοιπόν ότι ο p είναι πρώτος τότε για κάθε θετικό ακέραιο a με (a,p)=1 ισχύει ότι ap-1≡1mod p από όπου προκύπτει το πολύ ενδιαφέρον πόρισμα ap≡a mod p και κατ’ επέκταση το a●ap-2≡1 mod p που σημαίνει ότι ο αντίστροφος το a κατά p είναι ο ap-2. Παράδειγμα (8,13)=1 το υπόλοιπο της διαίρεσης 813-1=812=68719476736 με το 13 είναι 1, ο αντίστροφος του 8 κατά 13 είναι 813-2=811=8589934592 δηλαδή το 5.
.jpg)
Οι σχετικά πρώτοι ακέραιοι του n, που είναι και μικρότεροι του δίνονται από τη συνάρτηση Euler φ(η)
Παράδειγμα οι μικρότεροι σχετικά πρώτοι του 1.764.381.125 είναι σύμφωνα με τη φ(η) 1.764.381.125(1-1/5)(1-1/13)(1-1/17)=1.596.725·4·12·16= =1.226.284.800
Το επόμενο δίνει τον αντίστροφο κατά n του a μέσω της φ(n). Ισχύει ότι aφ(n)≡1 mod n.. Θυμίζουμε ότι ο αντίστροφος του a κατά n υπάρχει μόνο αν (a,n)=1. Επομένως αν ο n είναι πρώτος τότε ο αντίστροφος του a κατά n είναι ο aφ(n)-1.
Στα προηγούμενα βρέθηκε ότι ο αντίστροφος του 8 κατά 13 είναι ο 5. Το φ(13)=13(1-1/13)=12, είναι οι (1,2,3,4,5,6,7,8,9,10,11 και 12). Ο αντίστροφος του 8 κατά 13 λοιπόν είναι 812-1=8589934592 ότι και στο προηγούμενο.
Αν a<p και ο p είναι πρώτος αριθμός, θα χαρακτηρίζεται ο a ως τετραγωνικό υπόλοιπο mod p αν x2≡a mod p για κάποιο x. Παράδειγμα το 4 είναι τετραγωνικό υπόλοιπο κατά 13 γιατί υπάρχουν οι αριθμοί 2,11<13 για τους οποίους (22 mod 13)=4 και (112 mod 13)=4 επίσης. Αν βρεθεί ο ένας από τους δυο x τότε ο άλλος είναι ο αντίθετός του (-x) κατά p.
Η αναζήτηση τετραγωνικών υπολοίπων δεν είναι εύκολη διαδικασία αν στη σχέση x2≡a mod n ο n είναι κατάλληλος σύνθετος αριθμός που προκύπτει από το γινόμενο δύο μεγάλων πρώτων q, p. Η γνώση των q και p αποτελεί κλειδί παρά την γνωστοποίηση του n
ΚΡΥΠΤΟΓΡΑΦΙΑ Σινάτκας Ι.
Έστω λοιπόν ότι ο p είναι πρώτος τότε για κάθε θετικό ακέραιο a με (a,p)=1 ισχύει ότι ap-1≡1mod p από όπου προκύπτει το πολύ ενδιαφέρον πόρισμα ap≡a mod p και κατ’ επέκταση το a●ap-2≡1 mod p που σημαίνει ότι ο αντίστροφος το a κατά p είναι ο ap-2. Παράδειγμα (8,13)=1 το υπόλοιπο της διαίρεσης 813-1=812=68719476736 με το 13 είναι 1, ο αντίστροφος του 8 κατά 13 είναι 813-2=811=8589934592 δηλαδή το 5.
Οι σχετικά πρώτοι ακέραιοι του n, που είναι και μικρότεροι του δίνονται από τη συνάρτηση Euler φ(η)Παράδειγμα οι μικρότεροι σχετικά πρώτοι του 1.764.381.125 είναι σύμφωνα με τη φ(η) 1.764.381.125(1-1/5)(1-1/13)(1-1/17)=1.596.725·4·12·16= =1.226.284.800
Το επόμενο δίνει τον αντίστροφο κατά n του a μέσω της φ(n). Ισχύει ότι aφ(n)≡1 mod n.. Θυμίζουμε ότι ο αντίστροφος του a κατά n υπάρχει μόνο αν (a,n)=1. Επομένως αν ο n είναι πρώτος τότε ο αντίστροφος του a κατά n είναι ο aφ(n)-1.
Στα προηγούμενα βρέθηκε ότι ο αντίστροφος του 8 κατά 13 είναι ο 5. Το φ(13)=13(1-1/13)=12, είναι οι (1,2,3,4,5,6,7,8,9,10,11 και 12). Ο αντίστροφος του 8 κατά 13 λοιπόν είναι 812-1=8589934592 ότι και στο προηγούμενο.
Αν a<p και ο p είναι πρώτος αριθμός, θα χαρακτηρίζεται ο a ως τετραγωνικό υπόλοιπο mod p αν x2≡a mod p για κάποιο x. Παράδειγμα το 4 είναι τετραγωνικό υπόλοιπο κατά 13 γιατί υπάρχουν οι αριθμοί 2,11<13 για τους οποίους (22 mod 13)=4 και (112 mod 13)=4 επίσης. Αν βρεθεί ο ένας από τους δυο x τότε ο άλλος είναι ο αντίθετός του (-x) κατά p.
Η αναζήτηση τετραγωνικών υπολοίπων δεν είναι εύκολη διαδικασία αν στη σχέση x2≡a mod n ο n είναι κατάλληλος σύνθετος αριθμός που προκύπτει από το γινόμενο δύο μεγάλων πρώτων q, p. Η γνώση των q και p αποτελεί κλειδί παρά την γνωστοποίηση του n
ΚΡΥΠΤΟΓΡΑΦΙΑ Σινάτκας Ι.
by: Πληροφορική Online
Πληροφορική Online Updated at: 7:49 π.μ.