Lesson 20: Shor's Algorithm for Integer Factorization¶
20.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- Assemble the complete Shor algorithm from the reduction (L17), the QFT (L18) and QPE (L19).
- Derive the order-finding circuit and the state after each stage.
- Apply the continued-fraction expansion to recover \(r\) from a measured \(s/r\).
- Execute a full worked factorisation of 15 and of 21 by hand.
- State the resource requirements and the security implications.
20.2 The Complete Algorithm¶
INPUT: odd composite N, not a prime power
CLASSICAL PRE-PROCESSING
1. Pick random a in {2,...,N-1}
2. If gcd(a,N) > 1, return it (lucky)
QUANTUM ORDER FINDING ---- the only quantum part ----
3. Prepare |0>^t |1> with t = 2n+1, n = ceil(log2 N)
4. H^t on the counting register
5. Apply modular exponentiation: |k>|1> -> |k>|a^k mod N>
6. (Optionally measure the second register)
7. Apply QFT^-1 to the counting register
8. Measure -> integer m; set phi = m / 2^t (an estimate of s/r)
CLASSICAL POST-PROCESSING
9. Continued fractions on phi -> candidate r
10. Verify a^r = 1 mod N. If not, try nearby denominators or repeat.
11. If r odd or a^(r/2) = -1 mod N, go to 1
12. Return gcd(a^(r/2) - 1, N) and gcd(a^(r/2) + 1, N)
Why t = 2n+1 counting qubits?¶
Two candidate orders \(r_1 \ne r_2\) both less than \(N\) give fractions \(s_1/r_1\) and \(s_2/r_2\) that differ by at least
To resolve them we need precision better than \(\frac{1}{2N^2}\), i.e.
This is exactly the precision at which the continued-fraction algorithm is guaranteed to return the correct \(r\).
20.3 The Quantum Core, Step by Step¶
Step 3–4.
Step 5 — modular exponentiation. This is a reversible circuit computing \(a^k \bmod N\):
This single step is over 90 % of the circuit's cost. It is built from \(t\) controlled modular multiplications (each \(|y\rangle\to|a^{2^j}y \bmod N\rangle\), with the constant \(a^{2^j}\) precomputed classically), which in turn are built from modular adders, which are built from Toffoli gates. Best-known constructions use \(O(n^3)\) gates and \(2n+O(\log n)\) qubits.
Step 6 — measure the second register (conceptually). Suppose we see \(a^{k_0}\). The first register collapses to a periodic comb:
— equally spaced spikes of period \(r\), with an unknown offset \(k_0\).
(By the principle of deferred measurement, we need not actually measure; the analysis is identical. The state above is what the counting register looks like conditioned on the outcome.)
Step 7 — inverse QFT. By the shift theorem (L18, Problem 4) the unknown offset \(k_0\) contributes only phases, and the periodic comb transforms into a comb of period \(2^t/r\):
Step 8 — measure, obtaining \(m\) with
Equivalence to QPE. This is exactly quantum phase estimation applied to the modular multiplication operator \(U_a|y\rangle = |ay\bmod N\rangle\), whose eigenphases are \(s/r\) (L19, Problem 5), with the trivially-preparable input \(|1\rangle = \frac{1}{\sqrt r}\sum_s|u_s\rangle\).
20.4 Continued Fractions¶
Problem. We have \(\phi = m/2^t\), a good approximation to \(s/r\). We know \(r < N\). Recover \(r\).
Tool. The continued-fraction expansion
produces a sequence of convergents \(p_k/q_k\) that are the best rational approximations with denominators up to \(q_k\).
Algorithm.
x = phi
for k = 0, 1, 2, ...:
a_k = floor(x)
x = 1 / (x - a_k) (stop if x - a_k == 0)
convergents: p_{-1}=1, p_0=a_0, q_{-1}=0, q_0=1
p_k = a_k p_{k-1} + p_{k-2}
q_k = a_k q_{k-1} + q_{k-2}
Theorem (Legendre). If \(\left|\phi - \frac{s}{r}\right| < \frac{1}{2r^2}\) then \(s/r\) appears among the convergents of \(\phi\).
With \(t = 2n+1\) we have \(|\phi - s/r| \le 2^{-t-1} < \frac{1}{2N^2} \le \frac{1}{2r^2}\), so the theorem applies and the correct \(r\) is guaranteed to be one of the convergent denominators.
Procedure. Compute convergents until \(q_k \ge N\); test each \(q_k\) by checking \(a^{q_k}\equiv1\pmod N\). Also test small multiples \(2q_k, 3q_k\) — needed when \(\gcd(s,r) > 1\) causes the fraction to appear in lowest terms with a smaller denominator.
20.5 Solved Problems¶
Problem 1 — Complete factorisation of 15 with a = 7¶
Run the whole algorithm. Take \(n = 4\), \(t = 3\) (a common textbook simplification; the full \(t = 2n+1 = 9\) is not needed for such a small case).
Solution.
Classical setup. \(\gcd(7,15) = 1\) ✓. From L17, \(r = 4\); the quantum step must discover this.
Quantum trace. The sequence \(7^k \bmod 15\) for \(k = 0,\dots,7\):
— clearly periodic with \(r = 4\).
After Step 5:
Suppose the second register measures \(7\). The counting register collapses to
Apply \(\mathrm{QFT}_8^{-1}\):
The bracket is \(e^{-2\pi im/8}\left(1 + e^{-2\pi i\cdot4m/8}\right) = e^{-2\pi im/8}\left(1 + (-1)^{m}\right)\), which vanishes for odd \(m\) and equals \(2e^{-2\pi im/8}\) for even \(m\).
Measurement gives \(m \in \{0,2,4,6\}\), each with probability \(\frac14\).
Classical post-processing. Take \(m = 6\): \(\phi = \frac{6}{8} = \frac34\).
Continued fractions of \(\frac34\): \(\frac34 = [0;1,3]\), with convergents \(\frac01, \frac11, \frac34\). The last has denominator \(q = 4 < 15\) ✓.
Candidate \(r = 4\). Verify: \(7^4 = 2401 = 160\times15 + 1 \equiv 1 \pmod{15}\) ✓.
Finish. \(r=4\) even ✓; \(x = 7^2 = 49 \equiv 4\); \(x\ne14\) ✓.
Other outcomes. \(m=0\) gives \(\phi = 0\) — useless, retry. \(m=2\) gives \(\phi = \frac14 \Rightarrow r = 4\) ✓. \(m=4\) gives \(\phi = \frac12\), whose convergent denominator is \(2\); testing \(7^2 = 4 \ne 1\), so try \(2q = 4\): \(7^4 \equiv 1\) ✓. Useful outcomes: 3 out of 4.
Problem 2 — Factorisation of 21 with a = 2¶
Factor \(N = 21\), \(a = 2\). Use \(t = 5\) (\(2^t = 32\)).
Solution. Sequence \(2^k\bmod 21\): \(1, 2, 4, 8, 16, 11, 1, 2, \dots\) — period \(r = 6\) ✓ (L17).
Expected measurement. \(\frac{m}{32}\approx\frac{s}{6}\), so \(m \approx \frac{32s}{6} = 5.333s\):
| \(s\) | \(32s/6\) | nearest \(m\) | \(\phi = m/32\) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 5.33 | 5 | 0.15625 |
| 2 | 10.67 | 11 | 0.34375 |
| 3 | 16 | 16 | 0.5 |
| 4 | 21.33 | 21 | 0.65625 |
| 5 | 26.67 | 27 | 0.84375 |
Take \(m = 27\), \(\phi = \frac{27}{32}\).
Continued fraction of \(\frac{27}{32}\):
Convergents:
| \(k\) | \(a_k\) | \(p_k\) | \(q_k\) | \(p_k/q_k\) |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 |
| 2 | 5 | 5 | 6 | 0.8333 |
| 3 | 2 | 11 | 13 | 0.8462 |
| 4 | 2 | 27 | 32 | 0.84375 |
Candidate denominators: \(1, 6, 13, 32\). Discard \(q \ge N = 21\).
Test \(q = 6\): \(2^6 = 64 = 3\times21 + 1 \equiv 1\pmod{21}\) ✓.
Finish. \(r\) even ✓; \(x = 2^3 = 8\); \(x \ne 20\) ✓.
Note the near-miss. The convergent \(\frac{11}{13}\) is numerically closer to \(0.84375\) than \(\frac{5}{6}\) is — but \(13\) fails the verification \(2^{13} = 8192 = 390\times21 + 2 \equiv 2 \ne 1 \pmod{21}\). The verification step is essential; you cannot simply take the best-looking convergent.
Problem 3 — Continued fractions in detail¶
A run on \(N = 55\) with \(t = 12\) (\(2^t = 4096\)) returns \(m = 819\). Find \(r\).
Solution. \(\phi = \frac{819}{4096} = 0.19995117\ldots\)
Continued fraction expansion.
Work it properly:
So \(\frac{819}{4096} = [0; 5, 819]\).
Convergents:
| \(k\) | \(a_k\) | \(p_k\) | \(q_k\) |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 1 | 5 | 1 | 5 |
| 2 | 819 | 819 | 4096 |
Candidates: \(q = 1\), \(q = 5\) (and \(4096 \ge 55\), discard).
Test \(r = 5\): \(2^5 = 32 \ne 1 \pmod{55}\). ✗
Test small multiples. \(r = 10\): \(2^{10} = 1024 = 18\times55 + 34 \equiv 34 \ne 1\). ✗ \(r = 15\): \(2^{15} = 2^{10}\cdot2^5 \equiv 34\times32 = 1088 = 19\times55 + 43 \equiv 43\). ✗ \(r = 20\): \(2^{20}\equiv 34^2 = 1156 = 21\times55+1\equiv \mathbf{1}\) ✓
Interpretation. The measurement corresponded to \(s = 4\): \(\frac{s}{r} = \frac{4}{20} = \frac15\), which in lowest terms is \(\frac15\) — so continued fractions returned \(q = 5 = r/\gcd(s,r)\). The useful outcomes are those with \(\gcd(s,r) = 1\), which happen with probability \(\phi(r)/r = \phi(20)/20 = 8/20 = 0.4\).
Finish the factorisation. \(r=20\) even ✓; \(x = 2^{10}\equiv 34\); \(x \ne 54\) ✓.
Problem 4 — Probability of a useful outcome¶
Show that the probability of measuring an \(s\) with \(\gcd(s,r)=1\) is \(\phi(r)/r\), and evaluate for \(r = 4, 6, 12, 20\). How many runs give 99 % confidence for \(r=12\)?
Solution. Since \(s\) is uniform on \(\{0,1,\dots,r-1\}\), the probability that \(\gcd(s,r)=1\) is by definition
| \(r\) | \(\phi(r)\) | \(\phi(r)/r\) |
|---|---|---|
| 4 | 2 | 0.500 |
| 6 | 2 | 0.333 |
| 12 | 4 | 0.333 |
| 20 | 8 | 0.400 |
Runs for \(r=12\) at 99 % confidence. Failure per run \(= 1 - \frac13 = \frac23\).
General bound. A theorem of Mertens gives \(\frac{\phi(r)}{r} = \Omega\!\left(\frac{1}{\log\log r}\right)\), so the number of repetitions grows only like \(O(\log\log N)\) — negligible.
In practice the count is smaller, because testing small multiples of the convergent denominators (as in Problem 3) rescues many of the "bad" outcomes.
Problem 5 — Resources for RSA-2048 and the security timeline¶
Estimate qubits, gate count, runtime and required coherence for factoring a 2048-bit modulus. Contrast with breaking AES-256.
Solution.
Logical qubits. The standard construction needs \(2n + O(\log n)\):
(Beauregard's optimisation reduces this to \(2n+3 = 4099\) using one-qubit control and semi-classical QFT.)
Gate count. Modular exponentiation dominates: \(O(n^3)\) Toffoli gates.
Each Toffoli needs 7 \(T\) gates, so the \(T\)-count is \(\sim6\times10^{10}\).
Physical qubits. Surface code at physical error rate \(10^{-3}\) requires code distance \(d\approx27\) for these depths, i.e. \(\approx 2d^2 \approx 1500\) physical qubits per logical qubit, plus magic-state factories:
Gidney & Ekerå (2021) give the careful figure: 20 million physical qubits, ~8 hours.
Coherence. With logical operations, the physical coherence requirement is only per-cycle; error correction extends the effective logical lifetime indefinitely. Without QEC, one would need \(T_2 > 8\) hours — impossible (current transmons: \(\sim100\ \mu\)s).
Contrast: AES-256 under Grover. From L01/L23, Grover needs \(\approx1.4\times10^{19}\) sequential iterations. Even at \(10^{9}\) iterations/second that is \(\approx460\) years, and Grover parallelises poorly (splitting into \(P\) machines gives only a \(\sqrt P\) improvement).
| RSA-2048 | AES-256 | |
|---|---|---|
| Quantum attack | Shor | Grover |
| Speed-up | super-polynomial | quadratic only |
| Estimated quantum runtime | ~8 hours | ~460 years |
| Mitigation | replace the algorithm (ML-KEM, ML-DSA) | double key length (already done) |
Conclusion. Symmetric cryptography survives with larger keys. Public-key cryptography based on factoring or discrete logarithms does not survive at all and must be replaced — the subject of L25.
20.6 Practice Problems¶
- Factor 15 using \(a = 2\). Find \(r\) and complete the reduction. [Ans: \(r=4\), \(x=4\), factors 3 and 5]
- Compute the continued fraction of \(\frac{13}{16}\) and list the convergents. [Ans: \([0;1,4,3]\); \(0/1, 1/1, 4/5, 13/16\)]
- A run on \(N=33\) gives \(\phi = \frac{85}{256}\). Find \(r\). [Ans: convergent \(1/3\); test \(r=3\): \(a\)-dependent — verify then try multiples]
- Why is \(t = 2n+1\) rather than \(t = n\)?
- Compute \(\phi(r)/r\) for \(r = 30\). [Ans: \(8/30 = 0.267\)]
- Explain why measuring the second register is unnecessary.
- If a device has 100 logical qubits, what is the largest RSA modulus it could attack? [Ans: about 48 bits — trivially factorable classically]
20.7 Summary¶
- Shor = classical reduction (L17) + quantum order finding + classical continued fractions.
- Order finding is phase estimation applied to \(U_a|y\rangle = |ay\bmod N\rangle\), whose eigenphases are \(s/r\); the easy input \(|1\rangle\) is an equal superposition of all \(r\) eigenstates.
- Use \(t = 2n+1\) counting qubits so that Legendre's theorem guarantees continued fractions recover \(r\).
- Measurement returns \(m\) with \(m/2^t \approx s/r\); convergents of \(m/2^t\) give candidate \(r\); always verify \(a^r\equiv1\) and test small multiples.
- A useful \(s\) (with \(\gcd(s,r)=1\)) occurs with probability \(\phi(r)/r = \Omega(1/\log\log r)\), so \(O(\log\log N)\) repetitions suffice.
- Complexity \(O(\log^3 N)\); modular exponentiation is >90 % of the gate cost.
- RSA-2048: ~4100 logical / ~20 million physical qubits, ~8 hours. RSA and ECC are dead against a fault-tolerant machine; AES-256 is not.
Next lesson: L21 — Grover's algorithm: the oracle and the diffusion operator.
Practise now: unit2-algorithms-lab.html → Shor Workbench: pick \(N\) and \(a\), watch the period
appear in the modular-exponentiation table, see the QFT peak structure, and step through the
continued-fraction table to recover \(r\).