Breaking the locks

When you buy something online, your browser and the shop agree on a secret using a scheme called RSA, or a cousin of it. RSA's lock is a number that is two large primes multiplied together. Anyone can see the number. Finding the two primes, for the sizes used in practice, would take ordinary computers longer than the universe has existed.

Peter Shor's idea, in 1994, was to turn factoring into finding a rhythm. Pick a number, say 7, and keep raising it to higher powers, dividing by the lock number each time and keeping the remainder. For lock number 15 the remainders go 7, 4, 13, 1, 7, 4, 13, 1. The pattern repeats every 4. That repeat length, called the period, is enough to work out the primes with a bit of ordinary arithmetic. For 15 it gives 3 and 5.

For a big lock number the period is astronomically long and an ordinary computer would take forever to spot it. A quantum computer puts all the powers in superposition at once, and then applies a quantum version of the tool engineers use to find the pitch of a sound, the Fourier transform. The rhythm shows up as interference: every period-length that is wrong cancels out, and the right one is what you measure.

Nobody has broken a real key this way. The largest number factored by an honest run of Shor's method is small enough to do in your head. The estimates for breaking a real 2048-bit RSA key have come down over the years, from tens of millions of noisy qubits to about a million as of 2025, running for a week or so. The machines that exist are hundreds of times too small and far too noisy.

Governments did not wait. In 2024 NIST published new lock designs that do not rest on factoring, and banks, browsers and phone makers are switching now. The reason to switch early is called harvest now, decrypt later: anything recorded today can be opened whenever the machine arrives.