Shor's Algorithm

Shor's algorithm is usually introduced as "the quantum algorithm that factors numbers", which is true and also slightly misleading, because the factoring is not where the quantum computer earns its keep. The algorithm is a classical reduction wrapped around one quantum subroutine, and the subroutine does not know what factoring is. It finds the period of a periodic function. That is all it does.

Here is the reduction. Suppose you want to factor N. Pick a random integer a with 1 < a < N. Compute gcd(a, N) — if that is not 1 you have stumbled onto a factor by luck and you are done, which essentially never happens for the semiprimes RSA uses. Otherwise, consider the function f(x) = a^x mod N. Because a and N are coprime, this function is periodic: there is some smallest r > 0 with a^r ≡ 1 (mod N), and thereafter f repeats with period r. That r is called the multiplicative order of a modulo N.

Now do a little algebra. If r happens to be even, then a^r − 1 ≡ 0 (mod N) factors as (a^{r/2} − 1)(a^{r/2} + 1) ≡ 0 (mod N). So N divides that product. Unless one of the two factors is itself a multiple of N — the failure case, which is what you get when a^{r/2} ≡ −1 (mod N) — the factors of N must be split between the two brackets. Compute gcd(a^{r/2} − 1, N) and gcd(a^{r/2} + 1, N) and at least one of them is a non-trivial factor of N.

That is the whole classical part, and it is genuinely elementary — Euclid's algorithm and one line of high-school algebra. The failure modes (r odd, or a^{r/2} ≡ −1) happen with probability at most about 1/2 for a random a, so you retry with a fresh a and succeed after a couple of attempts on average. Everything difficult has been pushed into one place: finding r. Classically, finding the order of a modulo N is believed to be as hard as factoring itself, and no sub-exponential algorithm for it is known. Quantumly, it is the natural thing a quantum computer does.