Pohlig–Hellman algorithm

In mathematics, the Pohlig–Hellman algorithm is an algorithm for the computation of discrete logarithms in a multiplicative group whose order is a smooth integer. The algorithm is based on the Chinese remainder theorem.

The algorithm was discovered by Roland Silver, but first published by Stephen Pohlig and Martin Hellman (independent of Silver).

We will explain the algorithm in terms of the group formed by taking all the elements of Z_p which are coprime to p, and leave it to the advanced reader to extend the algorithm to other groups by using Lagrange's Theorem.

Input Integers p, g, e.

Output Integer x, such that e ≡ g^x (mod p).

1. Determine the prime factorization of the order of the group (the totient in this case)  :
   ${\displaystyle \varphi (p)=p_{1}\cdot p_{2}\cdot \ldots \cdot p_{n}}$
2. From the remainder theorem we know that x = a₁ p₁ + b₁. We now find the value of b₁ for which the following equation holds using a fast algorithm such as Baby-step giant-step :
   ${\displaystyle {\begin{matrix}e^{\varphi (p)/p_{1}}&\equiv &(g^{x})^{\varphi (p)/p_{1}}{\pmod {p}}\\&\equiv &(g^{\varphi (p)})^{a_{1}}g^{b_{1}\varphi (p)/p_{1}}{\pmod {p}}\\&\equiv &(g^{\varphi (p)/p_{1}})^{b_{1}}{\pmod {p}}\end{matrix}}}$ (using Euler's theorem)
   Note that if ${\displaystyle g^{\varphi (p)/p_{1}}\equiv 1{\pmod {p}}}$ then the order of g is less than φ(p) and ${\displaystyle e^{\varphi (p)/p_{1}}\mod p}$ must be 1 for a solution to exist. In this case there will be more than one solution for x less than φ(p), but since we are not looking for the whole set, we can require that b₁=0.
   
   The same operation is now performed for p₂ up to p_n.
   
   A minor modification is needed where a prime number is repeated. Suppose we are seeing p_i for the k+1-th time. Then we already know c_i in the equation x = a_i p_i^k+1 + b_i p_i^k+c_i, and we find b_i the same way as before.
3. We end up with enough simultaneous congruences so that x can be solved using the Chinese remainder theorem.

Complexity

The time complexity of the Pohlig–Hellman algorithm is ${\displaystyle O({\sqrt {n}})}$  for a group of order n, but it is more efficient if the order is smooth.

References

1. S. Pohlig and M. Hellman. "An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance", IEEE Transactions on Information Theory 24 (1978), pp. 106–110.