Pohlig-Hellman-Algorithmus zum Berechnen diskreter Logarithmen

Question

Ich arbeite der Pohlig-Hellman-Algorithmus auf Codierung, aber ich habe Probleme die Schritte im Algorithmus verstehen basierend auf der Definition des Algorithmus.

Going durch das Wiki des Algorithmus :

Ich weiß, dass der erste Teil 1) ist der wichtigste Faktor von p-1 zu berechnen -. Das ist in Ordnung

Ich bin aber nicht sicher, was ich in den Schritten tun müssen, 2), wo Sie die Co-efficents berechnen:

Let x2 = c0 + c1(2). 
125(180/2) = 12590 1 mod (181) so c0 = 0.
125(180/4) = 12545 1 mod (181) so c1 = 0.
Thus, x2 = 0 + 0 = 0.

und 3) legt die coefficents zusammen und in dem chinesischen Restsatz lösen.

Kann jemand Hilfe bei der Erklärung dieses in einfachen Englisch (i) - oder Pseudo-Code. Ich mag die Lösung selbst offensichtlich Code, aber ich kann nicht mehr Fortschritte machen, wenn ich nicht den Algorithmus zu verstehen.

Hinweis: Ich habe viel von der Suche nach diesem getan, und ich las S. Pohlig und M. Hellman (1978). „Ein verbesserter Algorithmus zur Berechnung Logarithmen über GF (p) und seine Cryptographic Bedeutung, aber es ist immer noch nicht wirklich für mich einen Sinn.

Vielen Dank im Voraus

Update: wie q (125) bleibt konstant in diesem Beispiel kommen .

Wo, wie in diesem Beispiel erscheint wie er ein neues q jeweils Zeit .

Um genauer zu sein, ich verstehe nicht, wie die folgenden berechnet wird: Nun teilen 7531 durch einen ^ c0 zu erhalten 7531(a^-2) = 6735 mod p.

Answer 1

Beginnen wir mit der Hauptidee hinter Pohlig-Hellman. Nehmen wir an, wir y, g und p gegeben sind und dass wir wollen x finden, so dass

  

y == g ^x (mod p).

(Ich verwende == eine Äquivalenzbeziehung bezeichnen). Zur Vereinfachung der Dinge, ich gehe davon aus, dass die Ordnung von g p-1, dh die kleinsten positiven k mit 1 == g ^k (mod p) k = p-1.

Eine ineffiziente Methode x zu finden, wäre einfach zu versuchen, alle Werte im Bereich von 1 .. p-1. Etwas besser ist die „Baby-Schritt Riesenschritt“ Methode, die O erfordert ( p ^0.5 ) arithmetische Operationen. Beide Methoden sind ziemlich langsam für große p. Pohlig-Hellman ist eine deutliche Verbesserung, wenn p-1 viele Faktoren hat. D. h davon ausgehen, dass

  

p-1 = n r

Was dann Pohlig und Hellman vorschlagen, ist die Gleichung zu lösen

  

y ⁿ == (g ⁿ ) ^z   (Mod p).

Wenn wir Logarithmen zur Basis g auf beiden Seiten nehmen, dies ist das gleiche wie

  

n log _g (y) == log _g (y ⁿ ) == nz (mod p-1).

n geteilt werden kann, so dass

  

log _g (y) == z (mod r).

Daher x == z (mod r).

Dies ist eine Verbesserung, da wir nur einen Bereich von 0 .. r-1 für eine Lösung von z suchen müssen. Und wieder „Baby-Schritt Riesenschritt“ kann verwendet werden, um die Suche nach z zu verbessern. Offensichtlich ist dies einmal tun, ist keine vollständige Lösung vor. D. h man hat den Algorithmus, der oben für jeden Primfaktor r p-1 und dann zu wiederholen, den chinesischen Restsatz zu verwenden x aus den Teillösungen zu finden. Dies funktioniert gut, wenn p-1 ist quadratisch frei.

Wenn p-1 durch eine Antriebsleistung teilbar ist dann eine similiar Idee verwendet werden. Zum Beispiel nehmen wir an, dass die p-1 = m q ^k . Im ersten Schritt berechnen wir z, so daß x == z (mod q), wie oben gezeigt. Als nächstes wollen wir diese zu einer Lösung x == z verlängern‘(mod q ² ). Z.B. wenn p-1 = m q ² dann bedeutet dies, dass wir z‘finden, so dass

  

y ^M == (g ^M ) ^{z '} (mod p).

Da wir bereits, dass z wissen '== z (mod q), z' in der Menge sein muss {z, z + q, z + 2Q, ..., z + (q-1) q}. Auch hier konnten wir entweder eine erschöpfende Suche nach z‘tun oder der Suche mit‚Baby-Schritt Riesenschritt‘verbessern. Dieser Schritt ist für jeden Exponenten von q wiederholt wird, ist dies aus dem Wissen, x mod q ⁱ wir iterativ derive x mod q ^{i + 1} .

Answer 2

Ich bin Codierung es mich jetzt nach oben (JAVA). Ich bin mit Pollard-Rho die kleinen Primfaktoren von p-1 zu finden. Dann mit Pohlig-Hellman einen DSA privaten Schlüssel zu lösen. y = g ^ x. Ich bin mit dem gleichen Problem ..

UPDATE: "Um genauer zu sein, ich verstehe nicht, wie die folgenden berechnet wird:. Jetzt 7531 durch eine ^ c0 teilen zu bekommen 7531 (a ^ -2) = 6735 mod p"

Wenn Sie die modInverse eines ^ c0 finden es sinnvoll, wird

Viele Grüße