Remainders — “mod”
17 mod 12 = 5 — divide, keep only the leftover. It's clock arithmetic: 17 o'clock is 5 o'clock. “mod N” just means numbers wrap around at N.In 1994 Peter Shor showed that a quantum computer could factor huge numbers exponentially faster than any known classical method — which is exactly the problem RSA encryption bets its life on. Here's how it works, one idea at a time — every concept explained from scratch, and everything computed live on this page.
RSA public keys are built on a one-way street: pick two big primes p and q, publish their product N = p·q. Multiplying them takes microseconds. Recovering p and q from N — factoring — is where every known classical method chokes: the runtime of even the best algorithm explodes as the key grows.
Shor's algorithm needs a number of steps that grows only gently with the number of digits — the difference between “longer than the universe” and “an afternoon”. Drag the key size and watch the gap open up:
Back-of-envelope asymptotics only — real quantum hardware pays huge overheads for error correction. The point is the shape: one curve explodes, the other doesn't.
Two everyday tools are all the math this page needs:
17 mod 12 = 5 — divide, keep only the leftover. It's clock arithmetic: 17 o'clock is 5 o'clock. “mod N” just means numbers wrap around at N.gcd(12, 18) = 6 — the largest number dividing both. Crucially, computers find it near-instantly even for 600-digit numbers (a 2,300-year-old method by Euclid).Now the key move — no quantum yet. Pick any number a that shares no factor with N. Start at 1 and repeatedly multiply by a, each time keeping only the remainder mod N. The sequence always falls into a repeating loop, and the length of that loop, r, is called the period.
Why care about the period? Here's the trick. If r is even, jump to the loop's halfway point: h = a^(r/2) mod N. Squaring h completes the loop, so h² leaves remainder 1 — meaning h² − 1 is an exact multiple of N. But h² − 1 splits neatly into (h−1) × (h+1). So the prime factors of N must be hiding inside those two numbers, and “find the factor I share with N” is precisely the job gcd does in a flash. Play with it:
So the whole problem collapses to: find the period r. Classically that's no easier than factoring — for a 2048-bit N the period is astronomically long and the sequence looks like noise until it repeats. You'd have to walk it. This is where the quantum computer comes in: it doesn't walk the sequence, it hits all of it at once and reads the rhythm off the interference pattern.
A classical n-bit register holds one of 2ⁿ values. A quantum register of n qubits holds a superposition: an amplitude (a complex number) for each of the 2ⁿ values, all at the same time. When you measure it, you get one value at random — with probability equal to its amplitude squared. The art of quantum algorithms is choreographing amplitudes so that, by measurement time, the probability piles up on answers you want.
Shor's machine uses two registers. Register 1 is put into an equal superposition of every x from 0 to Q−1 (where Q is a power of two picked comfortably bigger than N², so many loops fit inside). Then a circuit computes f(x) = aˣ mod N into register 2 — once, acting on the whole superposition:
| Register 1 (x) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | … |
|---|---|---|---|---|---|---|---|---|---|
| Register 2 (7ˣ mod 15) | 1 | 7 | 4 | 13 | 1 | 7 | 4 | 13 | … |
Measuring register 2 returns some value, say 4 — and the superposition in register 1 collapses to exactly the x's that map to it: 2, 2+r, 2+2r, … An evenly spaced ladder of values — one rung every r steps. The period is now encoded in register 1. One problem: measuring register 1 would give you a single random member of that progression, which tells you nothing. You can't read a rhythm from one drumbeat.
What we need now is a rhythm detector: something that takes an evenly spaced pattern and answers “how far apart are the beats?” A prism does this for light, splitting it into its hidden colors; your ear does it for sound, hearing a pitch inside a wiggling air wave. The quantum version is the quantum Fourier transform (QFT), and it reads the rhythm of the amplitudes themselves — all of them at once, absurdly cheaply.
Here's how it detects rhythm. Each possible output k gets a score, computed by adding up one arrow per surviving x. Each arrow is rotated a fixed step more than the one before it — and the size of that step depends on k. Drag k and watch the arrows:
For most k's the arrows fan out around the circle and cancel to almost nothing — near-zero chance of measuring that k. But for a few special k's the rotation steps line every arrow up in the same direction: they reinforce — constructive interference — and the probability spikes. Those special k's are precisely the ones “in tune” with the ladder's spacing: multiples of Q/r. The period leaves a fingerprint you can measure.
Measure register 1 and you get one of those spikes: a k where k/Q sits extremely close to some simple fraction c/r — with the period r as its bottom number. Recovering the simple fraction hiding inside a messy decimal is an old, fast, classical trick — the same instinct that recognizes 0.333333… as ⅓ (the formal name is “continued fractions”). Try it — this is a faithful simulation of the real machine's output:
Time to put the pieces together. Note what's classical and what's quantum: the quantum computer does one narrow job — period-finding. Everything around it is ordinary code. And it's probabilistic: bad luck (odd period, useless measurement) just means retry, and the expected number of retries is small.
Not today. Factoring a real 2048-bit key with Shor needs thousands of logical qubits, which after error correction means millions of physical ones running for hours — well beyond current machines, which are in the hundreds-to-thousands of noisy physical qubits. The record numbers genuinely factored by Shor's algorithm on hardware are still tiny (think 15 and 21, like this page).
But the math is not in doubt, which is why the migration already started: NIST standardized post-quantum schemes (ML-KEM, ML-DSA — lattice-based, no known quantum speedup) in 2024, and "harvest now, decrypt later" is the reason long-lived secrets are being re-encrypted years before any such machine exists.
The one-sentence takeaway: Shor's algorithm turns factoring into rhythm-detection, and quantum interference is a physically native rhythm detector.