240 BC to this monthHistory

43 events. Teal dots are the classical story — sieves, congruences, records. Rose dots are the quantum one. Violet dots are Riemann's: the count of the primes, and the hypothesis that sits under the whole subject without ever touching a key.

classical · 22 quantum · 14 Riemann · 7

• about 240 BCEratosthenes of Cyrene

  The sieve: write the numbers out, strike every second one after 2, every third after 3, and what is left standing is prime. Still the fastest way to list the small primes, and still the first move in every big factoring run. [1]

• 1643Pierre de Fermat

  A number that is the difference of two squares splits at once: a² − b² = (a − b)(a + b). Fermat shows Mersenne how to walk a up from the square root until a² − N is a square. It is quick when the two factors are close together and hopeless when they are not — which is exactly why key generators keep them far apart. [2]

• 1732Leonhard Euler

  Fermat had guessed that 2^(2^n) + 1 is always prime. Euler splits the fifth one: 4,294,967,297 = 641 × 6,700,417. He did it by knowing, from Fermat's own little theorem, that any factor had to have the form 64k + 1, so he only had to try a handful. [3]

• 1801Carl Friedrich Gauss

  In the Disquisitiones, article 329: telling primes from composites and splitting the composites is 'one of the most important and useful in arithmetic', and 'the dignity of the science itself seems to require that every possible means be explored'. He lists two methods of his own. Nobody had a fast one. [4]

• 1859Bernhard Riemann

  An eight-page paper on how many primes there are below a given size. The count is tied to the zeros of one function, ζ(s), and Riemann remarks that all the zeros he has looked at sit on one line and that it is 'very probable' they all do. He does not prove it. Nobody has. [5]

• 1896Jacques Hadamard and Charles de la Vallée Poussin

  The Prime Number Theorem, proved twice in one year: the count of primes up to x runs like x divided by the natural log of x. The proof goes through Riemann's zeros — showing none of them sit on the edge of the strip. So there are plenty of primes of any size you want, and picking two big ones is cheap. [6]

• 1900David Hilbert

  The Riemann Hypothesis is the eighth of his twenty-three problems for the century. Asked what he would do if he woke after five hundred years, Hilbert is said to have answered: ask whether it had been proved. [7]

• 1926Maurice Kraitchik

  The trick every modern method rests on: you do not need N itself to be a difference of two squares. It is enough to find x² ≡ y² (mod N), two numbers whose squares leave the same remainder. Then N divides (x − y)(x + y), and half the time gcd(x − y, N) is a factor. Kraitchik collects such congruences and multiplies them together until the product is a square. [9]

• 1926–1933D. N. Lehmer and D. H. Lehmer

  Sieving machines: first bicycle chains on a shaft, then a photo-electric sieve with gears and a beam of light, testing thousands of candidates a second for whether they leave the right remainders. The first factoring hardware. [8]

• 1950Alan Turing

  On the Manchester Mark 1, one of the first stored-program computers, Turing checks that the zeros of ζ up to a certain height all sit on Riemann's line. He was hoping to find one off it. He did not. Every computation since — now past the first ten trillion zeros — has found the same. [10][41]

• 1970Michael Morrison and John Brillhart

  The continued-fraction method, run on an IBM 360/91, splits the seventh Fermat number: 39 digits, unfactored since 1732. The first factoring record set by a computer using a method built for computers. [11]

• 1974–1975John Pollard

  Two cheap methods in two years. The p − 1 method catches a factor p when p − 1 is made of small primes. The rho method walks a pseudo-random path through the numbers mod N and waits for it to loop; it finds a factor p in about √p steps, which for a 20-digit N is a few thousand steps on a laptop instead of a few billion. [12][13]

