Pohlig-Hellman-Algorithmus
Der Pohlig-Hellman-Algorithmus wurde nach den Mathematikern Stephen Pohlig und Martin Hellman benannt. Gelegentlich ist dieser Algorithmus in der Literatur auch unter dem Namen Silver-Pohlig-Hellman-Algorithmus zu finden. Mit dem Pohlig-Hellman-Algorithmus kann der diskrete Logarithmus in einer zyklischen Gruppe berechnet werden.
Die Relevanz dieses Verfahrens liegt darin, dass der Rechenaufwand nicht von der Gruppenordnung, sondern vom größten Faktor der Gruppenordnung abhängt. Nachteilig ist, dass für dieses Verfahren eine Primfaktorzerlegung der Gruppenordnung bekannt sein muss. Solch eine Primfaktorzerlegung ist im Allgemeinen jedoch nur sehr schwer zu bestimmen.
Mathematischer Hintergrund
BearbeitenSei eine zyklische Gruppe der Ordnung , wobei die Faktorisierung von bekannt und der größte Faktor von sei. Der diskrete Logarithmus in der Gruppe lässt sich dann mittels Silver-Pohlig-Hellman in statt Operationen berechnen. Dies geschieht in drei Schritten:
- Reduktion des Problems der Gruppe in zyklische Gruppen deren Ordnung ist, wobei ein Teiler von ist (die sich später hieraus ergebende Lösung ist eindeutig nach dem Chinesischen Restsatz).
- Reduktion von Gruppen mit Primzahlpotenzordnung in Gruppen mit Primordnung
- Zusammensetzen des Ergebnisses mittels des Chinesischen Restsatzes.
Der Algorithmus
BearbeitenSei die zyklische Gruppe der Ordnung , ein Erzeuger von und . Weiter sei die Primfaktorzerlegung von .
Der Algorithmus ist nun in zwei Schritten angegeben. Zuerst folgt eine Version für Gruppen, deren Ordnung einer Primzahlpotenz entspricht. Dieser kann im Folgenden als Unteralgorithmus im Allgemeinen Pohlig-Hellman verwendet werden.
Prime-Power-Pohlig-Hellman
BearbeitenDie Gruppenordnung sei , wobei eine Primzahl ist. Zur Bestimmung des diskreten Logarithmus in den Untergruppen wird der Babystep-Giantstep-Algorithmus von Shanks verwendet.
- Eingabe:
- Ausgabe Der diskrete Logarithmus
- Shanks( ),
- for to do
- Shanks( )
- return
In diesem Algorithmus wird verwendet, dass der diskrete Logarithmus in der folgenden Form geschrieben werden kann: . Aufgrund der vorgenommenen Beschränkungen ist diese Darstellung eindeutig.
Allgemeiner Pohlig-Hellman
Bearbeiten- Eingabe:
- Ausgabe Der diskrete Logarithmus
- for to do
- Prime-Power-Pohlig-Hellman( )
- Berechne für mit dem Chinesischen Restsatz .
- return .
- for to do
Referenzen
Bearbeiten- S. Pohlig and M. Hellman. "An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance", IEEE Trans. Information Theory 24, 1978, Seiten. 106-110.
- V. Shoup. "A Computational Introduction to Number Theory and Algebra", Cambridge University Press, 2007, http://shoup.net/ntb/, Seite 325ff.