Pohlig-Hellman algorithm

The Pohlig-Hellman algorithm was named after the mathematicians Stephen Pohlig and Martin Hellman . Occasionally this algorithm can also be found in the literature under the name Silver-Pohlig-Hellman algorithm . With the Pohlig-Hellman algorithm, the discrete logarithm can be calculated in a cyclic group.

The relevance of this method is that the computational effort does not depend on the group order, but on the largest factor in the group order. The disadvantage is that a prime factorization of the group order must be known for this method. However, such a prime factorization is generally very difficult to determine.

Math background

Let be a cyclic group of order , where the factorization of is known and the largest factor of is. The discrete logarithm in the group can then be calculated using Silver-Pohlig-Hellman in instead of operations. This is done in three steps: ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle G}$ ${\displaystyle {\mathcal {O}}({\sqrt {p}})}$ ${\displaystyle {\mathcal {O}}({\sqrt {n}})}$

1. Reduction of the problem of the group into cyclic groups whose order is, where is a divisor of (the solution that results from this later is clearly according to the Chinese remainder theorem ). ${\displaystyle G}$ ${\displaystyle G_{p^{k}}}$ ${\displaystyle p^{k}}$ ${\displaystyle p^{k}}$ ${\displaystyle n}$
2. Reduction of groups with prime power order in groups with prime order
3. Compound the result using the Chinese remainder of the sentence .

The algorithm

Let be the cyclic group of order , a generator of and . Next is the prime factorization of . ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle g}$ ${\displaystyle G}$ ${\displaystyle h\in \left\langle g\right\rangle }$ ${\displaystyle n=\Pi _{i=1}^{k}q_{i}^{e_{i}}}$ ${\displaystyle n}$

The algorithm is now given in two steps. First there is a version for groups, the order of which corresponds to a prime power. This can be used in the following as a sub-algorithm in general Pohlig-Hellman.

Prime-Power-Pohlig-Hellman

Let the group order be , where is a prime number. Shanks' Babystep-Giantstep algorithm is used to determine the discrete logarithm in the subgroups . ${\displaystyle n=q^{e}}$ ${\displaystyle q}$

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

Output The discrete logarithm ${\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 to do ${\displaystyle i\leftarrow 1}$ ${\displaystyle e-1}$
   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 this algorithm is used, that the discrete logarithm can be written in the following form: . Due to the restrictions made, this representation is clear. ${\displaystyle a=\log _{g}(h)}$ ${\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}$

General Pohlig-Hellman

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

Output The discrete logarithm ${\displaystyle a:=\log _{g}(h)}$

1. for to do ${\displaystyle i\leftarrow 1}$ ${\displaystyle k}$
   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. Calculate for with the Chinese remainder theorem . ${\displaystyle i=1,\dots k}$ ${\displaystyle c=c_{i}\mod q_{i}^{e_{i}}}$
3. return . ${\displaystyle c}$

credentials

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