Why Are Primes the Atoms of Numbers? From Euclid's Proof to RSA Encryption

Prime numbers are called the atoms of numbers because every whole number above 1 can be built by multiplying primes, and in exactly one way. 360 is 2 × 2 × 2 × 3 × 3 × 5 and nothing else, however you start splitting it. This is the fundamental theorem of arithmetic. The same fact explains why primes guard the internet: multiplying two primes is instant, but getting them back from their product can take an enormous amount of computing.

Look at the padlock beside the address in your browser. Behind many of those locks sits one public number, about 617 digits long, made by multiplying two secret primes. Everyone can see the number. Nobody can see the two primes. Why can’t anyone simply find them?

The fundamental theorem of arithmetic

Take 360 and split it: 36 × 10. Keep splitting. 36 is 6 × 6, 10 is 2 × 5, and each 6 is 2 × 3. Now nothing splits any further. The leaves of this factor tree are 2, 2, 2, 3, 3 and 5, so

The numbers that refuse to split, apart from the trivial 1 × itself, are the primes. They are where every branch ends.

But the first split was our choice. Start again with 8 × 45 instead. 8 is 2 × 4, and 4 is 2 × 2; 45 is 5 × 9, and 9 is 3 × 3. The leaves are again 2, 2, 2, 3, 3 and 5. The route changes; the collection at the end does not. That is the theorem: every whole number above 1 is a product of primes in exactly one way, apart from the order of the factors.

The idea is old. Euclid had the key step around 300 BC: in Book VII of the Elements (Proposition 30) he showed that if a prime divides a product of two numbers, it divides one of them. The first complete proof that the factorization is unique came from Carl Friedrich Gauss, in his Disquisitiones Arithmeticae of 1801.

This is also why 1 is not counted as a prime. If it were, 6 could be written 2 × 3, or 1 × 2 × 3, or 1 × 1 × 2 × 3, without end. Leaving 1 out keeps the whole point of the theorem: one number, one collection of primes.

Euclid’s proof that primes never run out

If every number is built from primes, could we run out of them? The gaps between primes do tend to grow, and no list of the primes found so far can settle the question. Euclid settled it with an argument in Book IX, Proposition 20, that still fits on a napkin.

Suppose someone hands you a box that supposedly holds every prime. For a small version, say the box holds 2, 3 and 5. Multiply everything in it: 2 × 3 × 5 = 30. Then add one, to get 31. Divide 31 by 2, by 3 or by 5 and the remainder is always 1, because 30 was divisible by each of them and the extra 1 spoils every division at once. So none of the primes in the box divides 31, and the primes that build 31 must come from outside the box. The same move defeats any finite box, however large. There is always a prime missing.

There is a trap here, and the video stops to let you fall into it. Multiply the first six primes and add one:

It is not. 30,031 = 59 × 509. But neither 59 nor 509 was in the box. Euclid never claimed that the new number is prime, only that its prime factors are new.

Gauss counts the primes

Finding primes is a matter of elimination. In the sieve credited to Eratosthenes you write out the numbers, circle 2 and cross out its other multiples, then do the same for 3, 5 and 7. Below 100, the 25 numbers left standing are the primes. Their spacing shows no obvious rule.

Around 1792 or 1793, Carl Friedrich Gauss, then about fifteen, came at the problem from another side. Decades later, in a letter to the astronomer Johann Encke dated 24 December 1849, he recalled that his book of logarithm tables included a list of primes, and that in idle quarter-hours he had counted them a thousand numbers at a time. Instead of asking where the next prime is, he asked how crowded each stretch is. His answer: near a number N, the density of primes is about 1 / ln N, so the number of primes up to N is roughly N / ln N.

The numbers bear him out, slowly. There are 168 primes below 1,000 and 78,498 below 1,000,000, against an estimate of about 72,382 from N / ln N. The estimate is not exact, but the ratio of the two creeps toward 1 as N grows.

Turning that guess into a theorem took a century. Bernhard Riemann’s paper of 1859 showed where to look, and in 1896 Jacques Hadamard and Charles de la Vallée Poussin independently proved the prime number theorem.

How RSA encryption uses prime numbers

In 1977 Ron Rivest, Adi Shamir and Leonard Adleman at MIT described RSA, a lock that anyone can close but only one person can open. Here is the toy version. Choose two secret primes, 61 and 53. Multiply them and publish the product:

Anyone can use 3233 to lock a message. Opening it depends on knowing the two primes. With a number this small you could find them by hand, so the toy shows the structure, not the protection. Real keys are 2048-bit numbers, about 617 decimal digits long. In February 2020 a team of six researchers factored the 829-bit challenge number RSA-250, and it took about 2,700 core-years of computing.

The other common lock on the web, elliptic-curve cryptography, works differently, but it too does its arithmetic modulo a prime. The widely used Curve25519, for example, is built on the prime 2²⁵⁵ − 19. Different machinery, but primes either way.

The biggest prime and the quantum threat

The largest known primes have a special shape, 2 raised to a power, minus 1: 2³ − 1 = 7, 2⁵ − 1 = 31. On 12 October 2024, Luke Durant, a 36-year-old former NVIDIA employee, confirmed that 2^136,279,841 − 1 is prime. It has 41,024,320 digits. He found it with thousands of cloud GPUs spread over 24 data-center regions in 17 countries, ending a 28-year run of record primes found on ordinary PCs.

Searching for a prime, though, is not what threatens the locks. The threat is the reverse task: recovering prime factors. In 1994 Peter Shor showed that a large enough quantum computer could factor numbers efficiently. Today’s quantum computers are far too small and noisy to do that for real keys. But data stolen today could be stored and decrypted later, once such a machine exists.

So the replacements have started. On 13 August 2024 NIST published its first three post-quantum standards, FIPS 203, 204 and 205. The first two, ML-KEM and ML-DSA, are built on lattices rather than primes; the third, SLH-DSA, is hash-based. Since Chrome 131, released in November 2024, the browser has mixed ML-KEM into its key exchange alongside the elliptic-curve lock.

The atoms of arithmetic still guard most of the internet. Now we are learning to build locks from something else.