The Problem That Launched a Revolution
In 1994, mathematician Peter Shor showed that a quantum computer could factor integers exponentially faster than any known classical algorithm. This single result transformed quantum computing from a theoretical curiosity into an urgent national security concern, because RSA encryption — the backbone of internet security — relies entirely on the difficulty of factoring large numbers. Shor's algorithm remains the most compelling evidence that quantum computers can solve important problems beyond classical reach.
From Factoring to Period-Finding
Shor's key insight was that factoring reduces to finding the period of modular exponentiation. Given N to factor, choose random a and find the smallest r such that a^r ≡ 1 (mod N). If r is even, then a^{r/2} ± 1 share non-trivial factors with N. The quantum part only needs to find this period r — everything else is classical. The reduction from factoring to period-finding was known classically; the quantum breakthrough was making period-finding efficient.
Quantum Fourier Transform
The heart of Shor's algorithm is the quantum Fourier transform (QFT), which maps computational basis states to frequency space. After preparing a superposition of a^x mod N for all x simultaneously (quantum parallelism), the QFT reveals the period as sharp peaks in the probability distribution. Measuring these peaks and using continued fractions extracts r with high probability. This simulation visualizes the QFT output peaks and how they correspond to the period.
The Road to Cryptographic Relevance
Factoring RSA-2048 requires about 4,000 error-corrected logical qubits, each encoded in thousands of physical qubits. Current quantum computers have hundreds of noisy physical qubits — a gap of roughly five orders of magnitude. Post-quantum cryptography standards (lattice-based, hash-based) are being deployed now in anticipation of future quantum computers. The race between quantum hardware and post-quantum migration defines modern cybersecurity strategy.