Θα υπολογίσουμε τον αντίστροφο του 109 mod 251.
Εφαρμόζοντας τον γενικευμένο Ευκλείδειο αλγόριθμο έχουμε διαδοχικά:
251=109x2 + 33 109=33x3 + 10 33=10x3 + 3 10=3x3 + 1
Συμπέρασμα (109,251)=1 συνεπώς οι 109 και 251 είναι σχετικά πρώτοι άρα υπάρχει ο αντίστροφος του 109 mod 251.
Διατρέχοντας αντίστροφα τον αλγόριθμο του Ευκλείδη έχουμε
1=10-3x3=10-(33-10x3)x3=10x10-33x3=(109-33x3)x10-33x3=
=10x109-33x33=10x109-33x(251-109x2)=76x109-33x251
Ο συντελεστής του 109 είναι ο αντίστροφός του κατά mod 251.
Με τα στοιχεία αυτά η εξίσωση 7x+12 = 3 mod 17 λύνεται ως εξής :
7x = -9 mod 17 είναι 7x = 8 mod 17 ή x = 7-1· 7x = 7-1 · 8 mod 17 ή
x =5 • 8 mod 17 = 40 mod 17 = 6
Δοκιμάζοντας τη λύση στην εξίσωση έχουμε 7 • 6 + 12 = 54 =3 «17 + 3
ΚΡΥΠΤΟΓΡΑΦΙΑ Σινάτκας Ι.
251=109x2 + 33 109=33x3 + 10 33=10x3 + 3 10=3x3 + 1
Συμπέρασμα (109,251)=1 συνεπώς οι 109 και 251 είναι σχετικά πρώτοι άρα υπάρχει ο αντίστροφος του 109 mod 251.
Διατρέχοντας αντίστροφα τον αλγόριθμο του Ευκλείδη έχουμε
1=10-3x3=10-(33-10x3)x3=10x10-33x3=(109-33x3)x10-33x3=
=10x109-33x33=10x109-33x(251-109x2)=76x109-33x251
Ο συντελεστής του 109 είναι ο αντίστροφός του κατά mod 251.
Με τα στοιχεία αυτά η εξίσωση 7x+12 = 3 mod 17 λύνεται ως εξής :
7x = -9 mod 17 είναι 7x = 8 mod 17 ή x = 7-1· 7x = 7-1 · 8 mod 17 ή
x =5 • 8 mod 17 = 40 mod 17 = 6
Δοκιμάζοντας τη λύση στην εξίσωση έχουμε 7 • 6 + 12 = 54 =3 «17 + 3
ΚΡΥΠΤΟΓΡΑΦΙΑ Σινάτκας Ι.
by: Πληροφορική Online
Πληροφορική Online Updated at: 2:14 μ.μ.