• 1976Gary Miller

  A fast, certain test for whether a number is prime — provided the Generalised Riemann Hypothesis is true. Without it the same test is fast and almost certain (Rabin's 1980 version), which is what every key generator uses. This is the closest the Riemann Hypothesis comes to cryptography: it would guarantee a primality test, not speed up any factoring. [14]

• 1977Ron Rivest, Adi Shamir and Leonard Adleman

  RSA: pick two big primes, publish their product N and a number e, keep the primes secret. Anyone can lock a message with (N, e); only someone who knows the primes can unlock it. The whole scheme rests on one bet — that splitting N is far harder than making it. Martin Gardner's column prints a 129-digit N and offers $100 to whoever splits it; Rivest guesses forty quadrillion years. [15][16]

• 1981John Dixon

  Kraitchik's idea with a proof attached: pick random x, keep the ones whose x² mod N breaks into small primes, and linear algebra over the parities finds a product that is a square. The first factoring method with a rigorous sub-exponential running time. [17]

• 1981Carl Pomerance

  The quadratic sieve: instead of testing each candidate x² − N for small factors one by one, sieve them all at once, the way Eratosthenes did — a factor p divides every p-th value in the row. Ten to a hundred times faster than the continued-fraction method for the same size, and the record holder for the next decade. [18][19]

• 1985Hendrik Lenstra

  The elliptic curve method: Pollard's p − 1 idea, but on a curve you can change if the first one does not work. Its cost depends on the size of the factor it finds, not the size of N, so it is the tool for pulling a 30-digit factor out of a 300-digit number. Also the first serious use of the curves that a Bitcoin wallet key lives on. [20]

• 1988–1990John Pollard, then the Lenstra brothers and Mark Manasse

  The number field sieve. Pollard's letter proposes sieving in a bigger number system than the integers; two years later the ninth Fermat number (155 digits) falls to it. The general version for numbers of no special form arrives in 1993 and is still, in 2026, the fastest method known for RSA-size numbers. [21][22]

• 1991RSA Laboratories

  The RSA Factoring Challenge: a list of numbers from 100 to 617 digits, each the product of two primes, with cash for each one split. The list becomes the yardstick everyone measures against. [29]

• April 1994Derek Atkins, Michael Graff, Arjen Lenstra, Paul Leyland and about six hundred volunteers

  Gardner's 129-digit number falls after eight months of spare time on computers around the world, by the quadratic sieve. The message inside: THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE. Rivest's forty quadrillion years lasted seventeen. [23]

• 1994Peter Shor

  A quantum computer, if one could be built, could split any N in a number of steps that grows like a small power of its length instead of exponentially. The quantum part finds the period of a^x mod N; the rest is Euclid. Every serious estimate of when RSA and wallet keys fall is an estimate of when a machine can run this. [42]

• August 1999Stefania Cavallar and a team of seventeen

  RSA-155, the first 512-bit number, by the number field sieve: about seven months, on the order of eight thousand MIPS-years. 512-bit keys were still in wide use. [24]

• December 2001Lieven Vandersypen and the IBM Almaden group

  Shor's algorithm runs on hardware for the first time: seven nuclear spins in a molecule, and 15 comes out as 3 × 5. The circuit was 'compiled' using knowledge of the answer, which every hardware demonstration since has also done. [43]

• 2002–2004Manindra Agrawal, Neeraj Kayal and Nitin Saxena

  PRIMES is in P: a fast, certain primality test with no hypothesis attached. Telling prime from composite is now settled and easy. Splitting a composite is not, and this result says nothing about it. [33]

• December 2009Thorsten Kleinjung and twelve others

  RSA-768, 232 digits: about two thousand years of a single 2.2 GHz core, spread over two and a half years of wall time. The team's own estimate: a 1024-bit key is about a thousand times harder and 'may be feasible' within a decade with the same effort. [25]

• 2012Enrique Martín-López and the Bristol group

  21 = 3 × 7 with photons and a recycled qubit. Still, in 2026, the largest number split by Shor's algorithm on a physical machine without the answer built into the circuit — and this one was compiled too. [44]

• 2012Austin Fowler, Matteo Mariantoni, John Martinis and Andrew Cleland

  The first careful bill for breaking a 2000-bit key on a surface-code machine: on the order of a billion physical qubits, about a day. The number every later estimate is measured against. [50]

• 2013John Smolin, Graeme Smith and Alexander Vargo

  'Oversimplifying quantum factoring': if you compile the circuit with the answer in hand, you can 'factor' any number at all with two qubits. The small demonstrations prove the hardware can hold a few qubits, and nothing about scaling. [47]

• 2015Nadia Heninger's group at Penn; the Logjam team

  'Factoring as a service': a 512-bit RSA key split in four hours on rented cloud machines for $75 — and hundreds of such keys still in use in mail and DNS. The same year, Logjam shows 512-bit Diffie-Hellman falling to a week's precomputation. Old key sizes do not retire themselves. [32][31]

• May 2019Craig Gidney and Martin Ekerå

  The bill drops fifty-fold: 2048-bit RSA in eight hours on twenty million noisy qubits, given a physical error rate of one in a thousand. A model, not a machine — nothing had a thousandth of that. [51]

• December 2019Fabrice Boudot, Pierrick Gaudry, Aurore Guillevic, Nadia Heninger, Emmanuel Thomé and Paul Zimmermann

  RSA-240 (795 bits) with the open-source CADO-NFS, about nine hundred core-years, in the same run as a 240-digit discrete logarithm. The two problems, factoring and discrete log, turn out to cost about the same. [26]

• February 2020The same six

  RSA-250, 829 bits, 2,700 core-years of a 2.1 GHz Xeon. It stood as the record for six and a half years. [27][26]

• March 2021Claus Peter Schnorr

  A preprint whose abstract says 'This destroys the RSA cryptosystem.' It did not split any challenge number, the claim was withdrawn in a revision, and later work found the method stops working past about 80 bits. The template for the next few years of headlines. [53][103]

• December 2022Bao Yan and twenty-three others

  A preprint says 372 qubits could 'challenge RSA-2048', by bolting Schnorr's method to a small quantum optimiser. The hardware run split a 48-bit number. Scott Aaronson: 'cargo cult quantum factoring'. The classical step does not scale, and the number 372 still circulates. [54][55]

• August 2023Oded Regev

  The first real improvement to Shor's algorithm in thirty years: a multi-dimensional version with about √n fewer gates for an n-bit number, at the price of more qubits. Ragavan and Vaikuntanathan bring the qubit count back down within months. [56][57]

• May 2024Larry Guth and James Maynard

  The first improvement since 1940 on how many zeros can sit off Riemann's line in a given range. Progress toward the Hypothesis, not a proof of it, and no change to any factoring method. [39]

• August 2024NIST

  The first three post-quantum standards are final: ML-KEM for key exchange, ML-DSA and SLH-DSA for signatures. Three months later a draft transition plan: RSA-2048 and 256-bit curves deprecated after 2030, disallowed after 2035. [63][64]

• December 2024Google Quantum AI

  Willow: 105 superconducting qubits, and for the first time a logical qubit that gets better as the code gets bigger — the 'below threshold' result the field had waited for since 1996. One logical memory, no logical gates. [62]

• May 2025Craig Gidney

  The bill drops twenty-fold again: 2048-bit RSA with fewer than a million noisy qubits, in under a week. Same error-rate assumption as 2019; the savings are in the arithmetic and the error correction. [58]

• February 2026Iceberg Quantum

  The 'Pinnacle' architecture: RSA-2048 with fewer than 100,000 physical qubits, on a newer family of error-correcting codes that needs long-range wiring nobody has built. Aaronson: 'I have no idea by how much this shortens the timeline.' [88][89]

• March 2026Ryan Babbush, Craig Gidney, Dan Boneh and colleagues at Google, Stanford and the Ethereum Foundation

  The wallet bill: a 256-bit curve key with fewer than 500,000 physical qubits, in minutes, on a fast superconducting machine. Google withholds the circuits and publishes a proof they work. The same week, Caltech puts a slower neutral-atom version at ten thousand atoms and about ten days per key. [91][92][93]

• April 2026Giancarlo Lelli; Project Eleven

  A 15-bit curve key recovered on IBM cloud hardware wins the one-bitcoin Q-Day Prize. Within a day, Bitcoin developers reproduce the 'recovery' with random bits, since 32,767 candidates can be checked by hand. Project Eleven's own CEO: this 'is not Q-Day'. [95][96]

• September 2026Eric Lu (Cognition); Stephen Weis (Anthropic)

  Two classical records in one month, both by porting CADO-NFS to data-centre GPUs with AI coding agents: RSA-260 (862 bits) on the 3rd, about 4,900 GPU-days; RSA-896 (896 bits) on the 19th, about 30 GPU-years of idle time in ten days. Both authors say the same thing: no new mathematics, and no effect on 2048-bit keys. [99][101]

What the story adds up to