The story
In 1994 Peter Shor, a mathematician at Bell Labs, showed that a quantum computer could factor large numbers into primes in a reasonable amount of time. He presented the result that year and published it in full in 1997. It startled cryptographers, because the security of much of the internet rests on the assumption that factoring a very large number is practically impossible.
Public-key systems such as RSA, invented in 1977, publish a number that is the product of two huge primes and rely on nobody being able to split it. The best known methods on ordinary computers take time that grows explosively with the size of the number. Shor's algorithm uses quantum mechanics: a quantum computer's bits (qubits) can be placed in superpositions, so one operation acts on many values at once. He reduced factoring to finding the repeating period of a certain function, then used the quantum Fourier transform, a quantum version of the method for finding frequencies in a signal, so that wrong answers cancel out and the right period stands out. A version also breaks the discrete logarithm problem behind Diffie-Hellman and elliptic-curve cryptography. In 2001 IBM researchers ran it on a seven-qubit machine to factor 15. Breaking real encryption needs vastly better hardware.
Why it mattered
- Governments and companies began researching post-quantum cryptography, and in 2024 NIST published its first standards for algorithms meant to resist quantum attack.
- Funding and interest in quantum computing rose, since Shor's result showed a concrete payoff.
- Quantum error correction developed rapidly, starting with Shor's own 1995 code, because large algorithms need reliable qubits.
- Security planners worry about attackers storing encrypted data now to decrypt it once quantum computers mature.
Sources
- How a quantum computer could break 2048-bit RSA encryption in 8 hours MIT Technology Review
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer arXiv
- NIST Releases First 3 Finalized Post-Quantum Encryption Standards NIST
- Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance arXiv
Drafted by AI (Claude) from the sources above and checked against them by AI; no historian has reviewed this page. Spot a mistake? Suggest a correction. How pages are made
Community notes
Loading notes…