Shor's algorithm, published by Peter Shor in 1994, efficiently factors large integers and computes discrete logarithms on a quantum computer, with exponential speedup over the best known classical algorithms. This is significant because the security of RSA encryption and many other public-key cryptographic systems relies on the classical intractability of factoring large numbers. A sufficiently powerful quantum computer running Shor's algorithm could break RSA-2048 in hours, compared to the billions of years estimated for classical supercomputers.
The algorithm works by reducing the factoring problem to finding the period of a modular exponential function, then using the quantum Fourier transform to identify the period efficiently. The quantum part of the algorithm requires approximately 2n+3 logical qubits to factor an n-bit number (roughly 4,100 logical qubits for RSA-2048), with a circuit depth of O(n³) gates. With fault-tolerant implementation using surface codes, estimates suggest that 10-20 million physical qubits would be needed, depending on physical error rates and code efficiency.
Despite being the most famous quantum algorithm, Shor's algorithm is far from practical implementation today. The largest number factored by a quantum computer using Shor's algorithm is 21 (= 3 x 7), though some compiled demonstrations have factored slightly larger numbers with classical assistance. The threat to cryptography is nevertheless taken seriously — NIST finalized post-quantum cryptography standards in 2024 (FIPS 203, 204, 205), and migration to quantum-resistant algorithms is underway across governments and industry. The timeline for a cryptographically relevant quantum computer is estimated at 10-20 years, though this range carries substantial uncertainty.