Erweiterter Euklid < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
Hallo an alle!
Ich bin zur Zeit dabei das "modular Inverse" programmiertechnisch umzusetzen.
Auf wikipedia habe ich dazu den Artikel gefunden:
http://en.wikipedia.org/wiki/Modular_inverse
Schaue ich mir dazu eine Beispielimplementierung an (http://en.wikipedia.org/wiki/Modular_inverse#Implementation_in_Python) so sehe ich da nur die Berechnung des erweiterten euklidschen Algorithmus.
Was mir unklar ist: Ich berechne doch damit
ax+by = ggT(a,b)
a und b ist gegeben, berechnet wird x, y und der ggT(a,b).
Das modular Inverse ist:
[mm] a^{-1} \equiv [/mm] x (mod m) bzw.
a * x [mm] \equiv [/mm] 1 (mod m)
Und nun setze ich in die Berechnung des erweiterten Euklid, in den ich normalerweise a und b hineingebe, a und m hinein um das modular Inverse zu bekommen?
Was mich nämlich stutzig macht, ist, dass ich die Aufgabe habe, das modular Inverse zu implementieren und als nächsten Punkt den erw. Euklid. Algo. Das wäre doch dann aber eins?
Und wie bereits erwähnt, wenn ich mir die Beispielimplementierung anschaue (Link siehe oben), so wird nut der extGCD() aufgerufen und danach (das kann ich nicht nachvollziehen) ein return gemacht bei dem b und x und D ins Spiel kommt.
Nehme ich das Beispiel aus wikipedia:
3*x [mm] \equiv [/mm] 1 (mod 11)
so kommt als Lösung für x = 4 heraus.
Wenn ich 3 und 11 in meine Berechnung des erw. Euklids gebe, so erhalte ich
4*3 + -1*11 = 1
Also 4, -1 und als ggT 1
Und das modular Inverse ist dann immer der Wert der als Erstes steht? Also kann es niemald der zweite Wert sein, in diesem Fall die -1?
Aber dann ist mir weiterhin diese Zeile unklar:
return b == 1 and ((x+D)%D) or None
Kann das mit dem Text aus wikipedia zusammenhängen: ?
"The multiplicative inverse of a modulo m exists iff a and m are coprime (i.e., if gcd(a, m) = 1). If the modular multiplicative inverse of a modulo m exists, the operation of division by a modulo m can be defined as multiplying by the inverse, which is in essence the same concept as division in the set of reals."
Und: Kann das modular Inverse negativ sein?
Mein Beispiel mit
6*x [mm] \equiv [/mm] (1 mod 15)
Da kommt bei mir -2 heraus.
Führe ich eine schon in Java implementierte Methode aus mit den Werten, so erscheint eine Fehlermeldung, dass die Zahl nicht invertierbar sei.
Ich hoffe ihr könnt etwas Licht in die Sache bringen.
Danke im voraus, Gruß PHANTOMIAS
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:26 Mo 08.06.2009 | | Autor: | statler |
Hi!
> Kann das mit dem Text aus wikipedia zusammenhängen: ?
> "The multiplicative inverse of a modulo m exists iff a and
> m are coprime (i.e., if gcd(a, m) = 1). If the modular
> multiplicative inverse of a modulo m exists, the operation
> of division by a modulo m can be defined as multiplying by
> the inverse, which is in essence the same concept as
> division in the set of reals."
>
> Und: Kann das modular Inverse negativ sein?
Klar kann es das! Ich kann es ja um den Modul abändern.
> Mein Beispiel mit
> 6*x [mm]\equiv[/mm] (1 mod 15)
> Da kommt bei mir -2 heraus.
Aber hier ist doch a = 6 und m = 15, die sind nicht teilerfremd, also gibt es kein Inverses.
> Führe ich eine schon in Java implementierte Methode aus mit
> den Werten, so erscheint eine Fehlermeldung, dass die Zahl
> nicht invertierbar sei.
Ebend!
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
Vielen Dank für die schnelle Antwort!
Ich habe bei dem Beispiel:
mit a = 6 und m = 15 nur meine bestehende extGCD Funktion verwendet und das Ergebnis ist dann
-2*6 + 1*15 = 3
was ja auch stimmt. Der ggT ist 3 und die Linearkombination ist auch korrekt.
Aber hier ist doch a = 6 und m = 15, die sind nicht teilerfremd, also gibt es kein Inverses.
Aber schaue ich mir die Beispielimplementierung an, so wird doch nur der Euklid angewandt und danach noch eine Zeile (frägt diese Zeile denn die teilerfremdheit ab?):
def invMOD(N,D):
x,y,b = extGCD(N,D);
return b == 1 and ((x+D)%D) or None
Aber im Prinzip ist das ja auch mein Problem: also ist der erweiterte Euklid nicht alles was ich machen muss um das modular Inverse zu berechnen?
Update: Also muss ggT = 1 sein, das ist der einzige Fall den ich prüfen muss?
Und in meinem Beispiel von 6 und 15 ist der ggT = 3, deswegen gibt es kein modular Inverses?
Bedeutet: erw. Euklid anwenden, der x-Wert ist mein Inverses wenn ggT =1 ist, andernfalls gibt es keins. Ist das richtig so?
Deswgen wohl die Abfrage auf b == 1.
Aber was macht das dann noch:
((x+D)%D) ?
Gruß PHANTOMIAS
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 02:08 Di 09.06.2009 | | Autor: | felixf |
Hallo!
> Vielen Dank für die schnelle Antwort!
>
> Ich habe bei dem Beispiel:
> mit a = 6 und m = 15 nur meine bestehende extGCD Funktion
> verwendet und das Ergebnis ist dann
> -2*6 + 1*15 = 3
> was ja auch stimmt. Der ggT ist 3 und die
> Linearkombination ist auch korrekt.
Ja.
> Aber hier ist doch a = 6 und m = 15, die sind nicht
> teilerfremd, also gibt es kein Inverses.
> Aber schaue ich mir die Beispielimplementierung an, so
> wird doch nur der Euklid angewandt und danach noch eine
> Zeile (frägt diese Zeile denn die teilerfremdheit ab?):
Ja: ist $b = 1$, also der ggT 1, so wird $x$ zurueckgeliefert, andernfalls `None'. Der zweite Fall (`None') bedeutet, dass es kein Inverse gibt.
> def invMOD(N,D):
> x,y,b = extGCD(N,D);
> return b == 1 and ((x+D)%D) or None
>
> Aber im Prinzip ist das ja auch mein Problem: also ist der
> erweiterte Euklid nicht alles was ich machen muss um das
> modular Inverse zu berechnen?
>
> Update: Also muss ggT = 1 sein, das ist der einzige Fall
> den ich prüfen muss?
Ja.
> Und in meinem Beispiel von 6 und 15 ist der ggT = 3,
> deswegen gibt es kein modular Inverses?
Ja.
> Bedeutet: erw. Euklid anwenden, der x-Wert ist mein
> Inverses wenn ggT =1 ist, andernfalls gibt es keins. Ist
> das richtig so?
Ja. (Wenn der ggT -1 ist gibt es auch ein Inverses, aber normalerweise liefert der Algorithmus einen positiven ggT zurueck wenn man da nicht rumpfuscht.)
> Deswgen wohl die Abfrage auf b == 1.
> Aber was macht das dann noch:
> ((x+D)%D) ?
Das sorgt dafuer dass $x$ die Ungleichung $0 [mm] \le [/mm] x < D$ erfuellt. Kann man auch weglassen bzw. durch die Abfrage x < 0 ? x + D : x ersetzen.
LG Felix
|
|
|
|
