Erweiterter Euklidischer Algorithmus?
Sei p =12619 (das ist eine Primzahl) und [x]= [810]p. Berechnen Sie das multiplikativ Inverse [x]^(-1) von [x] in Zp mit dem erweiterten Euklidischen Algorithmus.
Geben Sie Ihr Ergebnis in der Form [y] mit 0 kleiner-gleich y kleiner-gleich p-1 an. Überprüfen Sie Ihre Lösung.
Das ist die Aufgabe, die wir lösen sollen. Ich habe den erweiterten Euklidischen Algorithmus gegoogelt und soweit auch verstanden allerdings verstehe ich trtz nicht die Aufgabe und was ich machen soll...und was ist das Inverse und wie berechnet man es? Über Hilfe oder eine Lösung zum Nachvollziehen würde ich mich freuen, danke
1 Antwort
[y]ₚ ist zu [x]ₚ invers, wenn [x]ₚ ⋅ [y]ₚ = [1]ₚ, das heißt x⋅y ≡ 1 (mod p).
Bei dem erweiterten euklidischen Algorithmus werden zu zwei teilerfremden ganzen Zahlen p und x Koeffizienten k, y ∈ ℤ berechnet, sodass k⋅p + y⋅x = 1, was bedeutet, dass k⋅p + y⋅x = 1 bedeutet, dass x⋅y ≡ 1 (mod p). Beim euklidischen Algorithmus kommt genau dann am Ende 1 raus, wenn die Zahlen teilerfremd sind. Das ist hier der Fall, weil p eine Primzahl ist. Sonst gibt es kein Inverses.
Man führt den Algorithmus also für x und p durch und am Ende ist der für x berechnete Koeffizient die gesuchte Zahl.
Ich dachte du hättest den erweiterten euklidischen Algo verstanden. Er muss nur mit x und p gerechnet und die Lösung ist dann der Koeffizient von x.
Weißt du wie man den normalen euklidischen Algorithmus rechnet?
Beispiel mit x =7 und p = 11:
Euklidischer Algorithmus:
11 - 7 = 4
7 - 4 = 3
4 - 3 = 1
Hiermit wurde eine Darstellung von 1 durch x und p gefunden:
1 = 4 - 3 = (11 - 7) - (7 - 4) = (11 - 7) - (7 - (11 - 7)) = 2 ⋅ 11 - 3 ⋅ 7
Also wäre [-3]₁₁ = [8]₁₁ das Inverse zu [7]₁₁.
Und wie rechne ich das aus?