Engineering / Mathematics — Discrete Logarithms and Factoring
Discrete Logarithms in the Full Group Modulo p
The Pohlig-Hellman reduction combining prime power subproblems by the Chinese remainder theorem.
Executive summary
The discrete logarithm in a group of composite order reduces to the problem in each prime power factor, with the results reassembled by the Chinese remainder theorem.
The overall cost is governed by the largest prime factor of the group order, which is why smooth group orders are fatal.
Learning objectives
- State the Pohlig-Hellman reduction.
- Compute the resulting cost.
- Derive the parameter selection rule it implies.
01The reduction
Pohlig-Hellman
Let γ generate a group of order q = q₁^{e₁} ··· qₖ^{eₖ}. The discrete logarithm x is determined by its residues modulo each qᵢ^{eᵢ}, and each residue is a discrete logarithm in a group of that order.
Project to each factor
Raise both γ and α to the power q/qᵢ^{eᵢ}, giving elements of order qᵢ^{eᵢ}.
Solve each subproblem
Use the prime power method, itself reducing to order-qᵢ problems.
Reassemble
Chinese remainder the residues to recover x modulo q.
The projection works because raising to q/qᵢ^{eᵢ} maps the group onto its subgroup of that order, and the logarithm of the image is the residue of x modulo qᵢ^{eᵢ}.
02The cost
Total cost ≈ Σᵢ eᵢ(√qᵢ + log q) dominated by the largest prime factor| Group order q | Largest prime factor | Effective security |
|---|---|---|
| Prime, 256 bits | q itself | 2^128 — full |
| 2 × prime, 256 bits | The 255-bit prime | 2^127 — effectively full |
| Product of 32-bit primes | About 2^32 | 2^16 — negligible |
| Smooth, all factors small | Small | Broken |
03Parameter selection
The reduction dictates how cryptographic groups must be chosen.
Prime order subgroup
Work in a subgroup of large prime order q, so the reduction has nothing to decompose.
Safe primes
With p = 2q + 1, the group order p − 1 = 2q has only the trivial factor 2 alongside a large prime.
Validate group elements
Check that received elements lie in the intended prime-order subgroup, or an attacker can force the computation into a small subgroup.
The defence is to verify that any received element raised to the subgroup order gives the identity, or equivalently to work in a group where no small subgroup exists.
04Frequently asked questions
Does this attack apply to elliptic curves?
Yes, identically — it is a generic group method. Curve parameters are therefore chosen so the group order is prime or prime times a very small cofactor, and implementations validate that received points lie on the curve and in the right subgroup.
Why does the factor of 2 in a safe prime not matter?
Because it leaks only one bit — the quadratic character of the element. Working in the subgroup of squares removes even that, and no further reduction is available.
Is the factorisation of the group order needed to attack?
Yes, and it is normally public, since the group order is part of the published parameters. There is no security in hiding it, which is why the structure must be chosen safe rather than obscured.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 274-275.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.