Shor's Algorithm

Core Idea

Shor's algorithm factors an n-bit integer in polynomial time O(n³) on a quantum computer, compared to the best known classical algorithms which are sub-exponential. It works by reducing factoring to period finding: given N to factor, choose a random a coprime to N and find the period r of the function f(x) = a^x mod N using the quantum Fourier transform. From the period, factors of N can be extracted with high probability using classical number theory. Shor's algorithm threatens RSA and other cryptosystems whose security relies on the assumed classical hardness of factoring.

Explainer

Shor's algorithm is the most consequential quantum algorithm known, because it breaks the RSA cryptosystem whose security assumption is that factoring large integers is computationally hard. The algorithm runs in polynomial time on a quantum computer, while the best known classical algorithms for factoring (the general number field sieve) run in sub-exponential time exp(O(n^1/3 * (log n)^2/3)). If a sufficiently large quantum computer is built, RSA, Diffie-Hellman, and elliptic curve cryptography all become insecure.

The algorithm has a classical reduction and a quantum subroutine. The classical reduction uses number theory: to factor N, pick a random a < N with gcd(a, N) = 1. Find the order r of a modulo N — the smallest positive integer r such that a^r = 1 (mod N). If r is even and a^r/2 != -1 (mod N), then gcd(a^r/2 - 1, N) and gcd(a^r/2 + 1, N) are nontrivial factors of N. This reduction works with probability at least 1/2 over the random choice of a. The hard step — finding r — is where the quantum computer comes in.

The quantum subroutine creates the state (1/sqrt(2ⁿ)) sum_{x=0}^{2ⁿ - 1} |x>|a^x mod N> using controlled modular exponentiation, then applies the quantum Fourier transform to the first register. Before the QFT, the first register (conditioned on the second register's measurement) is a periodic superposition with period r. After the QFT, the amplitude is concentrated at values near multiples of 2ⁿ/r. Measuring gives a value c approximately equal to j * 2ⁿ/r for some random integer j. From the fraction c/2ⁿ, the continued fraction algorithm extracts r (as the denominator of the best rational approximation with small denominator).

The resource cost is substantial but polynomial. The circuit requires O(n) qubits (where n = log N), and the modular exponentiation uses O(n³) gates (the most expensive part). The QFT itself costs only O(n²) gates. The total time is O(n³) quantum gates plus O(n³) classical post-processing. Current quantum hardware is far from factoring cryptographically relevant numbers (2048-bit RSA requires thousands of logical qubits, which in turn require millions of physical qubits with error correction). Shor's algorithm has been demonstrated on small numbers (factoring 15, 21) as proof-of-concept experiments. The practical threat timeline depends on advances in quantum hardware and error correction, but the theoretical result has already motivated the development of post-quantum cryptography — lattice-based and other schemes believed to be hard even for quantum computers.