Μέγιστος κοινός διαιρέτης ΜΚΔ δύο θετικών ακεραίων α ‘και β λέγεται ο μεγαλύτερος ακέραιος Δ που διαιρεί και τους δύο α και β και συμβολίζεται με (α, β).
Η αναζήτηση του μέγιστου κοινού διαιρέτη δεν είναι εύκολη και ο ταχύτερος αλγόριθμος που χρησιμοποιείται είναι ο Ευκλείδειος.
Βασίζεται στο θεώρημα ότι αν α, β, δ και υ θετικοί ακέραιοι και β=αxδ+υ τότε (α,β)=(α,υ).
Παράδειγμα εφαρμογής του για (1210, 176)
1210=176x6+154 176=154x1+22 154=22x7+0 (1210,176)=22
Αυτό όμως που είναι ακόμα πιο σημαντικό και αξιοποιείται στον εντοπισμό του αντίστροφου α mod n είναι ο εκτεταμένος Ευκλείδειος αλγόριθμος που βασίζεται στο θεώρημα ότι ο (α,β) = αχ + βψ. Δηλαδή ο ΜΚΔ των αριθμών α και β μπορεί να γραφεί ως γραμμικός συνδυασμός τους με συντελεστές δυο άλλους ακεραίους το χ και ψ.
Στο παράδειγμα 22=176x7-1210x1
Ο αλγόριθμος είναι χρήσιμος για τον προσδιορισμό του αντίστροφου (12,25)=1 και 1=12x23-11x25. Άρα 23 = 12-1 mod 25
ΚΡΥΠΤΟΓΡΑΦΙΑ Σινάτκας Ι.
Η αναζήτηση του μέγιστου κοινού διαιρέτη δεν είναι εύκολη και ο ταχύτερος αλγόριθμος που χρησιμοποιείται είναι ο Ευκλείδειος.
Βασίζεται στο θεώρημα ότι αν α, β, δ και υ θετικοί ακέραιοι και β=αxδ+υ τότε (α,β)=(α,υ).
Παράδειγμα εφαρμογής του για (1210, 176)
1210=176x6+154 176=154x1+22 154=22x7+0 (1210,176)=22
Αυτό όμως που είναι ακόμα πιο σημαντικό και αξιοποιείται στον εντοπισμό του αντίστροφου α mod n είναι ο εκτεταμένος Ευκλείδειος αλγόριθμος που βασίζεται στο θεώρημα ότι ο (α,β) = αχ + βψ. Δηλαδή ο ΜΚΔ των αριθμών α και β μπορεί να γραφεί ως γραμμικός συνδυασμός τους με συντελεστές δυο άλλους ακεραίους το χ και ψ.
Στο παράδειγμα 22=176x7-1210x1
Ο αλγόριθμος είναι χρήσιμος για τον προσδιορισμό του αντίστροφου (12,25)=1 και 1=12x23-11x25. Άρα 23 = 12-1 mod 25
ΚΡΥΠΤΟΓΡΑΦΙΑ Σινάτκας Ι.
by: Πληροφορική Online
Πληροφορική Online Updated at: 2:11 μ.μ.