Pohlig–Hellman algorithm explained

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 introduced by Roland Silver, but first published by Stephen Pohlig and Martin Hellman, who credit Silver with its earlier independent but unpublished discovery. Pohlig and Hellman also list Richard Schroeppel and H. Block as having found the same algorithm, later than Silver, but again without publishing it.

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

\langleg\rangle

generated by

, which is always cyclic.)

Input. A cyclic group

of order

n=p^e

with generator

and an element

h\inG

Output. The unique integer

x\in\{0,...,n-1\}

such that

g^x=h

Initialize

x_0:=0.

Compute

	p^e-1
\gamma:=g

. By Lagrange's theorem, this element has order

For all

k\in\{0,...,e-1\}

, do:

1. Compute

	-x_k
h
	k:=(g

	p^e-1-k
h)

. By construction, the order of this element must divide

, hence

h_{k\in\langle\gamma\rangle}

1. Using the baby-step giant-step algorithm, compute

d_{k\in\{0,...,p-1\}}

such that

	d_k
\gamma

=h_k

. It takes time

O(\sqrtp)

1. Set

x_k+1

	kd
:=x
	k

Return

x_e

.The algorithm computes discrete logarithms in time complexity

O(e\sqrtp)

, far better than the baby-step giant-step algorithm's

O(\sqrt{p^e})

when

is large.

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

h\inG

, and a prime factorization

n=\prod_^rp_i^

Output. The unique integer

x\in\{0,...,n-1\}

such that

g^x=h

For each

i\in\{1,...,r\}

, do:

1. Compute

	e_i
n/p
	i

i:=g

. By Lagrange's theorem, this element has order

	e_i
p
	i

1. Compute

	e_i
n/p
	i

i:=h

. By construction,

h_i\in\langleg_i\rangle

1. Using the algorithm above in the group

\langleg_i\rangle

, compute

x_{i\in\{0,...,p}

	e_i

	i

-1\}

such that

	x_i
g
	i

=h_i

Solve the simultaneous congruence $x\equiv x_i\pmod$

\quad\forall i\in\\textThe Chinese remainder theorem guarantees there exists a unique solution

x\in\{0,...,n-1\}

Return

.The correctness of this algorithm can be verified via the classification of finite abelian groups: Raising

and

to the power of

	e_i
n/p
	i

can be understood as the projection to the factor group of order

	e_i
p
	i

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

lO(\sqrtn)

. However, it is much more efficient if the order is smooth: Specifically, if

\prod_i

	e_i
p
	i

is the prime factorization of

, then the algorithm's complexity is

\mathcal O\left(\sum_i \right)

group operations.^[2]

References

Book: Mollin, Richard. An Introduction To Cryptography. 2006-09-18. Chapman and Hall/CRC. 2nd. 978-1-58488-618-1. 344. Mollin06.
S.. Pohlig . Martin Hellman. M. . Hellman . An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance . IEEE Transactions on Information Theory . 24 . 1978 . 106–110 . 10.1109/TIT.1978.1055817 .
Book: Alfred J.. Menezes. Alfred Menezes. Paul C.. van Oorschot. Paul van Oorschot. Scott A.. Vanstone. Scott Vanstone. Handbook of Applied Cryptography. CRC Press. 1997. 107–109. Number-Theoretic Reference Problems. http://www.cacr.math.uwaterloo.ca/hac/about/chap3.pdf. 0-8493-8523-7. Menezes97. registration.

Notes and References

[#Mollin06|Mollin 2006]
[#Menezes97|Menezes, et al. 1997]