Shor's Algorithm

Shor's algorithm is a quantum algorithm for integer factorization that runs in polynomial time — specifically, O((log N)^3) operations for factoring an N-bit integer. It was discovered by Peter Shor in 1994 and remains the paradigmatic example of exponential quantum speedup over any known classical algorithm. The algorithm's structure is elegant: it reduces the apparently intractable problem of factoring to the tractable problem of period-finding, and then solves the period-finding problem using the Quantum Fourier Transform.

The reduction works by choosing a random integer a coprime to N and computing the period r of the function f(x) = a^x mod N. If r is even and a^{r/2} ≠ −1 mod N, then gcd(a^{r/2} ± 1, N) yields a non-trivial factor of N. The quantum speedup comes entirely from the QFT's ability to extract this period from a superposition of states in polynomial time.

Shor's algorithm is not merely a faster way to factor. It demonstrates that the security of RSA and other public-key cryptosystems is not a mathematical certainty but a contingent fact about classical computation. If a scalable quantum computer is built, these cryptosystems become transparent. The algorithm is therefore as much a result in the computational complexity of security as it is in quantum computing.

The common framing of Shor's algorithm as a 'threat to cryptography' misses the deeper point: it reveals that the hardness of factoring was never a fundamental physical law, but a boundary drawn by the computational limitations of classical machines. Quantum mechanics does not break mathematics; it redraws the map of what is efficiently computable, and that map has political consequences.

See also: Integer Factorization, Quantum Fourier Transform, Quantum Phase Estimation, Computational Complexity, RSA Cryptosystem