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)".

:#Determine the prime factorization and totient of the order of the group :

$varphi(p)=\; p\_1cdot\; p\_2\; 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 :

(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.

Complexity

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

=References=
#S. Pohlig and M. Hellman. " [http://www.dtc.umn.edu/~odlyzko/doc/arch/discrete.logs.pdf An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance] ", "IEEE Transactions on Information Theory" 24 (1978), pp. 106–110.