Two dates sit behind one of the biggest security worries in computing: spring 1994, when a Bell Labs researcher finished a recipe for factoring huge numbers on a quantum computer, and 2029, the year Google is aiming to finish moving its own systems to quantum-resistant encryption.
The researcher is Peter Shor. New Scientist caught up with him at the Quantum.Tech World conference in Boston, where attendees queued for selfies and signed badges. One onlooker described his algorithm as the one that “will break everything”.
Six months, one problem
Quantum computing was barely on Shor’s radar until he heard Umesh Vazirani lecture at Bell Labs on a problem quantum machines could solve better than any conventional one. The problem was contrived. Shor wondered whether a quantum computer might be good at something practical. Over about six months, ending in the spring of 1994, he found it: factoring very large numbers. He also worked out the steps a quantum computer would follow to do it.
Why does that matter? Most modern encryption, including the RSA scheme behind much of the internet, rests on the difficulty of factoring. RSA multiplies two large primes into a public key and keeps the primes secret. Anyone can encrypt with the public key, but decrypting without the primes means factoring, which classical computers cannot do at that scale. A large, error-corrected quantum computer running Shor’s method could recover the private key. His 1994 paper called its results “the first examples of quantum cryptanalysis”. It covers discrete logarithms as well, so related systems are exposed too.
Not yet, but the clock is running
Today’s machines cannot do it. QuantumAtlas notes that demonstrations have only factored tiny numbers such as 15 or 21, while real keys need thousands of bits and estimates of the logical qubits required run from thousands to millions.
The worry is “harvest now, decrypt later”: data intercepted today could be unlocked once the hardware exists. NIST has already set quantum-proof encryption standards, but New Scientist reported that adopting them is hard and costly, and that banks or hospital systems may need years just to audit their networks. US President Donald Trump recently signed an executive order requiring high-value federal systems to complete the move by 2031.
Shor himself is calm. “We have good methods for post-quantum cryptography, we just have to implement [them],” he said, then added: “This will be incredibly hard.” Of today’s quantum computers he said: “They’re still toys, but they’ll stop being toys very soon.” He does not expect them to help predict the stock market, and sees the useful targets as cryptography, simulating molecules and quantum systems, and some optimisation problems.
The man behind the algorithm
Shor was born on 14 August 1959 in New York City, studied mathematics at Caltech, and earned his Ph.D. at MIT in 1985. He joined AT&T Bell Laboratories the next year. In 2003 he left AT&T for MIT, where he holds the Morss professorship of applied mathematics. The honours include the Nevanlinna Prize and the Gödel Prize, the Dirac Medal in 2017 and the Breakthrough Prize in Fundamental Physics in 2023.
Sources
- Peter Shor’s algorithm could break the internet – but he's not worried | New Scientist
- Shor's Algorithm Explained | QuantumAtlas | QuantumAtlas
- Peter Shor (1959 – ) – Biography – MacTutor History of Mathematics, University of St Andrews
