Engineering / Mathematics — Primality Testing
Generating a Random Prime Between 2 and M
Generating a uniform random prime below a bound, the analysis of the retry loop, and the resulting output distribution.
Executive summary
Drawing uniform candidates below a bound and testing each until one is prime yields a prime distributed uniformly over the primes in range.
The expected number of candidates follows from the prime number theorem, and the analysis is the geometric distribution applied to a known success probability.
Learning objectives
- State the generation procedure and its expected cost.
- Prove the output distribution is uniform.
- Handle the interaction between test error and output correctness.
01The procedure
Random prime below M
bound M, round count ka prime in [2, M], uniform over primes in range- Repeat:
- Draw a uniform integer n from {2, ..., M}.
- Apply trial division by small primes; if composite, continue.
- Apply Miller-Rabin with k rounds; if composite, continue.
- Return n.
- Until an iteration cap is reached.
expected ≈ ln M candidatesThe success probability per candidate is π(M)/M ≈ 1/ln M, so the expected number of candidates is about ln M by the geometric distribution.
02Uniformity of the output
Output distribution
If candidates are drawn uniformly and independently, and the test is applied identically to each, the returned value is uniform over the primes in the range.
Reason. Conditioned on acceptance, every prime was equally likely to have been the drawn candidate, and acceptance depends only on primality.
Uniformity matters where a security argument assumes it. For RSA the requirement is weak, but for schemes whose proofs quantify over uniformly chosen primes, a biased generator invalidates the reduction.
03Test error and output correctness
The output is prime only up to the error probability of the primality test. Two error sources compound and are worth separating.
| Source | Probability | Consequence |
|---|---|---|
| Miller-Rabin false positive | ≤ 4^{−k} per accepted candidate | A composite is returned as prime |
| Cap exhausted | ≤ e^{−c} | Failure reported; caller retries |
| Entropy failure | Not quantifiable | Correlated or repeated outputs; catastrophic |
Only the first affects correctness of a returned value. The second is a clean failure the caller can handle, and the third is outside the probabilistic model entirely — which is why entropy quality must be established by other means rather than folded into the analysis.
04Frequently asked questions
Does the trial division filter affect uniformity?
No, because it rejects only composites. Any filter whose acceptance depends solely on primality preserves uniformity over the primes; a filter that rejected some primes would not.
Why draw from {2,...,M} rather than a bit-length range?
This form is the clean case for analysis. Practical generation fixes a bit length instead, which restricts the range to [2^{k−1}, 2^k) and changes the density slightly without altering the argument.
How large should the iteration cap be?
A small multiple of ln M — a hundred times the expected count makes spurious failure negligible while still catching a broken entropy source promptly.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 252-255.
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.