Simple Algorithm
Quantum Computing · Excited State · 26 min

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 gcd⁡(ar/2±1,N)\gcd(a^{r/2}\pm1,N) yields nontrivial factors when rr is even and ar/2≢−1(modN)a^{r/2}\not\equiv-1\pmod N.
  • Express order finding as phase estimation of Ua∣y⟩=∣ay mod N⟩U_a\ket y=\ket{ay \bmod N}, using its eigenvectors and the identity ∣1⟩=1r∑s∣us⟩\ket1=\tfrac{1}{\sqrt r}\sum_s\ket{u_s}.
  • Recover rr from a measured approximation of s/rs/r 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 N=pqN=pq, the product of two large primes; its security rests on the assumption that recovering pp and qq from NN is infeasible. The best known classical method, the general number field sieve, runs in heuristic time

exp⁡((64/93+o(1))(ln⁡N)1/3(ln⁡ln⁡N)2/3),\exp\Bigl(\bigl(\sqrt[3]{64/9}+o(1)\bigr)(\ln N)^{1/3}(\ln\ln N)^{2/3}\Bigr),

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 N\sqrt N?

For a 2048-bit NN there are about N≈21024≈10308\sqrt N\approx2^{1024}\approx10^{308} candidates. Trial division is exponential in LL, and even the number field sieve's subexponential cost is astronomical at this size. Shor's algorithm needs a number of gates polynomial in L=2048L=2048.

From factoring to order finding

The order of aa modulo NN, for gcd⁡(a,N)=1\gcd(a,N)=1, is the least r≥1r\ge1 with ar≡1(modN)a^r\equiv1\pmod N; the sequence ax mod Na^x\bmod N is periodic with period rr. A classical randomized reduction, going back to Miller (1976), turns any order-finding procedure into a factoring algorithm.

DerivationThe reduction
  1. gcd⁡(a,N)=1 ⟹ r=ord⁡N(a) exists\gcd(a,N)=1\ \Longrightarrow\ r=\operatorname{ord}_N(a)\ \text{exists}

    Classical pre-checks: if NN is even, output 2; if N=bkN=b^k for some k≥2k\ge2, output bb (testable in polynomial time). Pick a random a∈{2,…,N−1}a\in\{2,\dots,N-1\}; if gcd⁡(a,N)>1\gcd(a,N)>1, that gcd is already a factor.

  2. (ar/2−1)(ar/2+1)=ar−1≡0(modN)(a^{r/2}-1)(a^{r/2}+1)=a^r-1\equiv0\pmod N

    Suppose rr is even. Then ar/2a^{r/2} is a square root of 11 modulo NN, and NN divides the product.

  3. N∤ar/2−1,N∤ar/2+1  (if ar/2≢−1)N\nmid a^{r/2}-1,\qquad N\nmid a^{r/2}+1\ \ (\text{if } a^{r/2}\not\equiv-1)

    NN does not divide ar/2−1a^{r/2}-1, because rr is the least exponent with ar≡1a^r\equiv1. If moreover ar/2≢−1a^{r/2}\not\equiv-1, it does not divide ar/2+1a^{r/2}+1 either.

  4. 1<gcd⁡(ar/2±1, N)<N1<\gcd\bigl(a^{r/2}\pm1,\,N\bigr)<N

    So the prime factors of NN are split between the two factors, and Euclid's algorithm extracts nontrivial divisors in O(L3)\order{L^3} time.

  5. Pr⁡a[ r even and ar/2≢−1 ] ≥ 12\Pr_a\bigl[\,r\ \text{even and}\ a^{r/2}\not\equiv-1\,\bigr]\ \ge\ \tfrac12

    For odd NN with at least two distinct prime factors, a random aa works with probability at least 12\tfrac12 (proved in Order Finding & Continued Fractions).

Check your understanding

You run the reduction on N=15N=15 with a=14a=14. What happens?

  1. r=4r=4, and the factors 3 and 5 come out
  2. r=2r=2, but 14≡−1(mod15)14\equiv-1\pmod{15}, so the gcds are the trivial divisors 1 and 15: pick another aa
  3. rr is odd, so the method fails
  4. gcd⁡(14,15)=7\gcd(14,15)=7 reveals a factor immediately
Show the answer

B. r=2r=2, but 14≡−1(mod15)14\equiv-1\pmod{15}, so the gcds are the trivial divisors 1 and 15: pick another aa

