Engineering/Mathematics/Algorithm engineering

Generators and Discrete Logarithms in ℤ*p

Exponentiation modulo a prime is cheap and its inverse is not — provided the group order has a large prime factor. Pohlig–Hellman shows exactly how that condition can fail, and it is the reason protocol parameters are specified as carefully as they are.

Core algorithm
Computing
Protocol foundation
≈16 min read
Underpins Diffie–Hellman

O(√q)Generic boundBaby-step giant-step and Pollard rho, in a group of prime order q — and this is optimal for generic algorithms.

Pohlig–HellmanReductionCost drops to the largest prime factor of the group order, so a smooth order is fatal.

O(√q) spaceBSGS trade-offPollard rho matches the time with constant space, which is why it is preferred in practice.

L_p[⅓]Index calculusNon-generic attacks in ℤ*_p run in subexponential time, forcing large prime sizes.

Executive summary

Given a generator g of a cyclic group and an element h = g^x, the discrete logarithm problem is to recover x. In ℤ*_p the forward direction costs one modular exponentiation; the best known inverse costs subexponential time, and that asymmetry is the basis of Diffie–Hellman key exchange, DSA and ElGamal.

Two independent factors govern difficulty. Generic algorithms exploit only the group operation and run in O(√q) where q is the largest prime factor of the group order — so the order must have a large prime factor. Index calculus exploits the representation of elements as integers and runs in subexponential time in the size of p — so p itself must be large. Both constraints must be met simultaneously.

Parameter requirements for a prime-field discrete-log system
Requirement	Reason	Typical value
p large	Index calculus is subexponential in log p	2048–3072 bits
q ∣ p−1 large and prime	Generic attacks cost O(√q)	224–256 bits
g of order exactly q	Confines the computation to the strong subgroup	verified at generation
Received elements validated	Prevents small-subgroup confinement	check h^q = 1, h ≠ 1

This is the structure standardised for DSA and for finite-field Diffie–Hellman groups: a large prime p, a large prime-order subgroup q, and mandatory validation.

Contents

Finding a generator

ℤ*_p is cyclic of order p−1. Testing whether a candidate generates it requires the factorization of p−1 — there is no known shortcut.

Generator test for ℤ*p

input: prime p with the factorization p − 1 = ∏ qᵢ^eᵢ
repeat:
draw g uniformly from {2, …, p−2}
if g^{(p−1)/qᵢ} ≠ 1 for every i: return g

One exponentiation per prime factor per candidate. The success probability per candidate is φ(p−1)/(p−1), which exceeds roughly 1/(6 ln ln p) — so a small number of candidates suffices.

Generate the prime and its factorization together. Build p = 2q₁q₂⋯ + 1 from known primes and test p for primality, rather than trying to factor a given p−1.
Safe primes make everything easier. With p = 2q+1 and q prime, the factorization of p−1 is immediate and every element other than ±1 has order q or 2q. The cost is a much slower prime search.
A subgroup generator is usually preferable to a full generator. Take g = h^(p−1)/q for random h, which has order q unless it equals 1. Working in the prime-order subgroup eliminates leakage of the low-order bits of the exponent.

Contents

Generic algorithms

Generic discrete-log algorithms in a group of prime order q
Algorithm	Time	Space	Notes
Exhaustive search	O(q)	O(1)	Baseline
Baby-step giant-step	O(√q)	O(√q)	Deterministic; memory is the binding constraint
Pollard rho	O(√q) expected	O(1)	The practical generic choice
Pollard lambda (kangaroo)	O(√w) for an interval of width w	O(1)	When the exponent is known to lie in a short range
Parallel rho with distinguished points	O(√q / M) on M machines	modest	Linear speed-up; used in public record computations

Shoup's generic-group lower bound shows Ω(√q) operations are necessary for any algorithm using only the group operation — so these are optimal in that model.

Baby-step giant-step

m ← ⌈√q⌉
table ← { (g^j, j) : j = 0 .. m−1 } // baby steps
u ← g^{−m}
y ← h
for i = 0 .. m−1: // giant steps
if y is in table with value j: return i·m + j
y ← y·u
return failure

O(√q) group operations and O(√q) storage. Writing x = i·m + j with 0 ≤ i,j < m is the whole idea: a meet-in-the-middle over the two halves of the exponent.

Theorem T1

Pohlig–Hellman reduction

If the group order factors as m = ∏ q_i^e_i, then a discrete logarithm in the whole group reduces to one discrete logarithm in each subgroup of order q_i, repeated e_i times and lifted, with the results combined by the Chinese remainder theorem. Total cost is O(∑ e_i(log m + √q_i)) — governed by the largest prime factor, not by m.

The consequence for parameter choice

A group of order 2²⁵⁶ whose order is smooth offers no security at all. What matters is the largest prime factor of the order, which is why standards specify a prime-order subgroup and require that generated parameters be verified rather than trusted.

Contents

Diffie–Hellman key establishment

Agree on public parameters
A prime p, a prime q ∣ p−1 and a generator g of the order-q subgroup. These may be standardised or generated with verifiable randomness.
Each party samples a secret exponent
a and b uniformly from [1, q−1], using a cryptographic random source.
Exchange public values
A = g^a and B = g^b are sent in the clear.
Validate the received value
Check that it lies in the subgroup: B ≠ 1 and B^q = 1. Skipping this enables small-subgroup and invalid-parameter attacks.
Compute the shared secret
Both sides obtain g^ab. Derive keys from it with a key derivation function rather than using the raw group element.
Authenticate
Unauthenticated Diffie–Hellman is trivially defeated by an active in-the-middle attacker; signatures or a pre-shared secret are required.

