Engineering / Mathematics — Probabilistic Algorithms
Generating a Random Prime
Generating a random prime by repeated candidate testing, the expected number of trials, and the sieving optimisation.
Executive summary
Random prime generation draws candidates and tests them until one passes. The prime number theorem fixes the expected number of trials, and trial division by small primes removes most composites far more cheaply than a full test.
The procedure is the foundation of RSA and Diffie-Hellman key generation.
Learning objectives
- State the expected number of candidates required.
- Justify the small-prime sieving step.
- Bound the total expected cost.
01The basic procedure
Generate a random prime below M
bound M, round count ta probable prime below M- Draw a uniform candidate n from [2, M).
- Test n for primality with Miller-Rabin using t rounds.
- If it passes, return n.
- Otherwise repeat.
expected O(ln M) candidatesBy the prime number theorem the density of primes near M is about 1/ln M, so the expected number of candidates is about ln M. Restricting to odd candidates halves this immediately.
Expected candidates ≈ ln M / 2 for odd candidates02Sieving by small primes
A full Miller–Rabin round costs a modular exponentiation. Trial division by a small prime costs a single division. Since most composites have a small factor, filtering first is dramatically cheaper.
| Filter | Composites removed | Cost per candidate |
|---|---|---|
| Odd only | 50% | Free, by construction |
| Primes below 100 | ≈ 76% | 25 divisions |
| Primes below 1000 | ≈ 84% | 168 divisions |
| Primes below 10⁴ | ≈ 88% | 1229 divisions |
The proportion surviving a sieve by all primes below y is about e^{−γ}/ln y by Mertens' theorem, which is why returns diminish: extending the sieve bound tenfold removes only a few percent more.
03Total cost
Draw a candidate
Uniform odd value of the target size.
Sieve
Trial divide by precomputed small primes; reject on any hit.
Test
Run Miller-Rabin rounds only on survivors.
Repeat
Until a candidate passes.
The expected cost is dominated by Miller–Rabin runs on sieve survivors. With sieving removing roughly nine composites in ten, the number of full tests falls by an order of magnitude relative to the naive procedure.
04Frequently asked questions
How many Miller-Rabin rounds are needed?
Far fewer than the worst-case bound suggests. For random candidates rather than adversarial ones the error probability per round is vastly below one quarter, and standards typically specify a handful of rounds for large sizes.
Is incremental search from a random start acceptable?
It is common and much faster, since sieving can be done once over an interval. The output distribution is not uniform over primes — primes following a large gap are favoured — but the deviation is not known to be exploitable.
What if the candidate must satisfy extra conditions?
Such as p ≡ 3 mod 4, or q dividing p−1. Equidistribution across residue classes means restricting to one admissible class multiplies the expected trials by φ(n) and no more.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 162-165.
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.