Pohlig-Hellman-Algorithmus

Der Pohlig-Hellman-Algorithmus wurde nach den Mathematikern 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.