142=196=13⋅15+114^2=196=13\cdot15+1, so r=2r=2 and ar/2=14≡−1a^{r/2}=14\equiv-1. Then gcd⁡(13,15)=1\gcd(13,15)=1 and gcd⁡(15,15)=15\gcd(15,15)=15: no information. This is the failure case the condition ar/2≢−1a^{r/2}\not\equiv-1 excludes.

Order finding is phase estimation

Let L=⌈log⁡2N⌉L=\lceil\log_2N\rceil and define Ua∣y⟩=∣ay mod N⟩U_a\ket{y}=\ket{ay\bmod N} on LL qubits for 0≤y<N0\le y<N (and Ua∣y⟩=∣y⟩U_a\ket y=\ket y for N≤y<2LN\le y<2^L). It is a permutation of basis states, hence unitary, because multiplication by aa is invertible modulo NN. Repeated application to ∣1⟩\ket1 walks the cycle 1→a→a2→⋯→ar−1→11\to a\to a^2\to\cdots\to a^{r-1}\to1.

DerivationEigenvectors of modular multiplication
  1. ∣us⟩=1r∑k=0r−1e−2πi sk/r∣ak mod N⟩,s=0,1,…,r−1\ket{u_s}=\frac{1}{\sqrt r}\sum_{k=0}^{r-1}e^{-2\pi i\,sk/r}\ket{a^k\bmod N},\qquad s=0,1,\dots,r-1

    Fourier modes on the cycle generated by aa.

  2. Ua∣us⟩=1r∑k=0r−1e−2πi sk/r∣ak+1⟩=e2πi s/r∣us⟩U_a\ket{u_s}=\frac{1}{\sqrt r}\sum_{k=0}^{r-1}e^{-2\pi i\,sk/r}\ket{a^{k+1}}=e^{2\pi i\,s/r}\ket{u_s}

    Shift the summation index k→k−1k\to k-1 cyclically, using ar≡1a^r\equiv1.

  3. 1r∑s=0r−1∣us⟩=1r∑k=0r−1(∑s=0r−1e−2πi sk/r)∣ak⟩=∣1⟩\frac{1}{\sqrt r}\sum_{s=0}^{r-1}\ket{u_s}=\frac1r\sum_{k=0}^{r-1}\Bigl(\sum_{s=0}^{r-1}e^{-2\pi i\,sk/r}\Bigr)\ket{a^k}=\ket1

    The inner sum is rr for k=0k=0 and 00 otherwise. You cannot prepare a single ∣us⟩\ket{u_s} without knowing rr, but their uniform superposition is simply ∣1⟩\ket1.

  4. QPE on ∣1⟩ ⟹ φ~≈sr,s uniform in {0,…,r−1}\text{QPE on }\ket1\ \Longrightarrow\ \tilde\varphi\approx\frac sr,\qquad s\ \text{uniform in}\ \{0,\dots,r-1\}

    By linearity, phase estimation with input ∣1⟩\ket1 returns an estimate of s/rs/r for a uniformly random ss.

Phase estimation needs controlled-Ua2jU_a^{2^j}, which is controlled-Ua2jU_{a^{2^j}}: controlled multiplication by the constant a2j mod Na^{2^j}\bmod N. These constants are computed classically by repeated squaring, so the quantum circuit is a sequence of controlled modular multiplications that together compute ∣k⟩∣1⟩↦∣k⟩∣ak mod N⟩\ket{k}\ket{1}\mapsto\ket{k}\ket{a^k\bmod N}. This modular exponentiation dominates the cost of the algorithm.

Continued fractions: from a sample to the period

The measurement gives an integer yy with y/Q≈s/ry/Q\approx s/r, where Q=2tQ=2^t. Shor chose N2≤Q<2N2N^2\le Q<2N^2, so that the likely outcomes satisfy ∣y/Q−s/r∣≤1/(2Q)≤1/(2N2)\abs{y/Q-s/r}\le1/(2Q)\le1/(2N^2). Two distinct fractions with denominators below NN differ by more than 1/N21/N^2, so y/Qy/Q pins down s/rs/r uniquely, and a classical algorithm finds it.

Predict before you look

For N=15N=15, a=7a=7, Q=256Q=256, the outcomes y=0,64,128,192y=0,64,128,192 each occur with probability 14\tfrac14. For how many of them does the reduced fraction y/Qy/Q have denominator exactly r=4r=4?

Show the answer

2

