Primes thin out at a rate you can name
Near a 1024-bit number, one odd number in 355 is prime. That is not a small chance, which is the only reason public-key cryptography is possible.
There are 25 primes below 100, 168 below 1000, and 78,498 below a million. The counts fall away, but they never stop, and the rate at which they thin is one of the most useful facts in mathematics.
One in ln n
Near a number n, roughly one number in ln n is prime. Below 100 that predicts 100 / ln 100 = 21.7 primes, and Prime Sieve prints exactly that next to the true count of 25, along with the 13.1% error.
The estimate is crude here and it improves. At a million, N / ln N gives 72,382 against the true 78,498, an error of 7.8%. The relative error shrinks as N grows, which is the actual content of the prime number theorem.
The better estimate that looks worse
The tool prints a second approximation, Li(N), the logarithmic integral. At N = 100 it gives 29.1 and it is worse than the crude one: a 16.3% error against 13.1%.
Anyone reading only that row would conclude the fancier formula is not worth having. Change N and the ranking inverts and never comes back:
- N = 100: N/lnN off by 13.1%, Li off by 16.3%
- N = 1000: N/lnN off by 13.8%, Li off by 5.1%
- N = 10⁶: N/lnN off by 7.8%, Li off by 0.16%
Li is not a refinement of N / ln N so much as the honest version of it. The crude formula applies the density at n to the whole range from 0 to n, when the density near 2 is very different from the density near a million. Li integrates 1/ln t across the range instead of assuming it constant, and the payoff is an error of one part in six hundred where the shortcut is still wrong by 8%.
A single evaluation of an approximation tells you nothing about whether it is good. You need its behaviour as the input grows.
Why they never run out
Because 1/ln n falls slowly. Its sum diverges, so the primes are thin but not thin enough to be finite.
Euclid's proof is more direct and older. Take any finite list of primes, multiply them together, add one. The result leaves remainder 1 when divided by any prime on the list, so its prime factors are all missing from your list. No finite list can be complete.
The tool's other two readouts point at how much is still open. It counts 8 twin pairs below 100 and reports the largest gap as 8. Whether the twin pairs run on forever is unproven, and so is the conjecture that a prime always sits between consecutive squares.
The number that sizes a key
Generating an RSA key means finding large primes, and the method is to pick a random odd number of the right size and test it.
How long that takes is exactly the density question. A 1024-bit number is near 2¹⁰²⁴, and ln(2¹⁰²⁴) = 1024 × ln 2 = 710. So about one number in 710 near there is prime, and since you only ever test odd candidates, one in 355.
Three hundred and fifty-five trials, each a fast probabilistic primality test. That is why key generation takes a moment rather than a geological age, and the entire schedule comes from a logarithm. Push the exponent up and the cost grows linearly in the bit length, which is why 2048-bit and 4096-bit keys remain practical.
Had the primes thinned even slightly faster, say as 1/n, the search would be hopeless and the internet would be built on something else.
Nobody proves the primes they use
One detail makes the 355 trials cheap: the test does not establish primality.
Miller-Rabin picks a random witness and asks a question that every prime answers one way. A composite can answer like a prime, but at most a quarter of the possible witnesses will let it, so each independent round cuts the chance of being fooled by at least four. Forty rounds leave a worst case below 4⁻⁴⁰, which is around 10⁻²⁴.
That is far below the probability of an undetected memory error in the machine doing the arithmetic. The keys protecting the world's traffic rest on numbers that are almost certainly prime, and the residual doubt is smaller than the hardware's.
Watch
References (1)
- the test behind the 355 trials Rabin (1980). Probabilistic algorithm for testing primality. Journal of Number Theory 12(1).