Pohlig–Hellman algorithm

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In number theory, the Pohlig–Hellman algorithm sometimes credited as the Silver–Pohlig–Hellman algorithm[1] is a special-purpose algorithm for computing discrete logarithms in a multiplicative group whose order is a smooth integer.

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

We will explain the algorithm as it applies to the group Z*p consisting of all the elements of Zp 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 An Integer x, such that egx (mod p) (if one exists).
  1. Determine the prime factorization of the order of the group  :
    \varphi(p)= p_1\cdot p_2 \cdots p_n
    (All the pi are considered small since the group order is smooth.)
  2. From the Chinese remainder theorem it will be sufficient to determine the values of x modulo each prime power dividing the group order. Suppose for illustration that p1 divides this order but p12 does not. Then we need to determine x mod p1, that is, we need to know the ending coefficient b1 in the base-p1 expansion of x, i.e. in the expansion x = a1 p1 + b1. We can find the value of b1 by examining all the possible values between 0 and p1-1. (We may also use a faster algorithm such as baby-step giant-step when the order of the group is prime.[2]) The key behind the examination is that:
    
\begin{align}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{align}

    (using Euler's theorem). With everything else now known, we may try each value of b1 to see which makes the equation be true. If g^{\varphi(p)/p_1} \not\equiv 1 \pmod{p}, then there is exactly one b1, and that b1 is the value of x modulo p1. (An exception arises if g^{\varphi(p)/p_1} \equiv 1 \pmod{p} since then the order of g is less than φ(p). The conclusion in this case depends on the value of e^{\varphi(p)/p_1} \mod p on the left: if this quantity is not 1, then no solution x exists; if instead this quantity is also equal to 1, there will be more than one solution for x less than φ(p), but since we are attempting to return only one solution x, we may use b1=0.)
  3. The same operation is now performed for p2 through pn.
    A minor modification is needed where a prime number is repeated. Suppose we are seeing pi for the (k + 1)st time. Then we already know ci in the equation x = ai pik+1 + bi pik + ci, and we find either bi or ci the same way as before, depending on whether g^{\varphi(p)/p_i} \equiv 1 \pmod{p}.
  4. With all the bi known, we have enough simultaneous congruences to determine x using the Chinese remainder theorem.

Complexity[edit]

The worst-case 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. Specifically, if \prod_i p_i^{e_i} is the prime factorization of n, then the complexity can be stated as O\left(\sum_i {e_i(\log n+\sqrt p_i)}\right).[3]

Notes[edit]

References[edit]