← Hall of Foundations Exhibit 144 · π(x) ~ x/ln x
The One Foundation That's Genuinely Load-Bearing

How to find a
prime in the dark

RSA key generation commonly samples large candidates and tests for primality. The Prime Number Theorem explains their approximate density and therefore the expected number of attempts. It does not itself prove that a particular candidate is prime or impose a fixed running time.

Unlike the rest of this hall, the Prime Number Theorem is not background structure — it is directly load-bearing. Every RSA key you have ever used exists because primes are common enough to stumble onto by chance.
§1

Primes thin out — but slowly

Among small numbers, primes are everywhere. As you climb, they thin. The Prime Number Theorem pins down exactly how fast: the count of primes below x, written π(x), grows like x⁄ln x. Equivalently, a number near x is prime with probability about 1⁄ln x.

π(x) ≈ x / ln x  ·  density near x ≈ 1 / ln x

The slider shows small, exactly countable ranges. Cryptographic primes are vastly larger; the asymptotic theorem helps explain their density, not a direct enumeration on this screen.

—
Ink dots: the true π(x), counted by sieve. Teal line: the theorem's estimate x⁄ln x. They hug each other — and the fit only improves as x grows.
§2

The keygen coin-flip

Here's the payoff. To make a 2048-bit RSA modulus you need a random 1024-bit prime. The theorem says a random 1024-bit integer is prime with probability about 1⁄ln(2¹⁰²⁴) ≈ 1⁄710. But no keygen routine tests even numbers, and discarding half the candidates doubles your odds: roughly 1 in 355 odd candidates is prime. Sieve out small factors like 3 and 5 first and the rate improves again. So you test a few hundred candidates with a fast primality check, and finish with an expected runtime that depends on the implementation and hardware.

at 1024 bits: ~1 in 710 integers · ~1 in 355 odd candidates

Keep the claim narrow: this theorem explains why RSA can find its primes quickly. It says nothing about why factoring their product is hard — that bet is made in The One-Way Function, and the arithmetic that makes the resulting key work is in Euler & Fermat.

Prime density explains why random sampling is practical. Reliable random generation, primality testing, parameter choices and implementation are also necessary; a density theorem is not a complete key-generation algorithm.

Where this touches your keys

Why random prime search is practical

Random sampling with primality testing is a common strategy, but other constructions also exist. The theorem describes asymptotic density; expected runtime depends on candidate filtering, the primality test and the machine.