Now we bolt the toolkit together. Shor’s algorithm factors a big number — the bedrock of internet encryption — by a surprising detour: it turns factoring into finding a repeating period, and finds that period with phase estimation. Almost all of it is ordinary arithmetic; only one step is quantum.
↩ before you start · keep these handy
·From QC 07: phase estimation reads the eigen-phase of a unitary as a binary fraction.
·From QC 06: the inverse QFT inside QPE turns a winding into a readable number.
·From QI 8d: you’ve seen the outline — here is the full machine, end to end.
🔑 symbol decoder · every new mark, in plain words
aᵪ mod Nthe remainder of aᵪ divided by N. As x grows this sequence eventually repeats.period r (order)the smallest r with a^r mod N = 1 — the length of that repeat.gcd(p, q)greatest common divisor — the largest number dividing both. Fast and classical (Euclid).coprimetwo numbers sharing no factor: gcd = 1.Uₐ (modular mult.)the gate |y⟩ → |a·y mod N⟩. Its eigen-phases are exactly the fractions s/r.continued fractionthe classical trick that recovers r from the measured fraction s/r.
feel
Factoring in disguise
Nobody knows how to factor a huge number quickly — but there’s a back door. Pick a random number a and look at the powers a, a², a³… modulo N. They cycle with some period r. A little algebra turns that period into a factor of N. Finding the period is the only hard part — and that’s exactly what a quantum computer does exponentially faster.
🎲 everyday picture
A locked safe is hard to open by guessing the combination. But suppose pressing a key makes the dial advance by a fixed secret step, and you notice it returns to start every r presses. That repeat length quietly reveals the lock’s structure. Shor doesn’t guess the factors — it measures the rhythm of a related cycle, and the rhythm gives the factors away.
recapFactoring reduces to finding the period of aᵪ mod N; the period hands you a factor.
play
Factor a number, step by step
Choose N and a base a. The powers of a (mod N) are listed until they loop — that loop length is the period r the quantum step would find. The classical wrapper then turns r into the factors. Some choices of a fail (odd r, or a trivial root); that’s expected — you just retry.
▸ period-to-factor benchperiod r = quantum · rest = classical
N =
base a = {{ a }}
powers of {{ a }} (mod {{ N }}) — until the cycle closes
{{ s.v }}
a{{ s.exp }}
{{ ln.icon }}{{ ln.text }}
{{ verdict }}
recapFind r, then factor = gcd(ar/2 ± 1, N) — the quantum step supplies r, Euclid does the rest.
math
The five steps, and the one that’s quantum
1.Pick a random a < N. If gcd(a, N) > 1 you’ve already found a factor — lucky, done.
2.[QUANTUM] Run phase estimation on Uₐ|y⟩ = |a·y mod N⟩. Its eigen-phases are s/r, so QPE returns a fraction ≈ s/r.
3.Use continued fractions on that measured fraction to recover the period r.
4.If r is odd or ar/2 ≡ −1, discard and retry from step 1 (succeeds >½ the time).
5.Otherwise the factors are gcd(ar/2 − 1, N) and gcd(ar/2 + 1, N).
Only step 2 needs a quantum computer, and only because no fast classical period-finder is known. Everything else — gcd, continued fractions, retries — runs on your laptop in microseconds.
✎ worked example · factor N = 15 with a = 7
1.powers: 7¹=7, 7²=49≡4, 7³≡13, 7⁴≡1 (mod 15) → period r = 4
2.r is even, and ar/2 = 7² = 49 ≡ 4 (not −1) — good
recapFive steps; only the period-finding (step 2) is quantum, via QPE on the modular-multiply gate.
⚠ common misconceptions
“The quantum computer tries all possible factors at once.” It never touches factors directly. It finds a period; a short classical calculation converts that period into factors.
“Shor always works on the first try.” It’s randomized. A bad a (odd period, or ar/2 ≡ −1) just means retry — the success chance per attempt is comfortably above ½, so a few tries suffice.
“So today’s computers can break RSA.” The algorithm is proven, but factoring a real 2048-bit key needs millions of high-quality, error-corrected qubits — far beyond current hardware. That gap is the whole story of Parts C and D.
✓ you can now
✓explain why factoring reduces to period-finding
✓run the five steps of Shor by hand on a small N
✓identify the single quantum step (QPE on the modular-multiply gate)
✓say why it threatens RSA in principle but not yet in practice