Algorithm Zoo · Factoring & cryptanalysis
Shor's Algorithm (Factoring)
First described: Peter Shor, 1994
The problem
Factor an n-bit integer N.
Reduces factoring to order-finding modulo N. Order-finding is solved with quantum phase estimation on the modular-multiplication unitary U|y⟩ = |ay mod N⟩, run on enough qubits to read out the period r with high probability.
Best classical
Sub-exponential O(exp(c · n^{1/3} · (log n)^{2/3})) (GNFS)
Quantum complexity
Õ(n^3) gates, with Õ(n^2) depth using log-depth adders
Our verdict
The single algorithm that justifies post-quantum cryptography migration. No hardware demonstration has factored a non-trivial integer (15 and 21 'demonstrations' from 2001-2012 exploited known structure — see Smolin et al. 2013). Resource estimates still point to many years before RSA-2048 falls. But the threat is real because of harvest-now-decrypt-later: encrypt today, decrypt in 2040.
When to use it
- Cryptanalysis (RSA, finite-field DH, ECC) — the canonical use case that drives PQC migration.
- Modeling and resource estimation when planning Y2Q timelines.
When not to use it
- Anything but cryptanalysis. There's no second application that's been competitive.
- Today's hardware — 2048-bit RSA needs ~20M physical qubits at current error rates (Gidney & Ekerå, 2021).
Classical baseline
General Number Field Sieve is the current champion. 2048-bit RSA is conjectured safe from classical attack for decades; from a sufficiently large fault-tolerant quantum computer, hours-to-days. NIST PQC migration is the policy response.
Hardware cost
Gidney & Ekerå (2021): 2048-bit RSA factored in 8 hours with ~20M physical qubits at 10^-3 error rate. With 2026's best 2-qubit error (≈10^-4 on IonQ Tempo), the count drops but stays >1M qubits.
Key papers
- Algorithms for quantum computation: discrete logarithms and factoring ↗
Shor · 1994 · FOCS '94
- How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits ↗
Gidney, Ekerå · 2021 · Quantum
Deep-dive tutorials
Last verified: 2026-05-24