Lösung - Euklidischer Algorithmus 01
Problem 1:
Finde mit Hilfe des erweiterten euklidischen Algorithmus die modulare Inverse von 15 mod 26
Schritt 1: ggT(15,26)
26 = 1 * 15 + 11
15 = 1 * 11 + 4
11 = 2 * 4 + 3
4 = 1 * 3 + 1
3 = 3 * 1 + 0
ggT(15,26) = 1
Schritt2 - Umkehrung
1 = 4 - 1 * 3
3 = 11 - 2 * 4
4 = 15 - 1 * 11
11 = 26 - 1 * 15
Schritt 3 - Substitution
1 = 4 - (11 - 2 * 4) ... substituiere 3 durch (11 - 2 * 4) 1 = 3 * 4 - 11 1 = 3 * (15 - 1 * 11) - 11 ... substituiere 4 durch (15 - 1 * 11) 1 = 3 * 15 - 4 * 11 1 = 3 * 15 - 4 * (26 - 1 * 15) ... substituiere 11 durch (26 - 1 * 15) 1 = 7 * 15 - 4 * 26
Die modulare Inverse von 15 mod 26 lautet 7.
Problem 2:
Finde mit Hilfe des erweiterten euklidischen Algorithmus die modulare Inverse von 5 mod 48
Schritt 1: ggT(5,48)
48 = 9 * 5 + 3
5 = 1 * 3 + 2
3 = 1 * 2 + 1
2 = 2 * 1 + 0
Schritt 2 - Umkehrung
1 = 3 - 2
2 = 5 - 3
3 = 48 - 9 * 5
Schritt 3 - Substitution
1 = 3 - (5 - 3) 1 = 2 * 3 - 5 1 = 2 * (48 - 9 * 5) - 5 1 = 2 * 48 - 19 * 5
Die modulare Inverse von 5 mod 48 lautet -19 + 48 = 29 (positiver Wert gesucht).
Probe mit DERIVE
