Factoring large numbers is hard — the hardness that secures RSA, the lock on most of the internet. Shor's 1994 quantum algorithm makes it easy: it turns factoring into period-finding, and a quantum computer finds periods exponentially fast using the quantum Fourier transform. Pick a number, watch the period of aˣ mod N reveal itself as a comb of QFT peaks, then read off the factors.
a coprime to N and consider the function f(x) = aˣ mod N. Because the integers mod N form a finite group, f is periodic: f(x+r) = f(x) where r is the order of a (the smallest r with aʳ ≡ 1 mod N).
a^(r/2) ≢ −1 mod N, then a^(r/2) − 1 and a^(r/2) + 1 share nontrivial factors with N. Compute gcd(a^(r/2) ± 1, N) — those gcds are the factors. So factoring reduces to finding r.
aˣ mod N in superposition, and applies the quantum Fourier transform. The QFT of a periodic function is a comb of sharp peaks at multiples of Q/r (Q is the register size). One measurement lands on a peak k ≈ j·Q/r; the continued-fraction expansion of k/Q recovers r. The whole thing runs in polynomial time — about (log N)³ steps.
aˣ mod N cycling with period r; the lower panel is the QFT probability spectrum — those evenly spaced peaks are the period announcing itself.