Shor's Factoring Algorithm
Factoring reduces to period finding, and period finding is quantum-easy.
Multiply two 300-digit primes and you get a number nobody on Earth can factor: the best classical algorithms take time that grows almost exponentially with the number of digits. In 1994 Peter Shor showed that a quantum computer could factor in polynomial time. The quantum part is the phase estimation you already know; the rest is number theory as old as Euclid.
What you’ll learn
- Reduce factoring to order finding and prove that yields nontrivial factors when is even and .
- Express order finding as phase estimation of , using its eigenvectors and the identity .
- Recover from a measured approximation of with continued fractions, including the failure cases.
- Factor 15 and 21 end to end, and estimate the gate and qubit cost of the whole algorithm.
Why factoring?
The RSA cryptosystem publishes a modulus , the product of two large primes; its security rests on the assumption that recovering and from is infeasible. The best known classical method, the general number field sieve, runs in heuristic time
subexponential but superpolynomial in the number of digits. The largest RSA challenge number factored this way is RSA-250 (829 bits, 2020), at a cost of thousands of core-years; 2048-bit moduli are far out of reach.
Think first Why not just try every divisor up to ?
For a 2048-bit there are about candidates. Trial division is exponential in , and even the number field sieve's subexponential cost is astronomical at this size. Shor's algorithm needs a number of gates polynomial in .
From factoring to order finding
The order of modulo , for , is the least with ; the sequence is periodic with period . A classical randomized reduction, going back to Miller (1976), turns any order-finding procedure into a factoring algorithm.
Classical pre-checks: if is even, output 2; if for some , output (testable in polynomial time). Pick a random ; if , that gcd is already a factor.
Suppose is even. Then is a square root of modulo , and divides the product.
does not divide , because is the least exponent with . If moreover , it does not divide either.
So the prime factors of are split between the two factors, and Euclid's algorithm extracts nontrivial divisors in time.
For odd with at least two distinct prime factors, a random works with probability at least (proved in Order Finding & Continued Fractions).
You run the reduction on with . What happens?
- , and the factors 3 and 5 come out
- , but , so the gcds are the trivial divisors 1 and 15: pick another
- is odd, so the method fails
- reveals a factor immediately
Show the answer
B. , but , so the gcds are the trivial divisors 1 and 15: pick another
, so and . Then and : no information. This is the failure case the condition excludes.
Order finding is phase estimation
Let and define on qubits for (and for ). It is a permutation of basis states, hence unitary, because multiplication by is invertible modulo . Repeated application to walks the cycle .
Fourier modes on the cycle generated by .
Shift the summation index cyclically, using .
The inner sum is for and otherwise. You cannot prepare a single without knowing , but their uniform superposition is simply .
By linearity, phase estimation with input returns an estimate of for a uniformly random .
Phase estimation needs controlled-, which is controlled-: controlled multiplication by the constant . These constants are computed classically by repeated squaring, so the quantum circuit is a sequence of controlled modular multiplications that together compute . This modular exponentiation dominates the cost of the algorithm.
Continued fractions: from a sample to the period
The measurement gives an integer with , where . Shor chose , so that the likely outcomes satisfy . Two distinct fractions with denominators below differ by more than , so pins down uniquely, and a classical algorithm finds it.
For , , , the outcomes each occur with probability . For how many of them does the reduced fraction have denominator exactly ?
Show the answer
2
and give 4. But gives only the divisor 2 (here shares a factor with ), and gives nothing. Testing small multiples of the denominator, as the widget does, rescues too.
Success probability and cost
A run can fail in three ways. Each is cheap to detect, since you can check classically, and cheap to fix:
| Failure | Probability | Remedy |
|---|---|---|
| The estimate is far from every | at most with counting qubits | rerun |
| : the convergent gives only the divisor | (for example ) | test small multiples, or take the lcm of the denominators from two runs, which equals with probability above |
| odd, or | at most over random | pick a new |
So a constant expected number of runs suffices. The cost of one run:
| Resource | Textbook count |
|---|---|
| Counting qubits | , or one recycled qubit with the semiclassical QFT |
| Work register and ancillas | |
| Modular exponentiation | controlled modular multiplications of gates each: |
| Inverse QFT | gates, or approximately |
| Classical post-processing | bit operations (continued fractions, gcds) |
Compact circuits bring the total to qubits (Beauregard 2003). For the logical gate count runs into the billions; what that means in physical hardware is the subject of Breaking RSA: Resource Estimates.
Factoring with , you measure , so with convergents . You find and . What should you do?
- Conclude and compute
- Declare that 21 cannot be factored with
- Treat 3 as a divisor of : test its multiples ( gives ), or combine with another run via an lcm
- Increase and rerun until the denominator is even
Show the answer
C. Treat 3 as a divisor of : test its multiples ( gives ), or combine with another run via an lcm
: here shares the factor 2 with , so the convergent shows only . Since , 3 is not the order, but small multiples are cheap to test, and .
Shor in the lab, and what comes next
Small instances have been run many times: 15 was factored on a 7-qubit NMR quantum computer in 2001 (Vandersypen et al.), and later on photonic, superconducting and trapped-ion devices, the last with recycled control qubits (Monz et al. 2016). Read such claims carefully. Most demonstrations use circuits compiled with knowledge of the answer, for example with the known period built in, and Smolin, Smith and Vargo (2013) showed that such shortcuts can make "factoring" trivial for any number. As of the mid-2020s, no quantum computer has run Shor's algorithm on a number that is hard classically: that requires large-scale error correction.
Key takeaways
- Factoring reduces to order finding: if is even and , then are nontrivial factors; a random works with probability at least .
- Order finding is phase estimation of : eigenphases , input , and controlled powers implemented by modular exponentiation.
- About counting qubits put the estimate within of , so continued fractions recover exactly; is fixed with small multiples or an lcm of two runs.
- Cost: gates, dominated by modular exponentiation, and qubits ( with recycling), with a constant expected number of runs.
- Factoring is not NP-complete. Demonstrations so far are tiny and often compiled with the answer; breaking RSA needs large-scale error correction.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
In the reduction, . Why does this yield a nontrivial factor?
- Because are both prime
- Because forces
- Because divides neither factor: not since is minimal, and not since
- Because even implies is even
Show the answer
C. Because divides neither factor: not since is minimal, and not since
If divides a product but neither factor, its prime factors are split between the two, so each is a proper divisor greater than 1.
What are the eigenvalues of on the span of ?
- for , where is the order of
- Only , since is a permutation
Show the answer
A. for , where is the order of
cyclically shifts the states , so its eigenvalues on that cycle are the -th roots of unity, with eigenvectors . That is why the measured phase encodes .
For and the order is . Which factors does the reduction produce?
- and : it fails
- only
- None, since
- and
Show the answer
D. and
, so and .
Why does Shor take rather than ?
- To make the QFT unitary
- So that lies within of , close enough to single out among all fractions with denominator below (Legendre's condition)
- Because modular exponentiation needs bits of workspace
- To make every outcome an exact multiple of
Show the answer
B. So that lies within of , close enough to single out among all fractions with denominator below (Legendre's condition)
Fractions with denominators below are more than apart, and Legendre's theorem needs . Both follow from .
Which statement about Shor's algorithm is correct?
- It shows that quantum computers solve NP-complete problems in polynomial time
- It factors any -bit number with gates
- It runs in polynomial time while the best known classical algorithms are superpolynomial, and factoring is not believed to be NP-complete
- It breaks all public-key cryptography, including lattice-based schemes
Show the answer
C. It runs in polynomial time while the best known classical algorithms are superpolynomial, and factoring is not believed to be NP-complete
Shor's algorithm uses gates (or slightly fewer with fast arithmetic). Factoring sits in , and lattice-based schemes have no known efficient quantum attack.
Go deeper
- Order Finding & Continued Fractions · Turning a noisy measurement into an exact period.
- Breaking RSA: Resource Estimates · How many physical qubits and how much time, really?
- Discrete Logarithms & Elliptic Curves · Why ECC falls too, and with fewer qubits.
Further reading
- P. W. Shor, "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer", SIAM J. Comput. 26, 1484 (1997); conference version in Proc. 35th IEEE FOCS (1994).
- A. Ekert & R. Jozsa, "Quantum computation and Shor's factoring algorithm", Rev. Mod. Phys. 68, 733 (1996).
- M. A. Nielsen & I. L. Chuang, Quantum Computation and Quantum Information, §5.3 and Appendix 4 (Cambridge, 10th anniv. ed., 2010).
- L. M. K. Vandersypen, M. Steffen, G. Breyta, C. S. Yannoni, M. H. Sherwood & I. L. Chuang, "Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance", Nature 414, 883 (2001).