Engineering/Mathematics/Analytic number theory
The Distribution of Primes
Key generation is a sampling problem: draw random integers of a given size until one is prime. Whether that loop terminates quickly is a question about prime density, and the answer — roughly one in ln n — is the practical content of a century of analytic number theory.
- Density theory
- Number theory
- Underwrites key generation
- ≈16 min read
- Analytic results
01
Executive summary
Primes thin out, but slowly and predictably. The prime counting function π(x) satisfies π(x) ~ x/ln x, so the density of primes near x is about 1/ln x. For a k-bit number the density is about 1/(k ln 2), and restricting to odd candidates doubles it.
Three tiers of result matter to a practitioner. Chebyshev's elementary bounds fix the order of magnitude and are enough to prove that key generation terminates. Mertens' theorems control sums over primes and appear in sieve analysis. The prime number theorem and its arithmetic-progression refinement give the sharp constants used to estimate work per key and to justify the use of structured primes.
02
The prime counting function
π, θ and ψ
π(x) counts primes up to x. Analytic work prefers the weighted variants θ(x) = ∑p ≤ x log p and ψ(x) = ∑pk ≤ x log p, which are equivalent to π for asymptotic purposes: each of π(x) ~ x/ln x, θ(x) ~ x and ψ(x) ~ x implies the others.
| x | π(x) | x/ln x | li(x) | Relative error of x/ln x |
|---|---|---|---|---|
| 103 | 168 | 145 | 178 | ≈ 14% |
| 106 | 78,498 | 72,382 | 78,628 | ≈ 7.8% |
| 109 | 50,847,534 | 48,254,942 | 50,849,235 | ≈ 5.1% |
| 1012 | 37,607,912,018 | 36,191,206,825 | 37,607,950,281 | ≈ 3.8% |
| 1018 | 24,739,954,287,740,860 | ≈ 2.4128×1016 | ≈ 2.4740×1016 | ≈ 2.5% |
The convergence of x/ln x is genuinely slow; li(x) tracks π(x) far more closely, and the difference between them is the subject of the Riemann hypothesis.
The engineering form of the result
Near x, the chance that a random integer is prime is about 1/ln x. For a k-bit modulus factor, ln x ≈ 0.693k. At k = 1024 that is about 1/710 for odd candidates, and pre-sieving by small primes below 1000 removes roughly 80% of candidates before any expensive test runs.
03
Chebyshev's theorem and Bertrand's postulate
Chebyshev bounds
There are absolute constants 0 < c1 < c2 with c1x/ln x ≤ π(x) ≤ c2x/ln x for all x ≥ 2. The proof is elementary: the central binomial coefficient C(2n,n) is divisible by every prime in (n, 2n] and is bounded above by 4n, which pins θ(x) between linear bounds.
Bertrand's postulate
For every integer n ≥ 1 there is a prime p with n < p ≤ 2n. Proved by Chebyshev in 1852; Erdős's 1932 proof by careful analysis of the prime factorization of C(2n,n) is the version usually taught.
Why the elementary results are enough for algorithms
A randomised prime generator needs only a lower bound of the form c·x/ln x to prove that the expected number of trials is O(ln x). Chebyshev's bound supplies that with no analytic machinery, so the correctness and expected running time of key generation do not depend on the prime number theorem — only the sharp constants do.
Bertrand's postulate plays the analogous role for existence questions: it guarantees a prime in every dyadic interval, so “find a prime with exactly k bits” is always satisfiable, and it supplies the padding argument in several combinatorial proofs.
Contents04
Mertens' theorems
Sums and products over primes appear whenever a sieve is analysed. Mertens' results give them precisely:
| Result | Used for |
|---|---|
| ∑ 1/p diverges | Proves there are infinitely many primes, and that the divergence is only log-logarithmic — primes are sparse but not summably so |
| ∏(1−1/p) asymptotic | Density of integers with no small prime factor; the survival rate of trial-division pre-sieving |
| ∑ (log p)/p | Weighted prime sums appearing in Chebyshev-style arguments and smooth-number estimates |
| e−γ correction | Explains why the sieve of Eratosthenes retains about e−γ times the naively predicted count |
Design consequence
Pre-sieving candidates by all primes below B removes a fraction 1 − ∏p ≤ B(1−1/p) ≈ 1 − e−γ/ln B of them. Going from B = 100 to B = 106 only improves the survival rate from roughly 12% to 4%, because the product decays like 1/ln B. There is a clear point of diminishing returns, and it is reached early.
05
The prime number theorem and beyond
Prime number theorem
Proved independently by Hadamard and de la Vallée Poussin in 1896 using the non-vanishing of ζ(s) on the line Re(s) = 1. Elementary proofs were found by Erdős and Selberg in 1949.
The sharper statement with the logarithmic integral, π(x) = li(x) + E(x), is where error terms live. Unconditionally E(x) = O(x·exp(−c√(ln x))); under the Riemann hypothesis E(x) = O(√x ln x), which is essentially best possible.
Primes in arithmetic progressions
Dirichlet (1837): if gcd(a,d) = 1 then the progression a, a+d, a+2d, … contains infinitely many primes. PNT for progressions: the primes are asymptotically equidistributed among the φ(d) admissible residues, so π(x; d, a) ~ π(x)/φ(d).
Why this matters for structured primes
Cryptographic protocols often require primes of a special shape — safe primes p = 2q+1, or primes in a fixed residue class such as p ≡ 3 (mod 4) for fast square roots. Equidistribution says that fixing a residue class modulo a small d costs only a factor φ(d) in search time. Safe primes are a different matter: their density is conjectural, following a Hardy–Littlewood heuristic of order x/(ln x)2, and generation is correspondingly slower.
06
Gaps, and what remains open
| Statement | Status | Practical reading |
|---|---|---|
| Average gap near x is ~ ln x | Theorem (PNT) | Expected trials per prime found in key generation |
| Arbitrarily long prime-free gaps exist | Theorem — n!+2, …, n!+n | No guaranteed prime in a fixed short interval |
| A prime exists in (n, 2n] | Theorem (Bertrand) | Every bit-length is achievable |
| A prime exists in (n, n + n0.525] for large n | Theorem (Baker–Harman–Pintz, 2001) | Incremental search from a random start is provably efficient for large candidates |
| A prime exists between consecutive squares | Open (Legendre's conjecture) | Do not design an algorithm that requires it |
| Infinitely many twin primes | Open; bounded gaps below 246 known (Zhang, Maynard, Polymath) | Twin-prime-based parameters have no proven density |
| Riemann hypothesis | Open | Sharp error terms in π(x) and in many algorithm analyses are conditional on it |
Conditional results in algorithm analysis
Several bounds quoted in the algorithms literature — deterministic Miller–Rabin with a small fixed base set, bounds on the least primitive root, some index-calculus analyses — are conditional on the extended Riemann hypothesis. When such a bound is load-bearing for security or correctness, it must be labelled as conditional rather than presented as proved.
07
The sieve of Eratosthenes
For listing all primes below a bound — the standard way to build the small-prime table used in pre-sieving and in factor bases — nothing beats the classical sieve.
Sieve of Eratosthenes
- input: bound n
- A[2..n] ← true
- for p = 2 to ⌊√n⌋:
- if A[p]:
- for m = p², p²+p, p²+2p, …, ≤ n: A[m] ← false
- output {p : A[p]}
Θ(n log log n) operations and n bits of memory. Starting the inner loop at p² rather than 2p is what removes the redundant work; the log log factor is exactly Mertens' sum ∑ 1/p.
- Segmented sieving processes the range in cache-sized blocks, keeping only the primes up to √n in memory. This is the practical form for n beyond a few billion.
- Wheel factorisation skips multiples of the first few primes by construction, typically saving a constant factor of 3–4 in both time and space.
- Linear sieves reach Θ(n) by marking each composite exactly once via its smallest prime factor, and can compute μ, φ and the factorization of every n in the range at the same time.
- Do not use a sieve to test one large number for primality — that is the job of Miller–Rabin. The sieve answers a bulk question, not a point question.
08
Quick reference and FAQ
| Bit length k | Density among odd k-bit integers | Expected candidates per prime | Notes |
|---|---|---|---|
| 256 | ≈ 1/89 | ≈ 89 | Elliptic-curve field sizes |
| 512 | ≈ 1/178 | ≈ 178 | Factor of a 1024-bit RSA modulus |
| 1024 | ≈ 1/355 | ≈ 355 | Factor of a 2048-bit RSA modulus |
| 1536 | ≈ 1/532 | ≈ 532 | Factor of a 3072-bit RSA modulus |
| 2048 | ≈ 1/710 | ≈ 710 | Factor of a 4096-bit RSA modulus |
Using 2/(k ln 2) for odd candidates. Trial division by primes below 1000 typically removes about 80% of candidates before the first Miller–Rabin round, cutting real cost by roughly a factor of five.
Is x/ln x good enough for planning purposes?
Does the prime number theorem guarantee a prime in any given interval?
Are primes generated by incremental search from a random point safe to use?
Why do safe primes take so much longer to generate?
10
References and further reading
- V. Shoup, A Computational Introduction to Number Theory and Algebra, Cambridge University Press, 2005 — Chapter 5.
- T. M. Apostol, Introduction to Analytic Number Theory, Springer, 1976 — Chapters 3, 4 and 13.
- R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, 2nd ed., Springer, 2005 — Chapter 1 and §3.2 on sieving.
- R. C. Baker, G. Harman and J. Pintz, 'The difference between consecutive primes, II', Proc. London Math. Soc. 83 (2001) 532–562.
- M. Deléglise and J. Rivat, 'Computing π(x): the Meissel, Lehmer, Lagarias, Miller, Odlyzko method', Math. Comp. 65 (1996) 235–245.
KEVOS® Knowledge LibraryEngineering → MathematicsTaxonomy ID: ENG-MATHPage ID: distribution-of-primesReview cycle: annual