How does Shor's algorithm solve factoring problems exponentially faster than classical algorithms?

Shor’s algorithm solves factoring problems exponentially faster than classical methods by reducing factoring to a period-finding problem and leveraging quantum computing techniques like superposition and the Quantum Fourier Transform (QFT). Classical factoring algorithms, such as the general number field sieve, require time that grows exponentially with the number of digits in the input, making them impractical for large numbers. Shor’s algorithm, in contrast, runs in polynomial time because it replaces exhaustive search with a quantum subroutine that identifies patterns in modular arithmetic efficiently.

The algorithm works by first selecting a random integer a that is coprime with the number N to be factored. If a shares a factor with N, the problem is solved immediately. Otherwise, Shor’s algorithm seeks the smallest integer r (called the period) such that aʳ ≡ 1 mod N. Finding this period classically would involve evaluating aˣ mod N for increasing x until a repeat is detected—a process that scales exponentially with the size of N. Quantum computers avoid this bottleneck by using superposition: a quantum register evaluates aˣ mod N for all x simultaneously. The QFT then extracts the period r from this superposition by amplifying the correct frequency, a step that scales polynomially with the number of digits in N.

For example, to factor N=15, Shor’s algorithm might pick a=7. The sequence 7¹ mod 15=7, 7²=49 mod 15=4, 7³=28 mod 15=13, 7⁴=91 mod 15=1 reveals a period r=4. Using r, classical steps compute gcd(7^(4/2)±1, 15), yielding factors 3 and 5. The quantum speedup comes from finding r in O((log N)³) time versus classical methods, which require O(exp((log N)^(1/3))) time. This efficiency gap grows exponentially for larger N, making Shor’s algorithm transformative for cryptography, where large primes are foundational. The algorithm’s structure—quantum period-finding followed by classical post-processing—demonstrates how hybrid quantum-classical approaches tackle otherwise intractable problems.