← 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 needs two enormous primes — hundreds of digits each. There is no formula that hands them to you. Instead you guess, test, and repeat. The only reason this ever finishes is a theorem about how densely primes are scattered among the integers.

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

Drag the slider from small numbers up toward cryptographic sizes and watch the true prime count track the theorem's smooth prediction.

—
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 you're done — in milliseconds.

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.

Without the theorem's guarantee that primes stay this dense, key generation could take longer than the age of the universe. The density is the whole reason RSA is practical.

Where this touches your keys

Every RSA key ever made

Every RSA key generator works by exactly this loop: pick random, test primality, repeat. It terminates quickly for one reason — the Prime Number Theorem promises the primes are there to be found. This is the rare foundation you do lean on every single time.