Engineering / Mathematics — Primality Testing

Generating a Random k-Bit Prime with Miller-Rabin

Assembling bit-length constraint, trial division filtering and Miller-Rabin into a complete prime generator.

Page KV-MATH-0391Reading time 4 minReviewed 2026-08-07Author Kevin Jogin

Executive summary

A production prime generator combines exact bit-length control, a small-prime filter, and a calibrated number of Miller-Rabin rounds, with an iteration cap for safety.

Each component has been analysed separately; this page assembles them and accounts for the total cost.

Learning objectives

Assemble the complete generation procedure.
Account for the total expected cost.
Enumerate the correctness and safety checks.

01The complete procedure

Algorithm

Production k-bit prime generator

Inputbit length k, filter bound y, round count

Outputa k-bit prime

Precompute the primorial P of primes in (2, y] for the chosen filter bound y.
Set an iteration cap C = c · k for a safety multiplier c.
For up to C attempts:
Draw k−2 uniform random bits from the system entropy source.
Form n with the top bit set, the drawn bits, and the low bit set.
If gcd(n, P) ≠ 1, continue.
Run one Miller-Rabin round with a random base; if composite, continue.
Run the remaining rounds; if any reports composite, continue.
Return n.
Report failure — indicates a broken entropy source or a bug, not bad luck.

Cost expected O(k) candidates; O(k⁴) bit operations overall

Splitting the first Miller-Rabin round from the rest is deliberate: nearly every composite surviving the filter fails immediately, so the remaining rounds run essentially only on genuine primes.

02Cost accounting

Candidates drawn≈ k ln 2 / 2From the prime density for k-bit odds
Filter invocationsone per candidateA gcd; cheap relative to exponentiation
First-round tests≈ 10% of candidatesOnly filter survivors
Full round sets≈ 1Essentially only the prime itself
Dominant termO(k) exponentiationsEach O(k³), giving O(k⁴) overall

For a 1024-bit prime this is roughly 355 candidates, about 35 first-round tests, and one full set of rounds — a few hundred modular exponentiations in total, which completes in well under a second.

03Correctness and safety checks

Bit length. Verify the output has exactly k bits. For RSA factors, set the top two bits so the product has exactly the intended length.
Entropy source. Block until the source is seeded. Generating long-term keys at first boot on embedded devices has produced moduli sharing prime factors across devices, a total compromise detectable by anyone with a corpus of public keys.
Independent bases. Draw each Miller-Rabin base independently. Deriving one from another breaks the error compounding.
Distinct factors. For RSA, verify p ≠ q and that they differ substantially, since close factors fall to Fermat factorisation.
Cap handling. Treat cap exhaustion as an error to be reported, not a condition to retry silently.

04Frequently asked questions

Why set the top two bits for RSA factors?

So that the product of two k-bit primes has exactly 2k bits. With only the top bit set, the product can be one bit short, producing a modulus that does not match the declared key size.

How many rounds for a locally generated candidate?

Far fewer than 40 suffice mathematically, but the cost of the extra rounds is negligible because they run only on the accepted prime. Keeping 40 removes the need to reason about the distinction.

Should the generator be constant time?

The number of candidates inevitably varies, so full constant time is not achievable. What matters is that the operations on the accepted prime do not leak its value, and that timing does not reveal the factors after generation.

Sources and method

Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 258-261.

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.