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

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 $\mathcal O(\sqrt p)$ statt $\mathcal{O}(\sqrt n)$ Operationen berechnen. Dies geschieht in drei Schritten:

1. Reduktion des Problems der Gruppe G in zyklische Gruppen $G_{p^k}$ deren Ordnung p^k ist, wobei p^k ein Teiler von 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.

Der Algorithmus

Sei G die zyklische Gruppe der Ordnung n, g ein Generator von G und $h \in \left\langle g \right\rangle$. Weiter sei $n=\Pi_{i=1}^{k}q_i^{e_i}$ die Primfaktorzerlegung von 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.

Prime-Power-Pohlig-Hellman

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

Eingabe: g,q,e,h

Ausgabe Der diskrete Logarithmus a: = log _g(h)

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

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

Allgemeiner Pohlig-Hellman

Eingabe: $g, h, n, q_1, \dots, q_k, e_1 \dots e_k$

Ausgabe Der diskrete Logarithmus a: = log _g(h)

1. for $i\leftarrow 1$ to k do
   1. $n_i \leftarrow n/q_i^{e_i}, g_i\leftarrow g^{n_i}, h_i \leftarrow h^{n_i}$
   2. $c_i \leftarrow$ Prime-Power-Pohlig-Hellman(g_i,q_i,e_i,h_i)
2. Berechne für $i=1,\dots k$ mit dem Chinesischen Restsatz $c=c_i \mod q_i^{e_i}$.
3. return c.

Referenzen

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.