Studienarbeit

- Matthias Dohn -

Darstellung, Implementierung und Effizienzuntersuchung
der Algorithmen von J. Pollard
zur Lösung des „Diskreten Logarithmus Problems“
a^x mod p = ß

August 2002

Inhaltsverzeichnis

1. Aufgabenstellung

2. Rho-Methode
a. Darstellung des Algorithmus
b. Implementierung
c. Beispielrechnung
d. Zeitmessungen

3. Baby -Step-Giant-Step
a. Darstellung des Algorithmus
b. Implementierung
c. Beispielrechnung
d. Zeitmessungen

4. Kangaroo-Methode
a. Darstellung des Algorithmus
b. Implementierung
c. Beispielrechnung
d. Zeitmessungen

5. Programmbeschreibung
a. Anforderungen
b. Bedienung

6. Quellenverzeichnis
a. Bibliography
b. Webliography

Aufgabenstellung:

Ausgehend von dem Artikel im Journal of Cryptology “Kangaroos, Monopoly and Discrete Logrithms“ sollen die Algorithmen von J.M. Pollard dargestellt, implementiert und hinsichtlich ihrer Effizienz untersucht werden.

Einführung:

Das diskrete Logarithmus Problem ist ein oft diskutiertes mathematische Problem welches in der Kryptographie am bedeutendsten ist. Die Schwierigkeit das Lösen der Formel a^x mod p = ß wird zur Zeit bei Public-Key Verfahren angewandt.
Zahlreiche Mathematiker, unter anderem Edlyn Teske und Andreas Stein beschäftigen sich mit der Verbesserung von Methoden zur Lösung des DLP. Je nachdem welche Informationen bekannt sind kommen andere effiziente Algorithmen zur Anwendung.

J.M. Pollard hat in dem Artikel im Journal of Cryptology mehrere Methoden zur Lösung des Diskreten Logarithmus Problems vorgestellt. Die Rho-Methode wurde kurz erwähnt und wird im folgenden Kapitel vorgestellt. Im darauf folgenden Kapitel wird die Baby-Step-Giant-Step-Methode erläutert und anschliessend die „Lambda-Method for catching kangaroos“. 

Matthias Dohn Studienarbeit August 2002

2. Rho-Methode
a) Darstellung:

Die Rho-Methode zur Berechnung des Diskreten Logarithmus wurde 1978 von J.M.Pollard entdeckt und ist ein zufallsbasierter Algorithmus, nicht zu verwechseln mit dem gleichbenannten Rho-Algorithmus zur Primfaktorzerlegung. 

[...]