Shor's algorithm: the quantum proof that gave RSA a deadline
The phone rang on a weekend in April 1994, at the home of a mathematician with a cold. Peter Shor, a researcher at Bell Laboratories in Murray Hill, New Jersey, picked up to find Umesh Vazirani on the line with some news: the Berkeley computer scientist had heard, through what Shor later called “a game of telephone,” that Shor had solved the integer factorization problem on a quantum computer. The trouble was, Shor hadn’t — not yet. That Tuesday he had given a seminar talk about solving a different but related problem, the discrete logarithm. Someone at the talk told someone else, who told someone else, until the story arrived at Vazirani’s ear having grown considerably in the telling.
Shor took the call, reflected on it, and then worked out factoring.
The algorithm he published that year — first presented at the 35th Annual Symposium on Foundations of Computer Science in Santa Fe, New Mexico, in November 1994 — did something that no one had thought possible. On a quantum computer, it factored large integers in polynomial time.
This matters because RSA, the encryption scheme that at that moment was securing every sensitive internet transaction on the planet, works on one assumption: that multiplying two enormous prime numbers together takes a fraction of a second, but reversing that — recovering the primes from their product — would take a classical computer longer than the age of the universe. Shor showed that a sufficiently large quantum computer could do the reverse in a time that scales as roughly the cube of the input’s length, not exponentially. The assumption on which RSA rested dissolved.
The mechanism turns on a property that quantum computers handle naturally: periodicity. Finding the factors of a number, Shor showed, is equivalent to finding the period of a particular function — and a quantum Fourier transform can find that period exponentially faster than any classical technique. The math is elegant; the implications were seismic.
Seven years later, on December 20, 2001, a team at IBM’s Almaden Research Center in San Jose factored the number fifteen into three and five using a seven-qubit quantum computer — the architecture built from nuclear magnetic resonance, the qubits encoded in atoms of a custom-synthesized molecule dissolved in a test tube. The result, published in Nature, was almost comic in its modesty: fifteen equals three times five, a fact any five-year-old knows. But proving it with a quantum device, following Shor’s procedure exactly, was then the most complex quantum computation ever executed.
The IBM demonstration made a point that needed making. The threat was no longer theoretical in the way theoretical threats usually are — sitting safely in a paper, waiting on hardware that might never exist. The hardware existed. It was tiny. It would grow.
NIST took the hint, if belatedly. In 2016 the agency opened a competition to identify encryption algorithms that would survive a large quantum computer. By 2024 it had standardized three new post-quantum schemes — including the lattice-based CRYSTALS-Kyber for key exchange and CRYSTALS-Dilithium for signatures — none of which rely on factoring or discrete log, and none of which Shor’s algorithm touches.
The full transition is set for 2035. Three decades after a mathematician picked up a phone with a cold and worked out the problem he’d accidentally been credited for, the internet is rebuilding its locks.
Sources
- Shor’s algorithm — Wikipedia — development timeline, FOCS 1994 presentation, the 2001 IBM NMR demonstration, and the seven-qubit result published in Nature.
- arXiv:quant-ph/9508027 — Shor’s original paper — “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” AT&T Research, 1994/1995; establishes polynomial-time factoring on a quantum computer.
- Science News: Shor’s code-breaking algorithm — the Vazirani telephone anecdote and context of the April 1994 seminar where Shor first presented his discrete logarithm result.