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.

Sei ${\displaystyle G}$ eine zyklische Gruppe der Ordnung ${\displaystyle n}$, wobei die Faktorisierung von ${\displaystyle n}$ bekannt und ${\displaystyle p}$ der größte Faktor von ${\displaystyle n}$ sei. Der diskrete Logarithmus in der Gruppe ${\displaystyle G}$ lässt sich dann mittels Silver-Pohlig-Hellman in ${\displaystyle {\mathcal {O}}({\sqrt {p}})}$ statt ${\displaystyle {\mathcal {O}}({\sqrt {n}})}$ Operationen berechnen. Dies geschieht in drei Schritten:

1. Reduktion des Problems der Gruppe ${\displaystyle G}$ in zyklische Gruppen ${\displaystyle G_{p^{k}}}$ deren Ordnung ${\displaystyle p^{k}}$ ist, wobei ${\displaystyle p^{k}}$ ein Teiler von ${\displaystyle n}$ ist (die sich später hieraus ergebende Lösung ist eindeutig nach dem Chinesischen Restsatz).
2. Reduktion von Gruppen mit Primzahlpotenzordnung in Gruppen mit Primordnung
3. Zusammensetzen des Ergebnisses mittels des Chinesischen Restsatzes.

Sei ${\displaystyle G}$ die zyklische Gruppe der Ordnung ${\displaystyle n}$, ${\displaystyle g}$ ein Erzeuger von ${\displaystyle G}$ und ${\displaystyle h\in \left\langle g\right\rangle }$. Weiter sei ${\displaystyle n=\Pi _{i=1}^{k}q_{i}^{e_{i}}}$ die Primfaktorzerlegung von ${\displaystyle n}$.

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.

Die Gruppenordnung sei ${\displaystyle n=q^{e}}$, wobei ${\displaystyle q}$ eine Primzahl ist. Zur Bestimmung des diskreten Logarithmus in den Untergruppen wird der Babystep-Giantstep-Algorithmus von Shanks verwendet.

Eingabe: ${\displaystyle g,q,e,h}$

Ausgabe Der diskrete Logarithmus ${\displaystyle a:=\log _{g}(h)}$

1. ${\displaystyle u\leftarrow h^{q^{e-1}},{\hat {g}}\leftarrow g^{q^{e-1}}}$
2. ${\displaystyle a_{0}\leftarrow }$ Shanks(${\displaystyle {\hat {g}},q,u}$), ${\displaystyle a\leftarrow a_{0},{\hat {h}}\leftarrow h\cdot g^{-a_{0}}}$
3. for ${\displaystyle i\leftarrow 1}$ to ${\displaystyle e-1}$ do
   1. ${\displaystyle u\leftarrow {\hat {h}}^{q^{e-i-1}}}$
   2. ${\displaystyle a_{i}\leftarrow }$Shanks(${\displaystyle {\hat {g}},q,u}$)
   3. ${\displaystyle a\leftarrow a+a_{i}q^{i},{\hat {h}}\leftarrow {\hat {h}}\cdot g^{-a_{i}q^{i}}}$
4. return ${\displaystyle a}$

In diesem Algorithmus wird verwendet, dass der diskrete Logarithmus ${\displaystyle a=\log _{g}(h)}$ in der folgenden Form geschrieben werden kann: ${\displaystyle \log _{g}(h)=a=\sum _{i=0}^{e-1}a_{i}q^{i},0\leq a_{i}\leq q-1,i=0,\dots e-1}$. Aufgrund der vorgenommenen Beschränkungen ist diese Darstellung eindeutig.

Eingabe: ${\displaystyle g,h,n,q_{1},\dots ,q_{k},e_{1}\dots e_{k}}$

Ausgabe Der diskrete Logarithmus ${\displaystyle a:=\log _{g}(h)}$

1. for ${\displaystyle i\leftarrow 1}$ to ${\displaystyle k}$ do
   1. ${\displaystyle n_{i}\leftarrow n/q_{i}^{e_{i}},g_{i}\leftarrow g^{n_{i}},h_{i}\leftarrow h^{n_{i}}}$
   2. ${\displaystyle c_{i}\leftarrow }$ Prime-Power-Pohlig-Hellman(${\displaystyle g_{i},q_{i},e_{i},h_{i}}$)
2. Berechne für ${\displaystyle i=1,\dots k}$ mit dem Chinesischen Restsatz ${\displaystyle c=c_{i}\mod q_{i}^{e_{i}}}$.
3. return ${\displaystyle c}$.

1. 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.
2. V. Shoup. "A Computational Introduction to Number Theory and Algebra", Cambridge University Press, 2007, http://shoup.net/ntb/, Seite 325ff.