64/256=1/464/256=1/4 and 192/256=3/4192/256=3/4 give 4. But 128/256=1/2128/256=1/2 gives only the divisor 2 (here s=2s=2 shares a factor with rr), and 0/2560/256 gives nothing. Testing small multiples of the denominator, as the widget does, rescues y=128y=128 too.

Success probability and cost

A run can fail in three ways. Each is cheap to detect, since you can check ar≡1(modN)a^r\equiv1\pmod N classically, and cheap to fix:

FailureProbabilityRemedy
The estimate is far from every s/rs/rat most ε\varepsilon with t=2L+1+⌈log⁡2(2+12ε)⌉t=2L+1+\lceil\log_2(2+\tfrac1{2\varepsilon})\rceil counting qubitsrerun
gcd⁡(s,r)>1\gcd(s,r)>1: the convergent gives only the divisor r/gcd⁡(s,r)r/\gcd(s,r)1−φ(r)/r1-\varphi(r)/r (for example s=0s=0)test small multiples, or take the lcm of the denominators from two runs, which equals rr with probability above 12\tfrac12
rr odd, or ar/2≡−1a^{r/2}\equiv-1at most 12\tfrac12 over random aapick a new aa

So a constant expected number of runs suffices. The cost of one run:

ResourceTextbook count
Counting qubitst≈2L+1t\approx2L+1, or one recycled qubit with the semiclassical QFT
Work register and ancillasL+O(L)L+\order{L}
Modular exponentiation≈2L\approx2L controlled modular multiplications of O(L2)\order{L^2} gates each: O(L3)\order{L^3}
Inverse QFTO(L2)\order{L^2} gates, or O(Llog⁡L)\order{L\log L} approximately
Classical post-processingO(L3)\order{L^3} bit operations (continued fractions, gcds)

Compact circuits bring the total to 2L+32L+3 qubits (Beauregard 2003). For L=2048L=2048 the logical gate count runs into the billions; what that means in physical hardware is the subject of Breaking RSA: Resource Estimates.

Check your understanding

Factoring N=21N=21 with a=2a=2, you measure y=171y=171, so y/Q=171/512=[0;2,1,170]y/Q=171/512=[0;2,1,170] with convergents 0,12,13,1715120,\tfrac12,\tfrac13,\tfrac{171}{512}. You find 22≢12^2\not\equiv1 and 23≡8≢1(mod21)2^3\equiv8\not\equiv1\pmod{21}. What should you do?

  1. Conclude r=3r=3 and compute gcd⁡(23/2±1,21)\gcd(2^{3/2}\pm1,21)
  2. Declare that 21 cannot be factored with a=2a=2
  3. Treat 3 as a divisor of rr: test its multiples (26≡12^6\equiv1 gives r=6r=6), or combine with another run via an lcm
  4. Increase QQ and rerun until the denominator is even
Show the answer

C. Treat 3 as a divisor of rr: test its multiples (26≡12^6\equiv1 gives r=6r=6), or combine with another run via an lcm

