Lösung - Euklidischer Algorithmus 02Problem 1: I: 26 1 0 II: 15 0 1 I - II = III III: 11 1 -1 II - III = IV IV: 4 -1 2 III - 2*IV = V V: 3 3 -5 IV - V = VI VI: 1 -4 7 1 = -4*26 + 7*15 Die modulare Inverse von 15 mod 26 lautet 7 (15.7 mod 26 = 1). Problem 2: I: 48 1 0 II: 5 0 1 I - 9*II = III III: 3 1 -9 II - III = IV IV: 2 -1 10 III - IV = V V: 1 2 -19 1 = 2*48 - 19*5 Die modulare Inverse von 5 mod 48 lautet -19 + 48 = 29 (positiver Wert gesucht, daher -19 + 48 = 29, 5.29 mod 48 = 1) |