What is Shor's algorithm?
Shor's algorithm is a quantum algorithm, published by the mathematician Peter Shor in 1994, that can find the prime factors of large numbers and solve a related problem called the discrete logarithm dramatically faster than any known method on an ordinary computer. Those two problems are what keep RSA and elliptic-curve cryptography secure, so a large enough quantum computer running Shor's algorithm would break them.
Why factoring matters
Multiplying two large prime numbers is easy. Splitting the result back into its primes is extraordinarily hard: for numbers hundreds of digits long, the best known ordinary methods would take far longer than the age of the universe. RSA relies on that one-way difficulty. Elliptic-curve cryptography, which protects most modern secure connections, relies on a related problem that Shor's algorithm also solves.
How it works, in one paragraph
Shor's insight was to turn factoring into a problem of finding a repeating pattern, the period of a particular sequence of numbers. An ordinary computer has to hunt for that period step by step. A quantum computer can set up a superposition over many possibilities and use interference to make the right period stand out, so that measuring the qubits reveals it with high probability. Ordinary arithmetic then turns the period into the factors. The superposition lesson explains interference with small numbers.
What it breaks, and what it doesn't
- Breaks: RSA, through factoring, and elliptic-curve cryptography and Diffie-Hellman key exchange, through their discrete-logarithm problems. Together they cover most of today's key agreement, signatures and certificates.
- Doesn't break: symmetric encryption such as AES, or hash functions. Those face a much weaker speed-up from Grover's algorithm.
- Doesn't break (as far as anyone knows): the new post-quantum standards such as ML-KEM, which are built on mathematical problems that Shor's algorithm doesn't solve.
Can it be run today?
Not at a scale that matters. Demonstrations on real hardware so far have factored only very small numbers. Running Shor's algorithm against 2048-bit RSA needs a cryptographically relevant quantum computer. Published designs use over a thousand error-corrected logical qubits running for days. One 2025 model by Google researcher Craig Gidney put that at under a million noisy physical qubits, around twenty times fewer than his 2019 estimate with Martin Ekerå, under its own assumptions about error rates and hardware speed. These are estimates, not hardware specifications. Today's machines have hundreds to low thousands of physical qubits.
Shor's algorithm is the single biggest reason banks and governments pay attention to quantum computing.
Common confusions
- "Shor's algorithm tries every factor at once." No. It uses interference to reveal a hidden pattern. Trying every answer and reading one at random would be no better than guessing.
- "A small demo means RSA is nearly broken." Factoring tiny numbers, often with shortcuts, says little about 2048-bit keys.
- "It breaks all encryption." It breaks today's public-key methods. That's serious enough, but it's a defined scope with defined replacements.
Sources and further reading
Tags show what kind of source each one is (how sources are used). Checked against these sources on 12 October 2026. Spotted an error? Email hello@plainquantum.com and it will be corrected, with a note.
- Peer-reviewed paperPolynomial-time algorithms for prime factorization and discrete logarithms on a quantum computerPeter Shor, SIAM Journal on Computing, 1997
- Peer-reviewed paperHow to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubitsCraig Gidney and Martin Ekerå, Quantum, 2021
- PreprintHow to factor 2048 bit RSA integers with less than a million noisy qubitsCraig Gidney, 2025