Shor's Algorithm
Shor's algorithm factors integers in polynomial time by converting factoring into period finding, which a quantum computer solves with the quantum Fourier transform. It is mathematically sound and the reason post-quantum cryptography exists — but on real hardware it has only ever factored toy numbers like 15 and 21, and breaking RSA-2048 requires a fault-tolerant 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: given N = p × q, find p and q. RSA encryption rests on this being infeasible for 2048-bit numbers, and older elliptic-curve schemes fall to the same algorithm via a variant for discrete logarithms. So Shor's algorithm is the single most consequential result in quantum computing — and also the most misrepresented, because "could break RSA" (true, given hardware that doesn't exist) routinely gets compressed to "breaks RSA" (false today).
The precise status: theoretically sound, demonstrated only for toy numbers, practically incapable of threatening any real key today. The realistic near-term concern is "harvest now, decrypt later" — recorded encrypted traffic decrypted years from now — which is why the migration to post-quantum cryptography (NIST standardized the first algorithms in 2024) is already underway.
The classical approach
The best known classical algorithm, the general number field sieve, is sub-exponential but still explosive: the current record is RSA-250 (829 bits), factored in 2020 using roughly 2,700 core-years. Each additional bit multiplies the cost, and RSA-2048 is far beyond any conceivable classical effort.
Note the phrase best known: factoring has never been proven hard. It sits in a complexity sweet spot — believed hard classically, provably easy for a fault-tolerant quantum computer.
The quantum approach: factoring becomes period finding
The number theory does most of the work. Pick a random a coprime to N and consider the sequence a¹, a², a³, … mod N. It repeats with some period r, and if r is even, gcd(a^(r/2) ± 1, N) usually yields the factors. Concretely for a = 7, N = 15: the sequence 7, 4, 13, 1, 7, 4, … has period r = 4, and gcd(7² − 1, 15) = 3, gcd(7² + 1, 15) = 5. Factored.
Finding r classically is as hard as factoring. The quantum part does exactly one thing: it finds the period. A register in superposition over all exponents x is entangled with a^x mod N computed in a second register; this leaves the first register in a periodic state with spacing r, and a QFT converts that period into measurable peaks at multiples of 2ⁿ/r. A classical continued-fractions step recovers r from one peak. No "trying all answers at once" — the answer emerges because interference cancels every outcome that does not match the period.
Run it: the readout step, honestly labelled
What the toy leaves out
Everything expensive. The real algorithm computes a^x mod N in superposition — reversible modular arithmetic that dominates the qubit and gate count. For RSA-2048 that means thousands of logical qubits and billions of error-corrected operations, which is why every resource estimate assumes full fault tolerance. The 3-qubit demo skips it by preparing the periodic state by hand; the offset of the prepared pattern (we used offset 1) doesn't move the peaks, which is exactly why the algorithm can read the period without ever learning the offset.
The same shortcut infects most hardware "demonstrations of Shor": published factorings of 15 and 21 used compiled circuits simplified using prior knowledge of the answer. A 2013 paper (Smolin, Smith & Vargo, "Oversimplifying quantum factoring") showed such compilations can "factor" arbitrarily large numbers while demonstrating nothing. Treat any headline about factoring records with that in mind.
Limitations
- Fault tolerance is mandatory. The circuit depth for cryptographically relevant N is billions of operations; without error correction the state decoheres almost immediately. See circuit depth and width.
- Resource estimates are moving targets. A widely cited 2019 estimate for RSA-2048 was ~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 interconnects no machine has. Estimates falling is real progress in algorithms and codes — it is not hardware progress.
- Only some problems fall. Shor breaks RSA, Diffie–Hellman and elliptic curves. It does not break AES (Grover gives only a quadratic dent) or the lattice-based schemes NIST standardized in 2024.
On hardware today
Genuine, uncompiled period finding has been done only for the smallest cases (15 in 2012-era work with real modular arithmetic; most other records used shortcuts). Today's largest processors have roughly a thousand physical qubits with error rates around 10⁻³ — compare that with the millions of physical qubits at 10⁻³-or-better plus full error correction that RSA-2048 estimates assume; see current QPUs and how to read the specs.
Vendor roadmaps target useful fault tolerance around 2029–2033. Those are roadmap claims, not demonstrations. The honest summary: Shor's algorithm is why the cryptographic transition started now, and nothing more urgent than that.