In
group theory
In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups.
The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field ...
, the Pohlig–Hellman algorithm, sometimes credited as the Silver–Pohlig–Hellman algorithm,
[ Mollin 2006, pg. 344] is a special-purpose
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
for computing
discrete logarithm
In mathematics, for given real numbers ''a'' and ''b'', the logarithm log''b'' ''a'' is a number ''x'' such that . Analogously, in any group ''G'', powers ''b'k'' can be defined for all integers ''k'', and the discrete logarithm log''b' ...
s in a
finite abelian group
In mathematics, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written. That is, the group operation is commu ...
whose order is a
smooth integer.
The algorithm was introduced by Roland Silver, but first published by
Stephen Pohlig
Stephen Pohlig (1953-April 14, 2017) was an electrical engineer who worked in the MIT Lincoln Laboratory. As a graduate student of Martin Hellman's at Stanford University in the mid-1970s, he helped develop the underlying concepts of Diffie-Hellm ...
and
Martin Hellman
Martin Edward Hellman (born October 2, 1945) is an American cryptologist and mathematician, best known for his involvement with public key cryptography in cooperation with Whitfield Diffie and Ralph Merkle. Hellman is a longtime contributor to th ...
(independent of Silver).
Groups of prime-power order
As an important special case, which is used as a subroutine in the general algorithm (see below), the Pohlig–Hellman algorithm applies to
groups
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic ide ...
whose order is a
prime power
In mathematics, a prime power is a positive integer which is a positive integer power of a single prime number.
For example: , and are prime powers, while
, and are not.
The sequence of prime powers begins:
2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17 ...
. 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
.
:# Initialize
:# Compute
. By
Lagrange's theorem, this element has order
.
:# For all
, do:
:## Compute
. By construction, the order of this element must divide
, hence
.
:## Using the
baby-step giant-step algorithm, compute
such that
. It takes time
.
:## Set
.
:# Return
.
Assuming
is much smaller than
, the algorithm computes discrete logarithms in time complexity
, far better than the
baby-step giant-step algorithm's .
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 (to compute a logarithm modulo each prime power in the group order) and the
Chinese remainder theorem
In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer ''n'' by several integers, then one can determine uniquely the remainder of the division of ''n'' by the product of thes ...
(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
.
:# For each
, do:
:## Compute
. By
Lagrange's theorem, this element has order
.
:## Compute
. By construction,
.
:## Using the algorithm above in the group
, compute
such that
.
:# Solve the simultaneous congruence
The Chinese remainder theorem guarantees there exists a unique solution
.
:# 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
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.
[ Menezes, et al. 1997, pg. 108]
Notes
References
*
*
*
{{DEFAULTSORT:Pohlig-Hellman algorithm
Number theoretic algorithms