Pohlig–Hellman algorithm


In group theory, the Pohlig–Hellman algorithm, sometimes credited as the Silver–Pohlig–Hellman algorithm, is a special-purpose algorithm for computing discrete logarithms in a finite abelian group whose order is a smooth integer.
The algorithm was introduced by Roland Silver, but first published by Stephen Pohlig and Martin Hellman.

Groups of prime-power order

As an important special case, which is used as a subroutine in the general algorithm, the Pohlig–Hellman algorithm applies to groups whose order is a prime power. The basic idea of this algorithm is to iteratively compute the -adic digits of the logarithm by repeatedly "shifting out" all but one unknown digit in the exponent, and computing that digit by elementary methods.
Assuming is much smaller than, the algorithm computes discrete logarithms in time complexity Big O notation|, far better than the baby-step giant-step algorithm's Big O notation|.

The general algorithm

In this section, we present the general case of the Pohlig–Hellman algorithm. The core ingredients are the algorithm from the previous section and the Chinese remainder theorem.
The correctness of this algorithm can be verified via the classification of finite abelian groups: Raising and to the power of can be understood as the projection to the factor group of order.

Complexity

The worst-case input for the Pohlig–Hellman algorithm is a group of prime order: In that case, it degrades to the baby-step giant-step algorithm, hence the worst-case time complexity is. However, it is much more efficient if the order is smooth: Specifically, if is the prime factorization of, then the algorithm's complexity is group operations.