Frage: Pohlig-Hellman Algorithmus

flos
Neuling
Neuling
Beiträge: 5
Registriert: 26. Dez 2012 12:12

Frage: Pohlig-Hellman Algorithmus

Beitrag von flos » 10. Feb 2013 10:04

Hallo allerseits,

ich versuche gerade die Vorgehensweise beim o.g. Algorithmus zu verstehen und
anhand des Beispiels im Buch nachzuvollziehen. Leider gelingt mir das nicht vollständig.
Auch andere Beispiele im Internet weichen von der Vorgehensweise im Buch ab, weshalb
diese nur zur weitere Verwirrung führen.

Folgende Problematik.
Nachdem ich p-1 in seine Primfaktoren mit Exponent zerlegt habe, stelle ich die erste Kongruenz
für den ersten Primfaktor 2 auf (in diesem Fall 500^x(2) = 913 mod 2017.
Im Anschluss schreibe ich x(2) in der Form x0 + x1*2 + x2*2² + .....
Um jetzt die Koeffizienten zu bestimmen muss ich weitere Kongruenzen aufstellen.
Und hier komme ich nicht weiter....
1. Wie bestimme ich die weiteren Kongruenzen
2. Wie bestimme ich alpha und wozu benötige ich das.

Für den Primfaktor 3 wird die Kongruenz 294^x0(3) = 294 mod 2017 aufgestellt. Wie erhalte ich diese?

Fragen über Fragen. Über Hilfe wäre ich echt dankbar. Die Teilzeitarbeit raubte mir die Übungsgruppe...

Beste Grüße

ISTler
Erstie
Erstie
Beiträge: 22
Registriert: 3. Mai 2010 12:23

Re: Frage: Pohlig-Hellman Algorithmus

Beitrag von ISTler » 10. Feb 2013 16:21

Alpha ist in der Aufgabestellung gegeben. Gesucht ist x mit \(\gamma^x \equiv \alpha\; mod\; n\). Damit sollte klar sein wofür man es braucht.

Wenn du das Problem auf Primzahlpotenzordnung reduzierst erhälst du:
\(\gamma_{3}^{x(3)} \equiv \alpha_3\; mod\; n\)
\(576^{x(3)} \equiv 1933\; mod\; 2017\)
\(576^{x_0(3)+x_1(3)*3} \equiv 1933\; mod\; 2017\) Potenzieren mit 3^1
\(576^{3*x_0(3)+x_1(3)*9} \equiv 1933^3\; mod\; 2017\)
Da wir ja Primzahlpotenzordnung haben ergbt sich:
\(576^{3*x_0(3)+x_1(3)*9} \equiv 576^{3*x_0(3)} \equiv 1933^3\; mod\; 2017\)
\(294^{x_0(3)} \equiv 294\; mod\; 2017\)
Und das hat nurnoch Primzahlordnung.

Ich hoffe dir damit helfen zu können.

flos
Neuling
Neuling
Beiträge: 5
Registriert: 26. Dez 2012 12:12

Re: Frage: Pohlig-Hellman Algorithmus

Beitrag von flos » 10. Feb 2013 22:34

Super vielen Dank das beantwortet 1a den 2. Teil meiner Frage.
Wärst du so freundlich noch den 1. Teil ebenso ausführlich zu beschreiben,
also wie ich die Kongruenzen für x(2) so aufstelle, dass sich die Koeffizienten x0(2), x1(2), x2(2), ... bestimmen lassen?
Vor allem mit was ich wann potenzieren muss wäre sehr hilfreich zu wissen.
In dem Beispiel aus dem Buch kommen die Kongruenzen scheinbar irgendwoher :-)
Welche Relevanz haben die den die Zwischenschritte für alpha(1), alpha(2), etc.

Beste Grüße das hilft mir sehr!

dunlaith
Erstie
Erstie
Beiträge: 12
Registriert: 3. Jan 2013 15:46

Re: Frage: Pohlig-Hellman Algorithmus

Beitrag von dunlaith » 11. Feb 2013 00:22

Hi,

also ich gehe mal davon aus, dass du bei \(x(2)=x_{0}(2)+2x_{1}(2)+2^2x_{2}(2)+2^3x_{3}(2)+2^4x_{4}(2)\) bist.
Danach musst du eigentlich nur noch in die Formel (11.6), also \((\gamma^{p^{e-1}})^x_{i} =\alpha_{i}^{p-i-1}, 0 \leq i \leq e-1\) einsetzen.

Beispiel:
i = 0: \((500^{2^4})^{x_{0}} = 913^{2^4} \rightarrow 2016^{x_{0}} \equiv 1 \bmod 2017 \rightarrow x_{0} = 0\)
i = 1: \((500^{2^4})^{x_{1}} = 913^{2^3} \rightarrow 2016^{x_{1}} \equiv 2016 \bmod 2017 \rightarrow x_{1} = 1\)

ab dem Schritt beginnen die \(\alpha\)-Werte sich zu verändern. Warum wird dann gleich auch klar:
im Buch wird \(\alpha_{i} = \alpha\gamma^{-(x_{0}+x_{1}p+\dots+x_{i-1}p^{i-1})}\) gesetzt (über (11.6) steht: "Bezeichne das Gruppenelement auf der rechten Seite mit \(\alpha_{i}\)).
Für \(\alpha_{2}\) gilt damit \(\alpha_{2}= \alpha\gamma^{-(x_{0}+x_{1}p)}=913*500^{-(0+1*2)} = 913*500^{-1*2}\). Das Inverse von 500 ist 593 und \(913*593^2 \equiv 1579 \pmod {2017}\).

Danach fährt man fort mit:
i = 2: \((500^{2^4})^{x_{2}} = 1579^{2^2} \rightarrow 2016^{x_{2}} \equiv 2016 \bmod 2017 \rightarrow x_{2} = 1\)

Ich hoffe, ich konnte helfen - habe es eben selbst erst geschafft, mir das da herzuleiten :)
Viele Grüße

flos
Neuling
Neuling
Beiträge: 5
Registriert: 26. Dez 2012 12:12

Re: Frage: Pohlig-Hellman Algorithmus

Beitrag von flos » 11. Feb 2013 09:57

Super verstanden danke!

dees
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 6. Mär 2011 14:01

Re: Frage: Pohlig-Hellman Algorithmus

Beitrag von dees » 11. Feb 2013 19:42

Mal eine andere Frage, in Übung 12 P1 b) wird x(2) über die Reduzierung auf Primzahlordnung berechnet und x(13) wird über den Babystep-Giantstep-Algorithmus gelöst. Gibt es irgendeinen Indiz wann ich besser den Babystep-Giantstep benutze und wann ich weiter reduziere?

ISTler
Erstie
Erstie
Beiträge: 22
Registriert: 3. Mai 2010 12:23

Re: Frage: Pohlig-Hellman Algorithmus

Beitrag von ISTler » 12. Feb 2013 00:43

Da e(13)=1, kannst du das Problem nicht weiter reduzieren. Primzahlpotenzordnung ist in diesem Fall gleich Primzahlordnung.

Antworten

Zurück zu „Archiv“