171/512≈2/6=1/3171/512\approx2/6=1/3: here s=2s=2 shares the factor 2 with r=6r=6, so the convergent shows only r/gcd⁡(s,r)=3r/\gcd(s,r)=3. Since 23≢12^3\not\equiv1, 3 is not the order, but small multiples are cheap to test, and 26≡12^6\equiv1.

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 r=ord⁡N(a)r=\operatorname{ord}_N(a) is even and ar/2≢−1a^{r/2}\not\equiv-1, then gcd⁡(ar/2±1,N)\gcd(a^{r/2}\pm1,N) are nontrivial factors; a random aa works with probability at least 12\tfrac12.
  • Order finding is phase estimation of UaU_a: eigenphases s/rs/r, input ∣1⟩=1r∑s∣us⟩\ket1=\tfrac1{\sqrt r}\sum_s\ket{u_s}, and controlled powers implemented by modular exponentiation.
  • About 2L2L counting qubits put the estimate within 1/(2r2)1/(2r^2) of s/rs/r, so continued fractions recover s/rs/r exactly; gcd⁡(s,r)>1\gcd(s,r)>1 is fixed with small multiples or an lcm of two runs.
  • Cost: O(L3)\order{L^3} gates, dominated by modular exponentiation, and O(L)\order{L} qubits (2L+32L+3 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.

Question 1

In the reduction, N∣(ar/2−1)(ar/2+1)N\mid(a^{r/2}-1)(a^{r/2}+1). Why does this yield a nontrivial factor?

  1. Because ar/2±1a^{r/2}\pm1 are both prime
  2. Because gcd⁡(a,N)=1\gcd(a,N)=1 forces gcd⁡(ar/2+1,N)=1\gcd(a^{r/2}+1,N)=1
  3. Because NN divides neither factor: not ar/2−1a^{r/2}-1 since rr is minimal, and not ar/2+1a^{r/2}+1 since ar/2≢−1a^{r/2}\not\equiv-1
  4. Because rr even implies NN is even
Show the answer

C. Because NN divides neither factor: not ar/2−1a^{r/2}-1 since rr is minimal, and not ar/2+1a^{r/2}+1 since ar/2≢−1a^{r/2}\not\equiv-1

If NN divides a product but neither factor, its prime factors are split between the two, so each gcd⁡(ar/2±1,N)\gcd(a^{r/2}\pm1,N) is a proper divisor greater than 1.

Question 2

What are the eigenvalues of Ua∣y⟩=∣ay mod N⟩U_a\ket y=\ket{ay\bmod N} on the span of {∣ak mod N⟩}\{\ket{a^k\bmod N}\}?

  1. e2πis/re^{2\pi is/r} for s=0,…,r−1s=0,\dots,r-1, where rr is the order of aa
  2. as mod Na^s\bmod N
  3. Only ±1\pm1, since UaU_a is a permutation
  4. e2πia/Ne^{2\pi ia/N}
Show the answer

A. e2πis/re^{2\pi is/r} for s=0,…,r−1s=0,\dots,r-1, where rr is the order of aa

UaU_a cyclically shifts the rr states ∣ak⟩\ket{a^k}, so its eigenvalues on that cycle are the rr-th roots of unity, with eigenvectors ∣us⟩\ket{u_s}. That is why the measured phase encodes rr.

Question 3

For N=21N=21 and a=2a=2 the order is r=6r=6. Which factors does the reduction produce?

  1. gcd⁡(26−1,21)=21\gcd(2^6-1,21)=21 and gcd⁡(26+1,21)=1\gcd(2^6+1,21)=1: it fails
  2. gcd⁡(22−1,21)=3\gcd(2^2-1,21)=3 only
  3. None, since 23≡−1(mod21)2^3\equiv-1\pmod{21}
  4. gcd⁡(23−1,21)=7\gcd(2^3-1,21)=7 and gcd⁡(23+1,21)=3\gcd(2^3+1,21)=3
Show the answer

D. gcd⁡(23−1,21)=7\gcd(2^3-1,21)=7 and gcd⁡(23+1,21)=3\gcd(2^3+1,21)=3

ar/2=23=8≢−1≡20a^{r/2}=2^3=8\not\equiv-1\equiv20, so gcd⁡(7,21)=7\gcd(7,21)=7 and gcd⁡(9,21)=3\gcd(9,21)=3.

Question 4

Why does Shor take Q=2t≥N2Q=2^t\ge N^2 rather than Q≈NQ\approx N?

  1. To make the QFT unitary
  2. So that y/Qy/Q lies within 1/(2N2)1/(2N^2) of s/rs/r, close enough to single out s/rs/r among all fractions with denominator below NN (Legendre's condition)
  3. Because modular exponentiation needs 2L2L bits of workspace
  4. To make every outcome yy an exact multiple of Q/rQ/r
Show the answer

B. So that y/Qy/Q lies within 1/(2N2)1/(2N^2) of s/rs/r, close enough to single out s/rs/r among all fractions with denominator below NN (Legendre's condition)

Fractions with denominators below NN are more than 1/N21/N^2 apart, and Legendre's theorem needs ∣y/Q−s/r∣<1/(2r2)\abs{y/Q-s/r}<1/(2r^2). Both follow from Q≥N2Q\ge N^2.

Question 5

Which statement about Shor's algorithm is correct?

  1. It shows that quantum computers solve NP-complete problems in polynomial time
  2. It factors any LL-bit number with O(L)\order{L} gates
  3. It runs in polynomial time while the best known classical algorithms are superpolynomial, and factoring is not believed to be NP-complete
  4. 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 O(L3)\order{L^3} gates (or slightly fewer with fast arithmetic). Factoring sits in NP∩coNP\mathsf{NP}\cap\mathsf{coNP}, and lattice-based schemes have no known efficient quantum attack.

Go deeper

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).