The Algorithm on the Throne: Shor's Algorithm Part I — The Problem and the Idea
> Prerequisites: Episode 036 (QFT and phase estimation preview), 033/034 (templates and the speedup taxonomy), 021/022 (H, CNOT), 015 (multi-qubit registers). > Next episode: 038, "Shor II: Circuits and Cost."
In April 1994, news detonated across the cryptography community: someone had proved that if a sufficiently large quantum computer could be built, problems at the very foundation of modern cryptography like RSA would be broken efficiently. That still-hypothetical machine became, overnight, the justification for research funding worldwide — much of quantum computing's thirty-year funding curve took off from that announcement.
This article clarifies two things: why RSA's foundation rests specifically on "factoring large numbers," and why the quantum approach happens to be able to move it. Circuits and the cost accounting are left to episode 038.
The foundation: the marriage of factoring and cryptography
Multiply two large primes to get a big number N — that's multiplication, instantaneous on any calculator. The reverse — given only N, find its two prime factors — is factoring, notorious drudgery for classical computers: for an N of a few hundred digits, pooling all the world's computing power would not finish within the age of the universe.
"Easy to multiply, brutally hard to split apart" — this asymmetry is RSA's foundation: the public key is N (anyone can encrypt), the private key hides the two prime factors (only the owner can decrypt). An eavesdropper holding N must factor it first — and factoring is drudgery, hence security.
Note a subtlety: the information needed to decrypt has not vanished — it is "rolled up" inside N (N is the product of two primes; the ledger balances). The classical world cannot read it out only because the cost of taking it apart is astronomical. This resembles the old acquaintance from quantum information — "the information isn't lost, it's just unreadable" (episode 018). But don't rush the analogy: the quantum attack is not a brute-force demolition; it's a detour nobody saw coming.
The detour: turning factoring into period-finding
The pivot is a beautiful piece of old mathematical inventory (proved three hundred years ago; no need to memorize the name): factoring N can be completely reduced to "finding a period."
The construction: pick a random number a (sharing no factors with N) and write out the power sequence:
a, a², a³, a⁴, … modulo N
This sequence eventually cycles: there is a period r such that a^(x+r) mod N always equals a^x mod N (the sequence repeats every r steps). The three-hundred-year-old theorem guarantees: once you have r, factoring N takes only a few steps of arithmetic (sketch: r is even, and a^(r/2) ± 1 shares a common factor with N — finding common factors is a fast, happy task for classical computers).
A small-scale example: N = 15, take a = 7. The remainder sequence is 7, 4, 13, 1, 7, 4, 13, 1, … with period r = 4. Then a^(r/2) − 1 = 48 and a^(r/2) + 1 = 50 share with 15 the factors 3 and 5 — factoring complete. A real N has hundreds of digits, but the logic is unchanged; only one chasm remains:
> How large is r? When does the sequence start repeating? A classical computer doesn't know and must compute remainders step by step — and that computation is exponential.
So the whole campaign reduces to a purely technical question: how do you quickly find the period r of a problem where the period is hidden in a power sequence?
And you already know the shape of the answer — the machine profiled in episode 036, which eats periods and outputs frequencies.
Assembly: four parts screwed into one machine
Shor's algorithm = the previous four episodes' parts assembled per the manual (conceptual flow; circuit details in 038):
Part 1: the quantum version of the power sequence (episode 015's multi-qubit register + a modular-exponentiation black box). Use two registers: the x-register spans all exponents (Hadamard gates, episode 021); the y-register receives a^x mod N. One call to the black box puts remainders for all exponents on stage simultaneously (episode 031's constitution: superposition passes all inputs through the gate at once).
Part 2: QFT axis change (episode 036). The y-register can now be discarded (measure it or ignore it); the amplitude distribution on the x-register carries the pattern of period r — QFT in, frequency peaks out.
Part 3: measurement sampling (episode 036's "one glance"). Measure the x-register once; with high probability the outcome lands near a fraction k/r (k is some unknown small integer — frequencies are integer multiples of the period, as episode 036 explained).
Part 4: classical wrap-up. Run it a few times, collect several "fractions near k/r," and use classical continued-fraction techniques to recover r from the fractions — then apply the three-century-old theorem and a few classical arithmetic steps crack out the prime factors. The quantum part does exactly one thing: find r. Everything else is the classical world's own well-oiled routine.
The total bill: the quantum part's calls and gate count are polynomial in n (n = the bit length of N) — versus exponential classical factoring, an exponential speedup, the top-tier payoff of episode 034's taxonomy. The promise? "Periodicity" — and the periodicity of power sequences is not an artificial black-box quirk; it is number theory's intrinsic structure. That's why it is worth far more than BV/Simon's "promise problems" — this time, the problem itself is a real-world necessity.
The throne's meaning, and where the chasm sits
Shor's algorithm's historical standing needs no embellishment: it proved that a quantum computer (if buildable) is not "a faster calculator" but "a different kind of machine" — certain chasms of the classical world are gentle slopes on the quantum ledger. The "unbreachable foundation" assumption underpinning RSA, elliptic-curve cryptography, and a whole class of public-key schemes changed from a mathematical theorem into a conditional engineering problem.
But the chasm's location must be stated precisely (episode 039 covers this): factoring a real-world, few-hundred-digit N requires millions of physical qubits on an error-corrected, fault-tolerant machine — today's devices (hundreds to a thousand noisy qubits) are orders of magnitude away. Between "feasible in principle" and "breakable today" lies the entire error-correction engineering covered in the sixth batch. The theoretical throne is already cast; the coronation date is unset — this honest punctuation is the only sober posture when discussing "the quantum threat."
Tearing down the analogy
Where the "detour" analogy works and where it doesn't:
- Disanalogy 1: detours usually mean longer, slower routes; Shor's detour is shorter — the quantum call count is polynomial, far shorter than the classical exponential "straight" route. The analogy borrows "don't assault the front gate, find a hidden passage," not "farther."
- Disanalogy 2: "finding a period" sounds like pattern-hunting that might fail; quantum period-finding is probability amplified to near-certainty — QFT's peaks push success probability near 1, and the small residual failure probability is exponentially suppressed by rerunning a few times. The algorithm is "high-probability correct," not "a gamble."
Luggage to take home
1. RSA's foundation is "multiplication easy, factoring hard"; factoring reduces to finding the period r of a power sequence (three centuries of number-theoretic inventory), and once you have r, only fast classical arithmetic remains — the whole campaign converges on one word: *period*. 2. Shor = a four-part assembly: the modular-exponentiation black box spreads all exponents → QFT turns periodicity into frequency peaks → measurement takes a sample → classical continued fractions recover r. The quantum call count is polynomial — exponential speedup, with a promise grounded in number theory's intrinsic periodicity. 3. Throne and chasm coexist: in principle, public-key cryptography's foundation can be broken; in practice it needs a fault-tolerant, million-qubit machine that doesn't exist today — the "threat" is mathematical, not a calendrical matter (episode 039 expands on this).
Hook for the next stop: the four-step flow is complete — how do we build the one custom part, the "modular-exponentiation black box"? What does the circuit look like, how many gates does it need, where does the bill get expensive? Episode 038, "Shor II: Circuits and Cost."