Shor's Algorithm & the QFT

Factoring = period finding

Factoring a big number — splitting something like 15 into 3 x 5 — feels like a search problem, and for huge numbers it's so slow on ordinary computers that we build cryptography on its difficulty. Shor's key insight is that you don't have to search at all. Factoring can be rewritten as a different question: finding the *period* of a repeating sequence. And finding periods is exactly the kind of structured task a quantum computer can do well.

Here's the bridge. Pick a number you want to factor, call it N, and pick some smaller number a. Now look at the sequence of remainders you get from a^1, a^2, a^3, ... after dividing by N. That sequence always eventually repeats, and the length of one cycle is called the period, r. The remarkable fact from number theory is that once you know r, a little ordinary arithmetic turns it into the factors of N. So the whole hard problem collapses into one question: what is the period r?

a^1 a^2 a^3 a^4 a^5 a^6 a^7 a^8 ...
 mod N: 7   4   13  1   7   4   13  1  ...
        \___________/\___________/
            period r = 4 (it repeats)

The quantum Fourier transform

How do you find a period? Think of how a music app finds the pitch of a note: it takes a wiggling signal and asks *which frequencies it's made of*. A repeating pattern shows up as a sharp spike at its frequency. The quantum Fourier transform (QFT) does the same thing, but on a register of qubits prepared in a particular state: it converts 'repeats every r steps' into a state whose measurement is likely to land on values tied to that period.

The reason this is powerful is interference, not parallel guessing. The qubits are prepared in a superposition that quietly encodes the periodic pattern across many values at once. The QFT then makes the wrong answers cancel out and the right ones reinforce — like ripples in a pond meeting so that most crests flatten and a few add up tall. Only after that careful cancellation do you measure.

      ___              ___
|0>--|   |--[ QFT ]--|   |==> measure
|0>--| U |          |   |==> measure
|0>--| a |          |QFT|==> measure
|0>--|___|--........-|___|==> (read out a value
                            related to the period r)

Putting it together

1. Pick N (the number to factor) and a random a smaller than N. Do a quick classical check; sometimes you get lucky and find a factor with no quantum work at all.
2. On the quantum computer, build a superposition and apply the modular-exponentiation step so the register encodes the repeating remainder pattern of a's powers mod N.
3. Apply the QFT so interference concentrates the amplitude on outcomes tied to the period r.
4. Measure once. You get a single value; classical post-processing (a continued-fractions step) turns it into a candidate for the period r.
5. Use r with ordinary arithmetic to compute the factors of N. If this attempt fails — which happens sometimes — pick a new a and repeat. A few tries almost always succeeds.

Notice the rhythm: classical setup, one focused quantum subroutine, classical cleanup, and a retry loop. The quantum step is the only part nothing classical can do efficiently, and it works because the period is *structure the QFT can exploit* — not because the machine brute-forces every possibility.

Why RSA is at risk

RSA and related public-key systems rest on a bet: that factoring a large number (or the closely related problem behind elliptic-curve crypto) is so slow that no one can do it within a human lifetime. The best classical factoring methods take time that grows almost exponentially with the size of the number, which is why a long enough key is considered safe today.

Shor breaks that bet. For this structured problem, it turns the near-exponential classical cost into something that grows only polynomially — a genuine exponential speedup for factoring specifically. A large, reliable quantum computer running Shor could in principle recover a private key from its public counterpart, which is why people talk about it 'breaking RSA.' The response is post-quantum cryptography: new classical algorithms, built on math problems (like certain lattice problems) that Shor's period-finding trick does *not* crack.

The catch: you need a big fault-tolerant machine

All of that is the theory. The practical reality is humbling. Today's machines are in the NISQ era — noisy, with only a modest number of qubits and short coherence times — and they make far too many errors to run Shor on a cryptographically meaningful number. The largest numbers factored by a real quantum computer running Shor honestly are tiny, nothing close to a real RSA key.

The blocker isn't cleverness, it's reliability. Running Shor on a 2048-bit key needs millions of well-behaved physical qubits, because you have to wrap fragile physical qubits in error correction to build a handful of stable logical qubits. Schemes like the surface code can reach fault tolerance only once physical error rates drop below about 1%, and each logical qubit then costs thousands of physical ones. We are not there yet — estimates for breaking RSA land years to decades out.