Pohlig–Hellman turns one discrete logarithm in a cyclic group of composite order into several smaller discrete logarithms in prime-power components, then reconstructs the answer with the Chinese Remainder Theorem.
The algorithm is not a different definition of a discrete logarithm. It is a structural decomposition of the exponent. If a generator α has order
n = p1^e1 p2^e2 ··· pr^er,
then an unknown exponent x modulo n is determined by its residues modulo each prime power p_i^e_i. Pohlig–Hellman computes those residues separately. The expensive part is no longer the whole order n; it is the largest prime divisor appearing inside the decomposition.
This is Guide 25 in the Bukit Timah Tutor Computational Number Theory series. It deepens the overview in Guide 6: Discrete Logarithms, Baby-Step Giant-Step and Pollard Rho. It also reuses the Chinese Remainder Theorem from Guide 2 and the subgroup/order viewpoint from the finite-field and elliptic-curve guides.
Return to the BTT Mathematics Hub for the wider Mathematics estate.
1. The discrete logarithm problem
Let G be a cyclic group generated by α, with known order n. Given β∈G, find x such that
α^x = β.
The exponent is unique modulo n. We therefore seek x in the residue class ring Z/nZ.
Generic algorithms such as baby-step giant-step or Pollard rho work directly in a group whose relevant order is n. Their cost is on the scale of √n group operations, up to logarithmic and constant factors.
Pohlig–Hellman asks a different question first: how does n factor?
2. Why factorisation of the group order changes the problem
Suppose
n = 2^4 · 3 · 7 = 336.
Then the residue x mod336 is uniquely determined by
x mod16, x mod3, x mod7.
Instead of searching through 336 possible exponent classes as one object, we can solve three smaller problems and reconstruct x by CRT.
The same idea works for enormous n. If every prime divisor of n is small, the discrete logarithm can be much easier than the raw size of n suggests. If n contains one very large prime factor q, the q-component remains hard and usually dominates the work.
3. Projection into a prime-power subgroup
Fix one prime-power factor q^e of n. Let
n = q^e · m, with gcd(q,m)=1.
Raise both sides of α^x=β to the power m:
(α^m)^x = β^m.
The element α^m has order q^e. All components of the original group whose orders are coprime to q have been removed.
Thus the projected equation determines
x mod q^e.
This is the first layer of Pohlig–Hellman: project into each Sylow-style prime-power component of the cyclic group.
4. Why not simply solve one log of order q^e?
We could apply baby-step giant-step directly to the q^e-order subgroup, at cost roughly q^(e/2). Pohlig–Hellman can do better by recovering the exponent one base-q digit at a time.
Write
x mod q^e = l0 + l1 q + l2 q² + ··· + l_(e−1) q^(e−1),
where each digit l_j lies in {0,1,…,q−1}.
Each stage reduces to a discrete logarithm in a group of order q, not q^e.
5. The digit-lifting invariant
Suppose digits l0,…,l_(j−1) are known. Let
x_j = l0 + l1q + ··· + l_(j−1)q^(j−1).
Then β α^(−x_j) removes the part of the exponent already discovered. Raise this corrected element to
n / q^(j+1).
All higher unknown digits vanish because their exponents become multiples of n. What remains depends only on l_j.
Use the fixed order-q element
ω = α^(n/q).
The stage equation becomes
ω^(l_j) = (β α^(−x_j))^(n/q^(j+1)).
So l_j is a discrete logarithm in a group of prime order q.
6. The complete algorithm
Given α of order n and β∈<α>:
1. Factor n = product p_i^e_i. 2. For each prime power p_i^e_i: a. Recover x_i = x mod p_i^e_i digit by digit. b. Each digit requires one DLP in an order-p_i subgroup. 3. Reconstruct x mod n from all x_i using CRT. 4. Verify α^x = β.
The final verification is essential. It is cheap compared with the search and catches arithmetic, indexing and reconstruction mistakes.
7. A complete worked example in F337*
Work in the multiplicative group modulo the prime 337. The group order is
336 = 2^4 · 3 · 7.
Take
α = 10, β = 235.
We will solve
10^x ≡ 235 (mod337).
The answer will be recovered independently modulo 16, 3 and 7.
8. Verify that 10 has full order 336
To prove α is a generator of F337*, it is enough to check α^(336/q)≠1 for every prime q dividing 336.
10^168 mod337 = 336 ≠1 10^112 mod337 = 128 ≠1 10^48 mod337 = 175 ≠1.
Therefore the order of 10 is divisible by 2^4,3 and7 and hence equals 336.
This check matters. Pohlig–Hellman must use the actual order of α, not automatically the full ambient group order.
9. Solve x modulo 16
Here q=2,e=4. Write
x ≡ l0 + 2l1 + 4l2 + 8l3 (mod16),
with l_j∈{0,1}.
The order-two base is
ω = 10^(336/2) = 10^168 ≡336 ≡−1 (mod337).
So every digit equation asks only whether the corrected value is 1 or −1.
Digit l0
No digits are known yet, so x_0=0:
235^(336/2) ≡336 = ω.
Therefore l0=1.
Digit l1
Now x_1=1. Remove 10^1 from β and raise to 336/4=84:
(235·10^−1)^84 ≡336 = ω.
Therefore l1=1.
Digit l2
The known low digits give x_2=1+2=3. Correct by 10^3:
(235·10^−3)^42 ≡1.
Therefore l2=0.
Digit l3
The known value remains x_3=3. Raise the corrected element to 336/16=21:
(235·10^−3)^21 ≡336 = ω.
Therefore l3=1.
Hence
x ≡ 1 + 2 + 0·4 + 1·8 ≡ 11 (mod16).
10. The same 2-adic lift as a table
j known x_j corrected order-2 value digit l_j 0 0 336 1 1 1 336 1 2 3 1 0 3 3 336 1
The important feature is not the small numbers. At every row, the unknown digit has been isolated into the same tiny subgroup generated by −1.
11. Solve x modulo 3
Project to the order-three subgroup by raising to 336/3=112:
ω3 = 10^112 mod337 = 128. 235^112 mod337 = 1.
Since 128^0=1,
x ≡ 0 (mod3).
No digit lifting is needed because the prime power is 3^1.
12. Solve x modulo 7
Project to order seven:
ω7 = 10^(336/7) = 10^48 ≡175. 235^48 mod337 ≡79.
The powers of 175 modulo337 are
175^0 ≡ 1 175^1 ≡ 175 175^2 ≡ 295 175^3 ≡ 64 175^4 ≡ 79.
Therefore
x ≡ 4 (mod7).
13. Reconstruct the exponent with CRT
We now have
x ≡ 11 (mod16) x ≡ 0 (mod3) x ≡ 4 (mod7).
Combine the last two first. From x≡0 mod3, write x=3k. Then
3k ≡4 (mod7).
The inverse of 3 modulo7 is5, so
k ≡20 ≡6 (mod7).
Thus
x ≡18 (mod21).
Write x=18+21t and impose the mod16 condition:
18+21t ≡11 (mod16) 2+5t ≡11 (mod16) 5t ≡9 (mod16).
The inverse of5 modulo16 is13, so
t ≡9·13 ≡117 ≡5 (mod16).
Therefore
x ≡18+21·5 ≡123 (mod336).
14. Final verification
Compute directly:
10^123 mod337 = 235.
The reconstructed exponent satisfies the original equation. The solution is therefore
log_10(235) = 123 mod336.
This example was independently checked with exact modular arithmetic before publication.
15. Why the prime-power digit method works
Write the unknown exponent as
x = x_j + l_j q^j + q^(j+1)u.
Then
β α^(−x_j) = α^(l_j q^j + q^(j+1)u).
Raise to n/q^(j+1):
(β α^(−x_j))^(n/q^(j+1)) = α^(l_j n/q + un).
The α^(un) term is the identity because α has order n. Hence
(β α^(−x_j))^(n/q^(j+1)) = (α^(n/q))^l_j.
The right side lies in the order-q subgroup generated by ω=α^(n/q). The higher unknown digits have disappeared exactly.
16. Choosing the inner discrete-logarithm solver
Each digit l_j is a discrete logarithm in a group of prime order q. If q is tiny, exhaustive search is often simplest.
For larger q, baby-step giant-step gives deterministic square-root-scale work with square-root-scale storage. Pollard rho gives similar square-root-scale expected group operations with much lower memory.
Pohlig–Hellman is therefore a framework. It reduces the original problem to many smaller prime-order DLPs, and another algorithm solves each of those.
17. Complexity and the largest prime factor
Given the factorisation
n = product p_i^e_i,
and using square-root methods inside each prime-order subgroup, a standard complexity description is proportional to
sum over i of e_i · (log n + sqrt(p_i))
group operations, up to implementation details.
The qualitative lesson is more important than the exact cost formula: the largest prime divisor of the group order controls the difficult component.
A 1000-bit group order that factors completely into small primes can be easier for discrete logarithms than a much smaller group order containing one 250-bit prime factor.
18. Smoothness is helpful to the algorithm
An integer is B-smooth if all of its prime factors are at most B. Pohlig–Hellman is particularly effective when the group order is smooth.
This connects discrete logarithms to the same smoothness concept that appeared in factorisation algorithms. In the quadratic sieve, smooth values create linear relations. In ECM, smooth elliptic-curve orders create factors. In Pohlig–Hellman, a smooth group order decomposes the exponent into easy components.
The mathematical object changes, but the computational advantage of smooth structure keeps returning.
19. Prime-order subgroups isolate the hard part
Suppose n=hq where q is a large prime and h is completely smooth. Pohlig–Hellman solves the h-part cheaply and leaves one DLP modulo q.
If applications use only the subgroup of order q generated by α^h, then the easy cofactor has been removed from the working group.
This is one reason cyclic-group protocols are often formulated inside a large prime-order subgroup rather than the entire multiplicative group.
This guide is about the mathematics of group decomposition, not a security recommendation for any specific deployed system.
20. The order of α must be known correctly
If α does not generate the entire ambient group, use ord(α), not the ambient group order.
For example, if α has order 84 inside a group of order336, then exponents are defined modulo84. Artificially inserting the missing factor four creates components that do not belong to the cyclic subgroup generated by α.
In a finite field, generator testing uses the prime factors of p−1. On an elliptic curve, subgroup order is usually supplied by point-order or curve-order computations.
21. Membership matters
The equation α^x=β has a solution only when β belongs to the cyclic subgroup generated by α.
If α generates the whole working group G and β∈G, membership is automatic. If α generates only a subgroup, a separate membership condition may be required.
An algorithm that silently assumes membership can produce a failed digit log or inconsistent CRT data rather than a meaningful exponent.
22. Pohlig–Hellman on elliptic curves
The algorithm is not tied to multiplication modulo a prime. Any cyclic group with efficient group operations can be used.
For an elliptic-curve point P of order n and Q=[x]P, factor n. Project into the q^e component by multiplying points by n/q^e. Recover x modulo each q^e, then combine with CRT.
Products become point addition; exponentiation becomes scalar multiplication; the structure of the algorithm is unchanged.
23. Pohlig–Hellman and CRT are inverse viewpoints
The group order decomposition
n = product p_i^e_i
induces an exponent-ring decomposition
Z/nZ ≅ product Z/p_i^e_i Z.
Pohlig–Hellman moves from the global exponent to the components. CRT moves back from components to the global exponent.
The algorithm is therefore a computational realisation of a structural isomorphism, not merely a clever search trick.
24. Precomputation when many logs share the same group
If many discrete logarithms are solved for the same α and group order, several quantities can be reused:
factorisation of n, projection exponents n/p_i^e_i, order-p_i generators α^(n/p_i), lookup tables for very small p_i.
This can make repeated logs substantially cheaper than independent one-off solves.
For a single instance, precomputation overhead should still be included in performance accounting.
25. Memory tradeoffs
If the largest prime factor q is moderate, baby-step giant-step may be attractive because it is deterministic and simple. Its table needs roughly √q stored group elements.
Pollard rho avoids that large table and uses pseudorandom walks plus collision detection, with expected square-root-scale group work.
The next guide develops that collision equation and the parallel distinguished-point method in detail.
26. A clean implementation contract
A reusable Pohlig–Hellman routine should receive:
a group operation, identity element, inversion or subtraction operation, scalar/exponentiation operation, α and β, ord(α), prime-power factorisation of ord(α), an inner prime-order DLP solver.
The routine should return x modulo ord(α) or an explicit failure if a component log cannot be solved.
Separating the abstract group operations from the decomposition logic makes the same implementation pattern usable for finite fields and elliptic curves.
27. Pseudocode
PH(alpha, beta, n, factorisation):
residues = []
moduli = []
for (q, e) in factorisation:
omega = alpha^(n/q)
x_partial = 0
for j in 0..e-1:
corrected = beta * alpha^(-x_partial)
c = corrected^(n / q^(j+1))
digit = discrete_log_order_q(omega, c, q)
x_partial += digit * q^j
residues.append(x_partial)
moduli.append(q^e)
x = CRT(residues, moduli)
verify alpha^x == beta
return xThe notation alpha^(-x_partial) means the inverse of alpha^(x_partial) in the abstract group.
28. Testing strategy
For bounded educational tests, generate cyclic groups of known order and random exponents x. Compute β=α^x. Ask the implementation to recover x and compare modulo ord(α).
Test separately:
single prime order, a prime power such as 2^e, several coprime prime powers, x=0, x=n−1, components with zero digits, components with maximal digits.
Also test deliberately incorrect order/factorisation data and subgroup-membership failures. A robust implementation should fail clearly rather than return an unchecked integer.
29. Common mistakes
1. Factoring the ambient group order instead of ord(α). 2. Solving x modulo p but forgetting higher p-adic digits when p^e divides n. 3. Using n/p^e where the digit-lifting formula requires n/p^(j+1). 4. Forgetting to remove previously recovered digits before the next lift.
5. Applying CRT to moduli that are not the pairwise-coprime prime powers. 6. Assuming every β in the ambient group lies in <α>. 7. Reporting complexity in terms of n alone and ignoring the largest prime divisor. 8. Skipping the final verification α^x=β.
30. Practice set
1. State the discrete logarithm problem in a cyclic group. 2. Factor 336 into prime powers. 3. Explain why x mod336 is determined by x mod16, mod3 and mod7. 4. What projection isolates the q^e-component?
5. Write x mod2^4 in base two. 6. Derive the digit-lifting equation. 7. Why does each digit log have order q rather than q^e? 8. In the worked example, what is ω for q=2?
9. Recover the four binary digits from the table. 10. What residue does this give mod16? 11. Why is x≡0 mod3? 12. Why is x≡4 mod7?
13. Reconstruct x from the three congruences. 14. Verify the final exponent. 15. What group-order property makes Pohlig–Hellman especially efficient? 16. Which component dominates when one prime divisor is huge?
17. What changes when the group is elliptic-curve based? 18. Why might Pollard rho be chosen as the inner solver? 19. What quantities can be precomputed for repeated logs? 20. What is the final correctness check?
31. Answers
1. Given α of order n and β∈<α>, find x modulo n with α^x=β. 2. 336=2^4·3·7. 3. The prime-power moduli are pairwise coprime and their product is336, so CRT gives a unique residue modulo336. 4. Raise α and β to n/q^e.
5. l0+2l1+4l2+8l3. 6. Remove the known low digits and raise to n/q^(j+1), leaving (α^(n/q))^l_j. 7. The exponentiation kills all but one base-q digit and projects into the subgroup generated by α^(n/q). 8. 336≡−1 mod337.
9. 1,1,0,1. 10. 11 mod16. 11. The projected target is one in the order-three subgroup. 12. 175^4≡79, matching the projected target.
13. x≡123 mod336. 14. 10^123≡235 mod337. 15. A smooth or nearly smooth group order. 16. The large-prime-order component.
17. Multiplication/exponentiation become point addition/scalar multiplication; the decomposition is otherwise the same. 18. It gives square-root-scale expected work with low memory. 19. Factorisation of n, projection exponents, prime-order generators and small lookup tables. 20. Recompute α^x and compare with β.
Sources and further study
The Handbook of Applied Cryptography, Chapter 3, gives a standard Pohlig–Hellman algorithm, complexity statement and worked example. Victor Shoup’s A Computational Introduction to Number Theory and Algebra develops generator finding, discrete logarithms and Pohlig–Hellman-style reductions from an algorithmic viewpoint.
Continue through Batch 07
Next: Guide 26 will develop Pollard rho for discrete logarithms, collision equations and parallel distinguished-point search. Guide 27 will move to index calculus and factor-base relation collection. Guide 28 will extend that relation machinery to number-field-sieve discrete logarithms and descent.