Prime Numbers.

A prime number is a whole number greater than one whose only positive divisors are one and itself. Two, three, five, seven, eleven, thirteen — the sequence is so familiar from school that it's easy to forget how strange it gets. Every integer above one is either prime or can be written, uniquely up to order, as a product of primes. That fact has a name — the fundamental theorem of arithmetic — and it is the reason number theorists call primes the atoms of arithmetic. Everything else is built from them.

Euclid proved, around 300 BCE, that there are infinitely many primes. His argument is one of the cleanest in mathematics: assume there are finitely many, multiply them all together, add one. The new number is either prime, or has a prime factor — but it can't be one of the originals, because dividing by any of them leaves a remainder of one. Contradiction. The proof is so short you can write it on a napkin, which is part of why it has survived intact for two thousand years.

What Euclid did not answer is the question every subsequent number theorist has chased: how are the primes distributed? They start dense — every other number near zero is prime or near-prime — and then they thin out, but irregularly. There is a stretch of 33 consecutive composite numbers between 1327 and 1361. There is another stretch of 71 between 31397 and 31469. And then, suddenly, a pair of twin primes: 31, 33; 41, 43. The pattern, if one exists, is hidden underneath what looks for all the world like noise.

This tension — that primes are simple to define and almost impossible to predict — is the engine of most of number theory. It is also, after centuries of incremental progress and a few spectacular breakthroughs, still mostly an open question.

The first serious progress on the distribution question came from a fifteen-year-old. In 1792 or 1793, Carl Friedrich Gauss looked at a table of primes and noticed that they thinned out at a predictable rate — roughly, the number of primes up to x was close to x / ln(x). He scribbled the observation in his notebook, did not publish it, and moved on. Adrien-Marie Legendre announced essentially the same conjecture in print in 1798. Either way, the claim was clear: as you walk up the number line, the primes thin out like the logarithm.

That claim — now called the prime number theorem — sat unproven for nearly a century. The breakthrough came in 1859, when Bernhard Riemann published an eight-page paper titled "On the Number of Primes Less Than a Given Magnitude." Riemann's move was to study a function of a complex variable — the zeta function — whose non-trivial zeros, he argued, controlled the distribution of the primes. The argument was sketchy in places, and Riemann did not finish proving the theorem. But he laid out the machinery that would.

In 1896, two mathematicians — Jacques Hadamard and Charles de la Vallée Poussin — independently filled in the gaps. Both proofs leaned on complex analysis. Both confirmed that the ratio of π(x) (the actual count of primes below x) to x/ln(x) approaches one as x grows. That was the prime number theorem, finally a theorem.

The "elementary" proofs of 1949

For fifty years, mathematicians wondered whether complex analysis was strictly necessary, or whether you could prove the theorem using only real-variable techniques. In 1949, Atle Selberg and Paul Erdős independently produced "elementary" proofs that avoided complex analysis. The proofs are not simpler — most working number theorists would still reach for the analytic version — but they answered a philosophical question about what kind of mathematics the theorem really requires. Donald Newman found a markedly shorter analytic proof in 1980, and it is the one most introductory courses now teach.

What the theorem gives you, practically: a useful estimate, accurate to within a few percent for inputs of any reasonable size. There are about x/ln(x) primes below x. Below a million, that prediction is off by under 8 percent. Below 10²², it's off by less than one part in a billion. The theorem doesn't tell you which numbers are prime — it only tells you, on average, how often they show up. Almost everything that follows in number theory is the search for finer information about that average.

The prime number theorem says the primes thin out like the logarithm. Riemann's hypothesis is a much stronger claim: it pins down, to within an extraordinarily tight error term, exactly where the deviation from that smooth curve can sit. The technical statement is that every non-trivial zero of the Riemann zeta function lies on the line where the real part equals one-half. The consequence — and the reason number theorists care so much — is that if it's true, almost every error bound in analytic number theory tightens.

The Riemann hypothesis is one of the seven Clay Millennium Prize Problems. Six of those remain open. The bounty is a million dollars per problem, but anyone working on it is not, by any measure, in it for the money. It has been called the most important open problem in mathematics, and that is not hyperbole — entire subfields are built around what would follow if it were proved.

The numerical evidence is overwhelming. More than 10¹³ non-trivial zeros have been computed; every single one of them lies on the critical line. But computational evidence is not proof. As any number theorist will tell you, a counterexample needs to be found exactly once, and we have not finished checking.

The 2024 Guth–Maynard result

The first meaningful progress in decades arrived in mid-2024. Larry Guth of MIT and James Maynard of Oxford posted a paper that ruled out a previously plausible class of exceptions to the Riemann hypothesis. The result does not prove the hypothesis — it is, broadly, a stronger upper bound on how many zeros could possibly lie off the critical line. But it is the kind of structural progress that has been notably absent since the 1960s, and it has reanimated a community that had largely settled into the assumption that the problem was indefinitely beyond reach.

Two primes that differ by exactly two — 11 and 13, 41 and 43, 10006427 and 10006429 — are called twin primes. The twin prime conjecture, attributed to Alphonse de Polignac in the 1840s, says there are infinitely many of them. It has resisted proof for nearly two centuries. The reason is that as you walk up the number line, the primes thin out, and twin primes are doubly rare. There is no a-priori reason the supply should be infinite — and no a-priori reason it should run out.

