Pohlig-Hellman algorithm

From Wikipedia, the free encyclopedia

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 and runs in polynomial time.

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.

Input Integers p, g, e.

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

Use Euler's totient function to determine the prime factorization of the order of the group :
$\varphi(p)= p_0\cdot p_1 \cdot \ldots \cdot p_n$
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 :
$\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 $g^{\varphi(p)/p_1} \equiv 1 \pmod{p}$ then the order of g is less than φ(p) and $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.
We end up with enough simultaneous congruences so that x can be solved using the Chinese remainder theorem.