Engineering / Mathematics — Discrete Logarithms and Factoring
Finding a Generator of the Group of Units Modulo p
Locating a generator of Z_p*, the test based on the factorisation of p-1, and the density of generators.
Executive summary
The group of units modulo a prime is cyclic, so generators exist. Finding one is a generate-and-test procedure, and the test requires the factorisation of p minus one.
That requirement is why cryptographic primes are constructed with a known factorisation of p minus one rather than discovered at random.
Learning objectives
- State the generator test and justify it.
- Compute the density of generators.
- Explain the dependence on factoring p minus one.
01The test
Generator criterion
Let p − 1 = q₁^{e₁} ··· qₖ^{eₖ}. An element g ∈ Z_p* is a generator if and only if
g^{(p−1)/qᵢ} ≠ 1 (mod p) for every i.
The criterion works because the order of g divides p − 1, and a proper divisor of p − 1 divides (p−1)/qᵢ for at least one prime qᵢ. Ruling out each such case forces the order to be the full group order.
Find a generator
prime p with the factorisation of p−1a generator of Z_p*- Factor p − 1 into primes q₁, ..., qₖ.
- Repeat:
- Draw g uniformly from {2, ..., p−2}.
- If g^{(p−1)/qᵢ} ≠ 1 for every i, return g.
- Until a cap is reached.
expected O(1) candidates; k exponentiations per candidate02Density of generators
The number of generators is φ(p−1), so the probability that a random element is a generator is φ(p−1)/(p−1).
φ(p−1)/(p−1) = ∏_{q | p−1} (1 − 1/q) ≥ c / ln ln pThe bound is never worse than about 1/(6 ln ln p), which for cryptographic sizes is a small constant. A handful of candidates suffices in practice, and the expected count is bounded.
03The factoring dependence
The standard resolution is to construct the prime with the factorisation known in advance.
Choose the factorisation first
Select primes qᵢ and exponents, forming a candidate value for p − 1.
Form p
Set p = (that product) + 1.
Test p for primality
Miller-Rabin; if composite, adjust and retry.
Find a generator
The factorisation is known by construction, so the test applies directly.
Safe primes are the cleanest instance: with p = 2q + 1 and q prime, the factorisation of p − 1 is simply 2q, and the generator test needs only two exponentiations.
This dependency is a good example of a recurring theme: the structure that makes a group usable for cryptography must be arranged during parameter generation, because verifying it afterwards can be as hard as the problems the scheme relies on.
04Frequently asked questions
Is a generator needed, or does any element of large order suffice?
For most protocols an element of large prime order is what is actually required, not a full generator. Working in a prime-order subgroup is usually preferable, since it avoids small-subgroup issues entirely.
Are small numbers like 2 often generators?
Frequently, and implementations often test small candidates first for efficiency. There is no security concern in a generator being small — the discrete logarithm problem does not become easier for small bases.
What if p − 1 cannot be factored?
Then the generator test cannot be applied and no element can be certified as a generator. This is precisely why cryptographic primes are constructed with known structure rather than found by searching.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 268-270.
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.