Pohlig–Hellman turns one discrete logarithm in a composite-order cyclic group into several smaller discrete logarithms whose moduli are the prime-power factors of the group order.
The algorithm is not a generic shortcut for every discrete-logarithm problem. Its advantage appears when the group order is smooth or nearly smooth. If the order factors as many small prime powers, the large exponent can be reconstructed from residues modulo those prime powers. If the order contains one very large prime factor, that factor still controls the hard part.
This is Guide 25 in the Bukit Timah Tutor Computational Number Theory series. It deepens the discrete-logarithm overview in Guide 6 and reuses the Chinese Remainder Theorem from Guide 2.
1. The discrete logarithm contract
Let G=<g> be a cyclic group of known order N. Given h in G, find x modulo N such that
g^x = h.
Because g has order N, exponents are naturally taken modulo N.
If N is prime, there is no nontrivial subgroup decomposition from the factorisation of N itself. If N is composite, every divisor of N gives a subgroup, and prime-power divisors are the natural pieces for reconstruction.
2. Factor the group order first
Write
N = q1^e1 q2^e2 ... qr^er
with distinct primes q_i.
Pohlig–Hellman computes
x mod q1^e1, x mod q2^e2, ... x mod qr^er
and then combines the residues with CRT.
This already tells us something important about parameter choice: the factorisation of the group order is part of the security or complexity profile.
3. Projecting into a prime-power subgroup
Fix one prime power q^e dividing N. Raise both sides of g^x=h to the power N/q^e:
(g^(N/q^e))^x = h^(N/q^e).
The element
g_q = g^(N/q^e)
has order q^e. Therefore the projected equation depends only on x modulo q^e.
We have reduced the original log to a smaller subgroup log.
4. A complete worked example modulo 41
Work in F41*. This group has order 40. Take g=6, which has order 40, and let
h=24.
We want x satisfying
6^x ≡24 (mod41).
The group order factors as
40 = 8·5 = 2^3·5.
So we will solve x modulo 8 and modulo 5.
5. Solve x modulo 8
Project into the subgroup of order 8 by raising to 40/8=5:
g8 = 6^5 mod41 = 27, h8 = 24^5 mod41 = 14.
Now solve
27^x ≡14 (mod41)
with x taken modulo8.
A short table gives x≡5 mod8. Since the subgroup is tiny, brute force is enough. For large prime powers, the algorithm lifts the exponent one base-q digit at a time.
6. Solve x modulo 5
Project into the subgroup of order5 by raising to 40/5=8:
g5 = 6^8 mod41 = 10, h5 = 24^8 mod41 = 16.
Now solve
10^x ≡16 (mod41)
with x modulo5.
The subgroup table gives x≡3 mod5.
7. Reconstruct x with CRT
We now know
x ≡5 (mod8) x ≡3 (mod5).
The unique solution modulo40 is
x ≡13 (mod40).
Check:
6^13 mod41 = 24.
The original discrete logarithm has been reconstructed from two smaller subgroup logs.
8. Why prime-power lifting is better than solving one q^e-size log directly
Suppose q^e is large enough that a direct baby-step giant-step search in a group of size q^e is expensive. Pohlig–Hellman can recover the exponent digits
x = x0 + x1 q + x2 q² + ... + x_(e−1) q^(e−1)
with each digit x_i in {0,…,q−1}.
At each stage, earlier digits are removed and the remaining equation is raised to a power that collapses it into a subgroup of order q. The repeated hard subproblem therefore has size q rather than q^e.
9. Base-two lifting in the mod 41 example
The residue x mod8 equals5, whose binary expansion is
5 = 1 + 0·2 + 1·4.
Let
γ = g^(40/2) = 6^20 mod41 = 40 = −1 mod41.
This element has order2.
Start with partial exponent zero.
Digit 0.
h^20 mod41 = 40 = γ
so x0=1.
Digit 1. Remove g^1 from h and raise to 40/4=10:
(h g^−1)^10 mod41 = 1
so x1=0.
Digit 2. The current partial exponent is still1. Raise the corrected value to 40/8=5:
(h g^−1)^5 mod41 = 40 = γ
so x2=1.
Therefore x≡1+0·2+1·4=5 mod8.
10. General prime-power digit formula
Suppose we are recovering x modulo q^e and have already found
x^(k) = x0+x1q+...+x_(k−1)q^(k−1).
Form
c_k = (h g^(−x^(k)))^(N/q^(k+1)).
Let
γ = g^(N/q).
Then γ has order q and
c_k = γ^(x_k).
Thus each digit is found by solving a discrete logarithm in a subgroup of order q.
11. The inner discrete-log algorithm is replaceable
Pohlig–Hellman is a decomposition framework, not one fixed inner solver.
For very small q, use a lookup table. For moderate q, use baby-step giant-step. For larger q, use Pollard rho. If q itself has exploitable field structure, other algorithms may be appropriate.
The total complexity is therefore governed by the largest prime factor of the group order and by the best available solver for each prime-order subgroup.
12. What smooth group order means
An integer is B-smooth if all of its prime factors are at most B.
If N is B-smooth with modest B, every subgroup discrete logarithm is small. Pohlig–Hellman can then be dramatically faster than a generic square-root algorithm on the whole group.
If N=q·s where q is a huge prime and s is smooth, the algorithm quickly removes the s-part but still leaves a discrete logarithm modulo q. The large q remains the bottleneck.
13. Why prime-order subgroups are often chosen deliberately
Many cryptographic constructions operate inside a subgroup of large prime order rather than the entire multiplicative or elliptic-curve group.
The reason is structural: if the operational subgroup order is prime, Pohlig–Hellman has no nontrivial factorisation to exploit.
This does not by itself prove security. It removes one specific weakness and leaves the generic and structure-specific discrete-log algorithms to be considered separately.
14. Pohlig–Hellman in elliptic-curve groups
The same decomposition works in any finite cyclic group with known factored order.
For an elliptic curve, replace exponentiation by scalar multiplication:
Q = [x]P.
If P has order N, project to the q^e subgroup by multiplying P and Q by N/q^e.
The mathematics is identical. Only the group operation changes.
15. Membership and order checks matter
Before solving, confirm that h lies in <g>. If g does not generate the claimed subgroup, the exponent modulus is the actual order of g, not the ambient group order.
In F_p*, one can verify a claimed generator order by checking
g^N=1
and, for every prime q dividing N,
g^(N/q) != 1.
Without the order contract, CRT reconstruction can return an exponent for the wrong modulus.
16. CRT reconstruction as an explicit certificate
Suppose residues are x_i modulo n_i with pairwise coprime n_i. Let
N = product n_i, M_i=N/n_i, y_i=M_i^−1 mod n_i.
Then
x = Σ x_i M_i y_i mod N.
For the worked example:
n1=8, x1=5, M1=5, 5^−1 mod8=5 n2=5, x2=3, M2=8, 8^−1 mod5=2
so
x ≡5·5·5 + 3·8·2 ≡125+48 ≡173 ≡13 (mod40).
17. Parallelism
The prime-power branches are independent. Once N is factored, the q_i^e_i subgroup problems can be solved in parallel and joined only at the CRT stage.
Within a large prime-order branch, the inner discrete-log solver may also be parallelisable.
This separation is useful in both software architecture and complexity analysis.
18. Failure modes
Wrong group order. Every projected subgroup equation may be mis-scaled.
Incomplete factorisation of N. The unresolved cofactor still represents an unresolved exponent modulus.
Non-generator g. The solution is only defined modulo ord(g).
Incorrect digit removal. Prime-power lifting is sensitive to the current partial exponent.
CRT with non-coprime moduli. Prime-power components for distinct primes are coprime; arbitrary subgroup moduli may not be.
19. Verification is easier than discovery
Given a claimed x, the final check is simply
g^x ?= h.
For a detailed algorithm receipt, also verify every projected subgroup equation and each CRT residue.
This makes the computation auditable: a complex decomposition can end with one exact group equality.
20. Complexity viewpoint
If N=∏q_i^e_i, the work is approximately the sum of the costs of solving discrete logarithms of order q_i repeatedly e_i times, plus modest exponentiation and CRT overhead.
With baby-step giant-step inside the prime-order steps, the dominant scale is roughly determined by √q_max rather than √N, where q_max is the largest prime divisor of N.
This is why factorisation of the group order is a first diagnostic step before choosing a discrete-log algorithm.
21. Practice set
1. State the Pohlig–Hellman input contract. 2. Factor40 into prime powers. 3. For g=6 mod41, compute the subgroup generator of order8. 4. Compute the projected target for h=24.
5. Solve x mod8. 6. Solve x mod5. 7. Reconstruct x mod40. 8. Verify the final discrete logarithm.
9. Explain why raising to N/q^e projects into a subgroup of order q^e. 10. Write the base-q expansion used in digit lifting. 11. Why does each digit reduce to a subgroup of order q? 12. Which inner algorithm can replace a lookup table?
13. What happens if N has one enormous prime factor? 14. Why do prime-order subgroups block this decomposition advantage? 15. How does the method change on elliptic curves? 16. What is the simplest final verification?
22. Answers
1. A cyclic group <g> of known factored order N and a target h in that subgroup. 2. 40=2³·5. 3. 6^5=27 mod41. 4. 24^5=14 mod41.
5. x≡5 mod8. 6. x≡3 mod5. 7. x≡13 mod40. 8. 6^13≡24 mod41.
9. The projected generator’s order divides q^e and equals q^e when g has full order N. 10. x=x0+x1q+…+x_(e−1)q^(e−1). 11. Raising the corrected equation by N/q^(k+1) annihilates all higher powers, leaving γ^(x_k) in the order-q subgroup. 12. Baby-step giant-step or Pollard rho.
13. That prime-order branch remains hard and dominates. 14. There are no smaller prime-power factors to reconstruct. 15. Replace exponentiation by scalar multiplication. 16. Check g^x=h.
Sources and further study
Stephen C. Pohlig and Martin E. Hellman, An Improved Algorithm for Computing Logarithms over GF(p) and Its Cryptographic Significance, IEEE Transactions on Information Theory 24(1), 1978. Victor Shoup’s A Computational Introduction to Number Theory and Algebra develops finite cyclic groups, CRT and discrete logarithm algorithms in a unified computational framework.
Continue through Batch 07
Continue to Guide 26: Pollard Rho for Discrete Logarithms, Guide 27: Index Calculus, and Guide 28: Number Field Sieve for Discrete Logarithms.