Shor's Algorithm
The 1994 algorithm that factors large numbers exponentially faster than classical methods, threatening RSA. The reason quantum computing has a defense budget.
Shor's algorithm, published by Peter Shor in 1994, factors large numbers exponentially faster than any known classical method. Since RSA encryption, much of the internet's lock-and-key infrastructure, rests on factoring being hard, Shor's algorithm is the reason quantum computing has a defense budget.
The gap between threat and capability remains vast. Factoring a 2048-bit RSA key is estimated to require millions of physical qubits running error-corrected for hours. Current machines have hundreds to thousands of qubits and no fault tolerance at scale. The largest number genuinely factored by Shor's algorithm to date remains laughably small.
So why care now? 'Harvest now, decrypt later': adversaries can record encrypted traffic today and decrypt it when machines mature. That logic, not imminent capability, drives the post-quantum cryptography migration.