The state of the art on this problem moved more in the decade from 2013 to 2023 than it had in the previous hundred years.

Zhang, 2013

In April 2013, Yitang Zhang — a then-obscure lecturer at the University of New Hampshire — submitted a paper to the Annals of Mathematics. He proved that there is some number N, at most 70,000,000, such that infinitely many pairs of primes differ by less than N. This was the first time anyone had bounded the gap between primes at all. The Annals accepted the paper within three weeks. Zhang gave a talk at Harvard. The number theory community, briefly, went into something close to shock.

The Polymath project

Within weeks of Zhang's announcement, Terence Tao opened a "Polymath" project — an online, public collaboration to drive Zhang's bound down. Anyone could contribute; dozens of mathematicians did. By July 2013, the bound was 4,680. By the time the project closed, it had been pushed below 600.

Maynard, 2014

In November 2013, James Maynard — independently of Zhang and Polymath, and using a different sieve technique — pushed the bound to 600 in a single paper. Combined with subsequent work, the current best published bound is 246. That is: there are infinitely many pairs of primes whose difference is at most 246. Assuming a strong form of the Elliott-Halberstam conjecture, the bound drops to 6.

None of this proves the twin prime conjecture, which is the case N = 2. But the distance from 70,000,000 to 246 — and conditionally to 6 — is the largest single jump on this problem since it was posed.

The honest answer to "what do we know about primes" is: a great deal less than we'd like. A short tour of the open problems makes that concrete.

The pattern in all four: a statement that is easy to write down, intuitively likely, supported by mountains of computational evidence, and persistently beyond the techniques we currently have. This is the texture of prime number research. Progress is measured in epsilons and in centuries.

For most of their history, primes were a pure-mathematics object — beautiful, useless, and proud of it. That changed in 1977, when Ron Rivest, Adi Shamir, and Leonard Adleman published RSA. The trick at the heart of RSA is a simple asymmetry: multiplying two large primes is fast, and factoring their product is, as far as anyone knows, hard. The rest is bookkeeping.

Roughly: pick two primes p and q, each around 1024 bits long. Multiply them to get n. Publish n as your public key. Keep p and q private. Anyone in the world can encrypt a message to you using n, but no one can decrypt it without recovering p and q from n — a problem nobody knows how to solve quickly with a classical computer.

That's the whole edifice. Most of TLS, most of SSH, most of the modern internet's notion of identity, rests on the assumption that factoring 2048-bit semiprimes is too expensive to do at scale. The assumption has held for 49 years. It is also, almost certainly, on a clock.

Two algorithms, two trade-offs

To use RSA, you need to be able to find primes — specifically, to test whether a randomly generated 1024-bit integer is prime. Two algorithms divide that work.

Here is the rough shape of Miller–Rabin in practice — the algorithm that finds the primes your TLS handshake uses every day:

The quantum clock

In 1994, Peter Shor proved that a sufficiently large quantum computer could factor integers in polynomial time. Shor's algorithm is the reason every serious cryptographic standards body has spent the last decade designing replacements for RSA. The threat is not immediate — today's largest quantum computers are still well below the qubit count and coherence time needed to factor a 2048-bit semiprime — but it is real and dated.

A 2025 paper from a Google Quantum AI researcher revised the resource estimate downward: a 2048-bit RSA key could, on the latest accounting, be cracked by a quantum computer with fewer than a million noisy qubits running for less than a week. No such machine exists. None is close. But the trend line is not flat.

NIST has already standardized post-quantum replacements — ML-KEM and ML-DSA were finalized in 2024 — and is advising organizations to migrate to them on a timeline that, depending on who you ask, ends somewhere between 2030 and 2035. RSA is not dead. But for the first time in fifty years, primes are not the only game in town.

On October 12, 2024, a former Nvidia engineer named Luke Durant ran a verification on a 41,024,320-digit number. It passed. The number, 2¹³⁶²⁷⁹⁸⁴¹ − 1, became the 52nd known Mersenne prime — and the largest prime number anyone has explicitly written down.

Durant found it through the Great Internet Mersenne Prime Search (GIMPS), a distributed computing project that has been hunting Mersenne primes since 1996. GIMPS volunteers contribute idle compute to the search; in exchange, the project occasionally finds a new one. M136279841 was the first Mersenne prime discovered using GPUs rather than CPUs. Durant spent roughly a year and $2 million in cloud compute to find it.

Mersenne primes — primes of the form 2ⁿ − 1 — are favored targets for two reasons. First, there is an exceptionally fast primality test for them: the Lucas–Lehmer test runs in time roughly proportional to n², dramatically faster than Miller–Rabin on a number of the same size. Second, when a Mersenne prime 2ⁿ − 1 is found, the number 2ⁿ⁻¹(2ⁿ − 1) is automatically a "perfect number" — equal to the sum of its proper divisors. Euclid noticed the connection. Euler proved it goes both ways for even perfect numbers. Whether there are any odd perfect numbers is another open question.

What the chase is actually for

The largest-prime records are not used for anything. RSA needs primes of around 1024 bits, which is comically smaller than 41 million digits. The 52nd Mersenne prime will not encrypt your email or sign your software updates. It exists in the public record because it is the largest specific number that humans have proved to be prime — and because some questions are interesting on their own terms.