Shor's algorithm (conceptual)

In 1994, Peter Shor showed that a quantum computer can factor a large integer in polynomial time. This was the result that turned quantum computing from a curiosity into a national-security-level priority — because the hardness of factoring is the foundation of RSA, the most widely used public-key encryption algorithm on the Internet.

RSA relies on: given a large number $N$ that’s the product of two unknown primes $p$ and $q$, finding $p$ and $q$ is classically hard. The best known classical algorithm (the general number field sieve) runs in sub-exponential time $2^{O((\log N)^{1/3})}$, which is enough to protect 2048-bit keys against all known classical computers for the foreseeable future.

Shor’s algorithm factors $N$ in time $O((\log N)^3)$ on a quantum computer — polynomial, not sub-exponential. A large-enough quantum computer would break RSA.

This lesson walks through Shor’s algorithm at a conceptual level. The full details involve modular exponentiation, the QFT, and number theory — more than we can fit here. But the key idea is simple, and it’s the same trick as Simon’s algorithm from earlier.

The reduction: factoring → period finding

Shor’s crucial insight is that factoring can be reduced to a period-finding problem. Here’s the setup:

1. Pick a random integer $a$ with $1 < a < N$ and $\gcd(a, N) = 1$. (If $\gcd(a, N) > 1$, you already have a factor of $N$, and you’re done — but this is rare.)
2. Consider the function $f(x) = a^x \mod N$. This function is periodic: there exists some smallest $r$ (the order of $a$ modulo $N$) such that $f(x + r) = f(x)$ for all $x$.
3. If you can find $r$, and if $r$ is even and $a^{r/2} \neq -1 \pmod N$, then $\gcd(a^{r/2} - 1, N)$ is a non-trivial factor of $N$ — and you’ve factored $N$.

The “if” conditions happen with probability at least $1/2$ for random $a$, so repeating the process a few times is enough to factor $N$ with high probability.

So factoring reduces to: find the period $r$ of $f(x) = a^x \mod N$.

The period-finding algorithm

Classically, finding the period of $f(x) = a^x \mod N$ takes roughly $\sqrt{r}$ time (birthday-style collision search) — which is essentially as hard as factoring directly.

Quantumly, using the QFT, you can find the period in polynomial time. The algorithm is:

1. Prepare two quantum registers: an input register of $\sim 2\log N$ qubits, and an output register of $\sim \log N$ qubits. The input register starts in a uniform superposition over $\{0, 1, \ldots, Q-1\}$ where $Q \approx N^2$.
2. Apply the oracle computing $f(x) = a^x \mod N$ into the output register.
3. Measure the output register. This leaves the input register in a superposition of all $x$ with the same function value — an arithmetic progression of period $r$.
4. Apply the quantum Fourier transform to the input register.
5. Measure the input register.

The measurement outcome is a value $c$ such that $c/Q$ is close to $k/r$ for some integer $k$. Using the classical continued fractions algorithm, you can extract $r$ from $c/Q$ with high probability in a few attempts. Total quantum resources: polynomially many qubits and gates.

Why the QFT extracts the period

The key fact is that the quantum Fourier transform of an evenly-spaced arithmetic progression with period $r$ produces a state concentrated at frequencies that are multiples of $1/r$. In other words, the position-basis representation “an arithmetic progression with period $r$” transforms into a frequency-basis representation “a comb of peaks at $k/r$ for integer $k$.” Measure the frequency, divide out, and you get $r$.

This is exactly analogous to how a classical FFT converts a periodic signal into a spectrum with peaks at the fundamental frequency and its harmonics. The only difference is that the quantum version is exponentially faster and works on superpositions.

What Shor actually broke

It’s tempting to say “Shor’s algorithm breaks RSA.” That’s true in principle — a quantum computer with a few thousand logical qubits and a few billion gates could factor a 2048-bit RSA modulus. But such a machine doesn’t yet exist. The largest number Shor’s algorithm has factored on a real quantum computer is… still quite small. The engineering gap between “Shor works in theory” and “Shor is a threat to real RSA deployments” is large, and closing it is a major research push.

What Shor did break, unambiguously, is the comfortable assumption that factoring was secure against all possible computers. After Shor, cryptographers began designing post-quantum algorithms that are believed to resist both classical and quantum attack. The NIST post-quantum cryptography standardization process (starting 2016, with first finalized standards in 2024) is the result. Future Internet traffic will gradually migrate to post-quantum algorithms over the coming decade, long before large-scale Shor becomes feasible.

Shor’s algorithm is also the cleanest example of the resource-theoretic power of the QFT. Any future algorithm that finds a quantum speedup by extracting “hidden periodic structure” is walking in Shor’s footsteps.

What’s next

We’ll close Module 7 with a brief tour of two “near-term” algorithms — VQE and QAOA — that don’t need full fault tolerance to run. These are the algorithms researchers are actually running on today’s noisy devices, with an eye toward useful speedups in chemistry and optimization.