Pohlig-Hellman-Algorithmus
aus Wikipedia, der freien Enzyklopädie
Der Silver-Pohlig-Hellman-Algorithmus wurde nach den Mathematikern Leon Silver, Stephen Pohlig und Martin Hellman benannt. Er ist eine Methode zur Reduktion des Rechenaufwandes beim Berechnen diskreter Logarithmen.
Sei G eine zyklische Gruppe der Ordnung n, wobei die Faktorisierung von n bekannt und p der größte Faktor von n sei. Der diskrete Logarithmus in der Gruppe G lässt sich dann mittels Silver-Pohlig-Hellman in 
statt 
Operationen berechnen. Dies geschieht in drei Schritten:
- Reduktion des Problems von der Gruppe G in zyklische Gruppen
deren Ordnung pk ist, wobei pk ein Teiler von n ist - Reduktion von Gruppen mit Primzahlpotenzordnung in Gruppen mit Primordnung
- Zusammensetzen des Ergebnisses mittels des Chinesischen Restsatzes.
