Pohlig–Hellman algorithm

From Wikipedia, the free encyclopedia
  (Redirected from Pohlig-Hellman algorithm)
Jump to: navigation, search
Pohlig Hellman Algorithm
Steps of the Pohlig-Hellman algorithm.

In group 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 finite abelian 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).

Groups of prime-power order[edit]

As an important special case, which is used as a subroutine in the general algorithm (see below), 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.

(Note that for readability, the algorithm is stated for cyclic groups — in general, must be replaced by the subgroup generated by , which is always cyclic.)

Input. A cyclic group of order with generator and an element .
Output. The unique integer such that .
  1. Initialize
  2. Compute . By Lagrange's theorem, this element has order .
  3. For all , do:
    1. Compute . By construction, the order of this element must divide , hence .
    2. Using the baby-step giant-step algorithm, compute such that .
    3. Set .
  4. Return .

The general algorithm[edit]

In this section, we present the general case of the Pohlig-Hellman algorithm. The core ingredients are the algorithm from the previous section (to compute a logarithm modulo each prime power in the group order) and the Chinese remainder theorem (to combine these to a logarithm in the full group).

(Again, we assume the group to be cyclic, with the understanding that a non-cyclic group must be replaced by the subgroup generated by the logarithm's base element.)

Input. A cyclic group of order with generator , an element , and a prime factorization .
Output. The unique integer such that .
  1. For each , do:
    1. Compute . By Lagrange's theorem, this element has order .
    2. Compute . By construction, .
    3. Using the algorithm above in the group , compute such that .
  2. Solve the simultaneous congruence
    The Chinese remainder theorem guarantees there exists a unique solution .
  3. Return .

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[edit]

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.[2]

Notes[edit]

  1. ^ Mollin 2006, pg. 344
  2. ^ Menezes, et. al 1997, pg. 108

References[edit]