Related computational assumptions
Problem	Statement	Relation
DLP	Given g^a, find a	Hardest of the three — solving it breaks the others
Computational DH	Given g^a, g^b, compute g^ab	No harder than DLP; equivalence is known only in special cases
Decisional DH	Distinguish g^ab from a random group element	Easiest; false in ℤ*_p itself because Legendre symbols leak, hence the prime-order subgroup

The DDH failure in the full group ℤ*p is a concrete reason for working in the subgroup of quadratic residues: the Legendre symbol of g^{ab} is otherwise computable from those of g^a and g^b.

Logjam and the cost of shared parameters

Index calculus splits into an expensive precomputation that depends only on p, and a cheap descent per individual logarithm. When many deployments share one standardised prime, an adversary can amortise the precomputation across all of them. The 2015 Logjam work demonstrated this for 512-bit export-grade primes and estimated it as feasible for 1024-bit primes against a state-level adversary. Modern guidance is 2048 bits or more, or a move to elliptic curves.

Contents

Where the problem is easy, and where it is not

Discrete logarithm difficulty by group
Group	Best known attack	Practical implication
(ℤ_n, +)	Extended Euclid — polynomial	Never usable for cryptography
ℤ*_p	Number field sieve, L_p[⅓, 1.92]	2048–3072 bit primes required
F*_2^k, small characteristic	Quasi-polynomial (Barbulescu et al., 2014)	Small-characteristic fields are broken for this purpose
Elliptic curve over F_p	Pollard rho, O(√q)	256-bit curves give roughly 128-bit security
Anomalous or low-embedding-degree curves	Polynomial or subexponential via pairings	Excluded by explicit curve validation criteria

The 2014 quasi-polynomial result for small-characteristic fields is a reminder that a problem believed hard in one representation can collapse in another.

Generic hardness is representation-independent; real hardness is not. The Ω(√q) lower bound applies only to algorithms that ignore the encoding of elements, and index calculus does not.
Elliptic curves resist index calculus because there is no useful notion of a small factor of a point, which is why they achieve equivalent security with far smaller parameters.
Quantum algorithms break all of these. Shor's algorithm solves discrete logarithms in any abelian group in polynomial time, which is why post-quantum designs rest on lattices, codes and hash functions instead.

Contents

Quick reference and FAQ

Facts
Fact	Statement
Generator test	g^(p−1)/q ≠ 1 for each prime q ∣ p−1
Generator density	φ(p−1)/(p−1) of elements
BSGS	O(√q) time and space
Pollard rho	O(√q) time, O(1) space
Pohlig–Hellman	Cost set by the largest prime factor of the order
Generic lower bound	Ω(√q) group operations
Index calculus in ℤ*_p	L_p[⅓, 1.92] with the number field sieve
Subgroup validation	h ≠ 1 and h^q = 1

Why is a prime-order subgroup used rather than all of ℤ*p?

Three reasons: exponents become shorter, so exponentiation is faster; Pohlig–Hellman gains nothing because the order is prime; and decisional Diffie–Hellman becomes plausible, whereas in the full group the Legendre symbol leaks a bit of the shared secret.

How do I know standardised parameters are not backdoored?

Prefer parameters generated by a published, verifiable procedure from a seed, so that anyone can reproduce them. Named groups such as those in RFC 7919 are widely reviewed; ad hoc parameters supplied by a peer should be validated or rejected.

Is Pollard rho really as fast as baby-step giant-step?

Same asymptotic time, constant space, and it parallelises with linear speed-up using distinguished points. BSGS remains useful when memory is plentiful and a deterministic bound is required.

Does a small-subgroup attack apply if I always validate?

Validation of received elements closes it. The residual risk is reusing a static secret exponent with unvalidated inputs — the attacker learns the exponent modulo small factors of p−1 and combines the residues by CRT.

Contents

References and further reading

V. Shoup, A Computational Introduction to Number Theory and Algebra, Cambridge University Press, 2005 — Chapter 11.
W. Diffie and M. E. Hellman, 'New directions in cryptography', IEEE Trans. Inform. Theory 22 (1976) 644–654.
S. C. Pohlig and M. E. Hellman, 'An improved algorithm for computing logarithms over GF(p)', IEEE Trans. Inform. Theory 24 (1978) 106–110.
D. Adrian et al., 'Imperfect forward secrecy: how Diffie–Hellman fails in practice', ACM CCS, 2015.
RFC 7919, Negotiated Finite Field Diffie-Hellman Ephemeral Parameters for TLS, IETF, 2016.

KEVOS® Knowledge LibraryEngineering → MathematicsTaxonomy ID: ENG-MATHPage ID: discrete-logarithms-in-zpReview cycle: annual

Generators and Discrete Logarithms in ℤ*p

Executive summary

Finding a generator

Generic algorithms

Pohlig–Hellman reduction

Diffie–Hellman key establishment

Agree on public parameters

Each party samples a secret exponent

Exchange public values

Validate the received value

Compute the shared secret

Authenticate

Where the problem is easy, and where it is not

Quick reference and FAQ

References and further reading

Continue learning

KEVOS Intelligence

Executive summary

Finding a generator

Generic algorithms

Pohlig–Hellman reduction

Diffie–Hellman key establishment

Agree on public parameters

Each party samples a secret exponent

Exchange public values

Validate the received value

Compute the shared secret

Authenticate

Where the problem is easy, and where it is not

Quick reference and FAQ

Related pages in this library

References and further reading

Continue learning