Engineering / Mathematics — Probabilistic Algorithms
Generating a Random k-Bit Prime
Generating a prime of exactly k bits, the density in that range, and the constraints imposed by cryptographic use.
Executive summary
Cryptographic keys require primes of an exact bit length, not merely below a bound. Fixing the top bit restricts the range to a dyadic interval, where Bertrand's postulate guarantees a prime exists.
The density in that interval determines the expected number of trials.
Learning objectives
- Constrain a candidate to exactly k bits.
- Estimate the density of primes in a dyadic interval.
- Apply the additional constraints cryptographic use imposes.
01Fixing the bit length
A k-bit integer lies in [2^{k−1}, 2^k). Setting the top bit forces the length and setting the bottom bit forces oddness, so both are imposed at generation rather than by rejection.
Generate a random k-bit prime
bit length k, round count ta probable prime of exactly k bits- Draw k − 2 uniform random bits.
- Form n by prefixing a 1 bit and appending a 1 bit, giving an odd k-bit value.
- Sieve n by small primes; if any divides it, return to step 1.
- Run t rounds of Miller-Rabin; if any fails, return to step 1.
- Return n.
expected O(k) candidates before sievingBertrand's postulate guarantees the interval contains a prime for every k ≥ 2, so the search cannot fail for lack of a target.
02Density in the interval
The number of primes in [2^{k−1}, 2^k) is approximately 2^{k−1}/(k ln 2), so among odd candidates in that range the density is about 2/(k ln 2).
| Bit length | Expected odd candidates | After sieving to 10³ |
|---|---|---|
| 512 | ≈ 178 | ≈ 28 |
| 1024 | ≈ 355 | ≈ 57 |
| 2048 | ≈ 710 | ≈ 114 |
| 4096 | ≈ 1420 | ≈ 227 |
03Cryptographic constraints
RSA and discrete-log parameters impose conditions beyond primality, and each restricts the candidate pool.
Coprimality with e
For RSA, p − 1 must be coprime to the public exponent, or the private exponent does not exist. Cheap to check by a gcd.
Separation of p and q
The two factors must differ substantially in value, or Fermat factorisation recovers them quickly from a modulus whose factors are close.
Modulus length
The product must have exactly the target length, which constrains the top bits of each factor.
Strong or safe primes
Some standards require p − 1 to have a large prime factor. Slower to generate and of contested value against modern factoring methods.
04Frequently asked questions
Why fix the top bit rather than reject short candidates?
Because rejection would discard half the draws for no benefit. Setting the bit directly produces a uniform value on the dyadic interval, which is exactly the desired distribution.
Are strong primes still recommended?
Their value is contested. They defend against older factoring methods whose running time depends on the structure of p − 1, but the number field sieve is insensitive to that structure, so the protection is largely against attacks no longer relevant.
How does this scale to very large keys?
Poorly, at roughly the fourth power of the bit length. This is one practical reason elliptic curve cryptography is attractive: comparable security at far smaller parameter sizes, with much faster key generation.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 165-167.
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.