Shor's Algorithm
Shor's algorithm is a quantum algorithm that finds the prime factors of a whole number (for example, 15 = 3 × 5) far faster than any known normal method. It works by turning factoring into a search for a repeating pattern, called period finding, which a quantum computer solves with the quantum Fourier transform. The math is sound, and it is the reason new "post-quantum" encryption exists. But real hardware has only ever factored toy numbers like 15 and 21, and breaking RSA-2048 needs an error-corrected machine that does not exist today.
| Task | Best classical | Quantum |
|---|---|---|
| Factor an n-bit integer | exp(O(n^(1/3) (log n)^(2/3))) — general number field sieve, sub-exponential | O(n^3) gates with schoolbook arithmetic, ~O(n^2 log n) with fast multiplication (theory, fault-tolerant) |
| RSA-2048 in practice | Infeasible — vastly beyond all computing power on Earth | 2025 estimate: under a million noisy physical qubits running for about a week — a machine ~1,000x larger and far cleaner than anything that exists; earlier estimates said 20 million, so treat all such numbers as moving targets |
What problem does Shor's algorithm solve?
Factoring means taking a number N = p × q and finding p and q. For small numbers it is easy: 15 = 3 × 5. For huge numbers it is very hard. RSA encryption, which protects a lot of internet traffic, depends on it being impossible for 2048-bit numbers. (A 2048-bit number has about 617 digits.) Older elliptic-curve encryption falls to a close cousin of the same algorithm, which solves a related problem called discrete logarithms.
So Shor's algorithm is the most important single result in quantum computing. It is also the most misreported. "Could break RSA" is true, given hardware that doesn't exist. That often gets shortened to "breaks RSA," which is false today.
Here is the exact status: the theory is sound, it has only been shown on toy numbers, and it can't threaten any real key today. The real near-term worry is called "harvest now, decrypt later." Someone could record encrypted messages today and decrypt them years from now. That is why the move to post-quantum cryptography (encryption designed to resist quantum attacks) is already happening. NIST, the U.S. standards agency, approved the first of these methods in 2024.
How would a normal computer factor a number?
The best known normal method is called the general number field sieve. It is faster than trying every divisor, but its cost still explodes as numbers grow. The current record is RSA-250, a number 829 bits long. It was factored in 2020 using roughly 2,700 core-years. That means one computer core would need about 2,700 years. Each extra bit makes the job harder, and RSA-2048 is far beyond any normal effort we can imagine.
Notice the words best known. No one has ever proven factoring is hard. It sits in a sweet spot. People believe it is hard for normal computers. It is proven to be easy for an error-corrected quantum computer.
How does Shor's algorithm work?
Number theory does most of the work. Here are the steps:
- Pick a random number a that shares no factors with N.
- Look at the list a¹, a², a³, … mod N. ("Mod N" means keep only the remainder after dividing by N, like hours wrapping around on a clock.)
- This list repeats every r steps. We call r the period.
- If r is even, the numbers gcd(a^(r/2) − 1, N) and gcd(a^(r/2) + 1, N) usually give the factors. (gcd means greatest common divisor, the biggest number that divides both.)
Let's work it out for a = 7 and N = 15.
- 7¹ = 7. Remainder after dividing by 15: 7.
- 7² = 49. 49 − 45 = 4.
- 7³ = 343. 343 − 330 = 13.
- 7⁴ = 2,401. 2,401 − 2,400 = 1.
- Then it starts over: 7, 4, 13, 1, 7, 4, …
The period is r = 4. Half of that is 2, and 7² = 49. So gcd(49 − 1, 15) = gcd(48, 15) = 3, and gcd(49 + 1, 15) = gcd(50, 15) = 5. Factored: 15 = 3 × 5.
For huge numbers, finding r with a normal computer is as hard as factoring itself. The quantum part does exactly one job: it finds the period.
Here is how. One set of qubits is put in a superposition over all the powers x. A second set computes a^x mod N for each one, and the two sets become entangled. This leaves the first set in a repeating state with spacing r. Then a QFT turns that period into peaks you can measure, at multiples of 2ⁿ/r. A normal math step called continued fractions recovers r from one peak.
Think of a song with a steady beat. You can't hear the beat from a single note, but an equalizer can pick out the rhythm. Unlike a song, you only get one sample per run. So the circuit is set up to make that one sample land on the rhythm. There is no "trying all answers at once." The answer shows up because interference cancels every result that doesn't match the period.
Run it: the readout step, honestly labeled
What does the toy version leave out?
Everything expensive. The real algorithm computes a^x mod N in superposition. That takes reversible arithmetic, which uses up most of the qubits and gates. For RSA-2048, it means thousands of logical qubits (error-corrected qubits, each built from many physical ones) and billions of error-corrected steps. That is why every cost estimate assumes full error correction.
The 3-qubit demo skips that by setting up the repeating state by hand. We started the pattern at offset 1. The offset doesn't move the peaks. That is exactly why the algorithm can read the period without ever learning the offset.
The same shortcut spoils most hardware "demos of Shor." Published factorings of 15 and 21 used circuits simplified with knowledge of the answer. A 2013 paper (Smolin, Smith & Vargo, "Oversimplifying quantum factoring") showed that such shortcuts can "factor" any large number while proving nothing. Keep that in mind with any headline about factoring records.
What are its limits?
- Error correction is a must. For numbers that matter in encryption, the circuit is billions of steps deep. Without error correction, the quantum state falls apart almost at once. See circuit depth and width.
- Cost estimates keep changing. A widely cited 2019 estimate for RSA-2048 was about 20 million noisy qubits for 8 hours. A 2025 estimate cut that to under one million qubits for about a week. Both assume error rates and links between chips that no machine has. Falling estimates are real progress in algorithms and error-correcting codes. They are not hardware progress.
- Only some encryption falls. Shor breaks RSA, Diffie–Hellman and elliptic curves. It does not break AES. (Grover's search only makes a small, quadratic dent there.) It also doesn't break the lattice-based methods NIST approved in 2024.
How does Shor's algorithm do on hardware today?
Real period finding, with no shortcuts, has been done only for the smallest cases. The number 15 was done in work from around 2012 with real modular arithmetic. Most other records used shortcuts.
Today's largest chips have roughly a thousand physical qubits, with error rates around 10⁻³ (about 1 mistake in 1,000 steps). RSA-2048 estimates assume millions of physical qubits at 10⁻³ or better, plus full error correction. See current QPUs and how to read the specs.
Vendor roadmaps aim for useful error correction around 2029–2033. Those are roadmap claims, not demonstrations. The honest summary: Shor's algorithm is why the switch to new encryption started now. Nothing more urgent than that.