Grover's search gave a quadratic speedup. Shor's algorithm gives an exponential one — and it targets the exact mathematical problem that secures the modern internet. It is the single most consequential quantum algorithm, and the reason governments and companies are already preparing for machines that don't yet exist.
What Shor's algorithm does
Given a large integer, Shor's algorithm finds its prime factors in roughly polynomial time on a quantum computer. Classically, factoring a number with a few thousand bits is so slow it would take longer than the age of the universe — that hardness is assumed, not proven, but no fast classical method has ever been found despite centuries of effort.
The clever part uses everything from this track: it turns factoring into finding the period of a repeating function, and a quantum computer finds that period with astonishing efficiency using the quantum Fourier transform — a giant, precisely tuned interference pattern that makes the period's frequency reinforce while everything else cancels. Interference, exactly as the Core lesson promised, doing genuinely hard work.
Why this breaks today's cryptography
Recall from the Cyber Security track that RSA and Diffie–Hellman — the backbone of HTTPS, secure email and digital signatures — are secure because factoring and the discrete-logarithm problem are hard. Shor's algorithm solves both. A sufficiently large, error-corrected quantum computer could therefore:
- forge digital signatures,
- decrypt intercepted HTTPS traffic,
- and impersonate secure servers.
It is important to be precise: today's quantum computers are nowhere near big or reliable enough to do this (the next lessons explain why). But data captured now could be decrypted later — the "harvest now, decrypt later" threat — which is why the response is already urgent.
The response: post-quantum cryptography
Cryptographers aren't waiting. Post-quantum cryptography (PQC) designs new algorithms based on mathematical problems believed hard even for quantum computers (such as lattice problems). In 2024 the US NIST standardised the first PQC algorithms, and the internet has begun migrating — browsers and messaging apps are already deploying quantum-resistant key exchange. It is a rare case of the security world fixing a vulnerability years before the weapon to exploit it exists.
Shor's is the dream; the reason it isn't yet a reality is brutal engineering. Quantum states are absurdly fragile, and keeping them alive long enough to run Shor's on a real number is the central challenge — the noise problem, next.