Make one, break oneSplit
Multiplying is cheap. Splitting is the whole problem. The box below makes a product of two primes at whatever size you like and then tries to get the primes back, with a live count of the work. Watch the wall arrive.
Make a semiprime, then split it
Trial division tries every odd number up to the square root. Pollard's rho method (1975) walks a pseudo-random path and needs about the square root of the smaller prime — the square root of the square root. At 6 digits both finish. At 12, rho finishes and trial division shows you its projection. At 20 neither finishes, and the projection is the point.
Why there are always enough primes
Making a key means finding two primes of about 309 digits. That only works because primes never run out and never get too thin. The Prime Number Theorem [6] says that near a number x, about one in every ln x whole numbers is prime — ln being the natural logarithm, a number that grows very slowly. So:
| size of the number | about one prime in every |
|---|---|
| 2 digits | 5 |
| 5 digits | 12 |
| 10 digits | 23 |
| 20 digits | 46 |
| 50 digits | 115 |
| 100 digits | 230 |
| 155 digits | 357 |
| 308 digits | 709 |
| 617 digits | 1421 |
At 309 digits, one number in about 709 is prime — and only the odd ones need testing, so one in 354. Pick random numbers, test each with a fast test that can tell prime from not (Miller–Rabin, 1976–1980; certain-if-the-Riemann-Hypothesis-holds in one version, almost-certain in the one everyone uses [14]), and a prime turns up in a few hundred tries. Your browser does it below.
A 2048-bit key, made here
Two 1024-bit primes, found by the same test, multiplied. This is the shape of the key that guards most of the web.
Why the two primes are kept apart
Fermat noticed in 1643 [2] that any odd number is a difference of two squares, a² − b², and that (a − b)(a + b) is then a factorisation. Walk a up from the square root of N and check whether a² − N is a perfect square. If the two primes are close together, a starts near both of them and the walk is short. The primes 10,007 and 10,037 give N = 100,440,259, and Fermat's walk finds them in 1 steps. Key generators keep their two primes far apart for exactly this reason, and one of the 2024 'RSA-2048 broken' papers turned out to have chosen its numbers so that the primes differed in two bits [78].
