Shor's Algorithm Explained Step by Step
The problem it attacks
Multiplying two large primes is easy, but recovering them from the product is believed to be hard for ordinary computers. RSA encryption relies on that gap. Shor's algorithm shows that a quantum computer could close it.
The trick: factoring becomes period finding
Mathematicians have long known that factoring a number N can be turned into finding the period of a function: pick a number a, and look at how the sequence a, a squared, a cubed and so on behaves when you only keep remainders after dividing by N. That sequence eventually repeats, and the length of the repeat is the period. Knowing the period lets you compute factors of N with a little classical arithmetic, with good probability. Finding the period is the hard part for classical machines.
What the quantum part does
- Put a register of qubits into an even superposition of many input values at once.
- Compute the function on all of them together, which entangles the input and output registers.
- Apply a quantum Fourier transform, an operation that uses interference so that amplitudes reinforce at values related to the period and cancel elsewhere.
- Measure. The result gives a clue about the period, and the classical computer finishes the job, repeating if the first attempt fails.
It is not "trying every answer at once." The power comes from interference concentrating probability on useful outcomes, a point covered in quantum computing myths.
A useful detail is that the quantum Fourier transform is the same tool that appears in many other quantum algorithms, which is why it is often the first advanced circuit that students study. The overall speedup is considered exponential relative to the best known classical factoring methods, though that comparison is about known algorithms, not a proof that no fast classical method exists.
Beyond RSA
The same period finding idea solves the discrete logarithm problem, which protects elliptic curve cryptography. That matters for many signature schemes, and it is the basis of the discussion in will quantum computers break Bitcoin and Solana.
What hardware it needs
Real keys are enormous, so the circuit is deep and needs very low error rates. Published resource estimates for breaking commonly used key sizes call for a large number of high quality, error corrected qubits, which translates into a very large number of physical qubits, with figures that depend heavily on assumptions and have changed as methods improved. Today's noisy machines are nowhere close. Demonstrations so far have factored only tiny numbers, and some of those used shortcuts that make them poor evidence.
What is still unknown
Nobody can state a reliable date for when this could happen. See the timeline for context. Meanwhile, standards bodies are moving to post-quantum cryptography, and the risk of harvest now, decrypt later is a reason to start early.
Frequently asked questions
Who invented Shor's algorithm?
Peter Shor published it in 1994. It showed that a quantum computer could factor large numbers efficiently.
Has Shor's algorithm broken RSA?
No. Only very small numbers have been factored with quantum hardware, and no machine today is close to the scale needed.
Does Shor's algorithm try all possible factors at once?
No. It uses interference to make the period of a function show up in the measurement, then classical math finishes the job.
Does Shor's algorithm threaten elliptic curve cryptography?
Yes, in theory. A variant solves the discrete logarithm problem that elliptic curve schemes rely on.
Does Shor's algorithm break hash functions?
No. It does not apply to hash functions in that way. Grover's algorithm is the relevant one, with a smaller effect.
How many qubits would it take?
Estimates are large, depend on assumptions and have changed over time. The need is for error corrected qubits, which means many physical qubits each.
Keep reading
- Quantum Algorithms Explained for Beginners
What is a quantum algorithm? Learn how Shor's, Grover's and other quantum algorithms work in plain English, and which ones matter for cryptography and crypto. - What Is RSA and Why Can Quantum Computers Break It?
RSA encryption relies on the difficulty of factoring big numbers. Learn how RSA works in plain English and why a large quantum computer could break it. - Grover's Algorithm Explained Step by Step
How does Grover's algorithm work? Learn amplitude amplification, why the speedup is only quadratic, and what it really means for keys and hashes. - Post-Quantum Cryptography and Crypto: What It Means
Why large quantum computers could threaten blockchain signatures, and what post-quantum cryptography is doing about it.
All Quantum computing guides | Back to top | Search the site
Main pages: Quantum computing explained | Quantum and crypto | Companies | Quantum news | Glossary