Which of the locks from topics 01 to 06 does a quantum computer open?
What Shor's algorithm takes and what it leaves, the two families of replacement (lattices and hashes) and what they weigh, and the order in which a real system moves. This is the section the tools on the post-quantum page put into practice.
In 1994 Peter Shor noticed that factoring and the discrete logarithm are, underneath, the same kind of problem: a function hides a repeating pattern, and finding the period of the pattern gives the answer. A classical computer has no known shortcut to a period. A quantum computer does: put an input register into an equal superposition, compute the function, and a Fourier transform concentrates the amplitude on multiples of the inverse period, so a handful of measurements reveal it.
For factoring, the repeating function is ax mod N, and its period r is the order of a. When r is even, the number ar/2 is a square root of 1 modulo N, and unless it is the trivial one (−1), the two gcds of it with N, shifted by one each way, hand back the factors. For the discrete logarithm the function has a two-dimensional hidden period, and the secret exponent is the direction it points in. Elliptic-curve cryptography has the same structure and, because its keys are shorter, falls with a smaller machine.
The consequence is stark and also narrow. Everything built on these three problems goes: RSA, Diffie-Hellman, ECDH, ECDSA, EdDSA, which is the whole of today's public-key infrastructure. Symmetric ciphers and hashes do not hide a period for the algorithm to find, so they only meet Grover's square root, as topics 02 and 03 showed.
Factoring by the order. Take N = 3233 and a = 7. The order r is the least r with 7r ≡ 1 (mod 3233); walking the powers gives r = 780, which is even. Then x = 7390 mod 3233 = 2439, which is neither 1 nor −1 (3232), so
gcd(x − 1, N) = gcd(2438, 3233) = 53 gcd(x + 1, N) = gcd(2440, 3233) = 61
and 53 × 61 = 3233. The quantum computer's only job in this recipe is the step that is hard classically, finding r; the rest is arithmetic a school could do. Topic 13 of The Machinery derives how the period is read off the measurement, and Shor's Clockwork lets you build the chain of multiplications that computes ar/2 in the fewest steps.
The discrete log as a period. In the Diffie-Hellman toy (p = 23, g = 5, A = 8) define f(x, y) = 5x · 8−y mod 23. Since 8 = 56, we get f(x + 6, y + 1) = f(x, y) for every pair: the function repeats along the direction (6, 1), and the secret exponent 6 is that direction. A quantum computer finds the hidden direction of a two-dimensional period the way it finds a one-dimensional one.
The price of the machine. What it takes to run this at a real size has fallen quickly. For a 2,048-bit RSA key, Gidney and Ekerå estimated in 2019 about 20 million noisy physical qubits running for about 8 hours; Gidney's 2025 estimate is under one million qubits and under a week. Shor's method did not change; the arithmetic circuit and the error correction around it did (approximate residue arithmetic, denser storage of idle qubits, cheaper magic states), trading a longer runtime for far fewer qubits. Neither number is a prediction of when such a machine exists, which is the open question that sets the migration deadline.
Nowhere yet, at this size The largest numbers factored by running Shor's algorithm on real quantum hardware are tiny, and a machine that threatens a 2,048-bit key does not exist. The reason to act now is not that it does, it is the recording problem of topic 06 plus the speed at which the estimates keep falling.
On this site The Harvest Clock turns Mosca's inequality into a decision, the Bitcoin page applies this to a real system, and the Q-Day quest on the Secure hub walks the chain from headline to forecast. If you want to feel the classical half of the algorithm, Shor's Clockwork is that.
Check yourself
Shor's algorithm threatens RSA, Diffie-Hellman and elliptic-curve cryptography. What do those three share that AES and SHA-256 lack?
Factoring and both discrete logarithms are period-finding problems, which a quantum computer solves in polynomial time using the Fourier transform. AES and SHA-256 hide no such period, so they only meet Grover's square root.