Shor's Algorithm

Multiply two big prime numbers together and you get a much bigger number. Easy.

Now go the other way. Given only the big number, find the two primes. Nobody knows how to do that quickly, and essentially all of the internet's security is built on that fact.

In 1994, Peter Shor found a way for a quantum computer to do it. This is the result that got the whole field funded.

The surprise is not the quantum bit

Shor's real insight has nothing to do with quantum mechanics. It is a piece of ordinary number theory.

Pick any number a. Look at the sequence a, a², a³... and each time, keep only the remainder after dividing by the big number you are trying to crack.

That sequence repeats. And if you know how often it repeats, a couple of lines of school arithmetic hand you the prime factors.

So the whole problem becomes: find how often it repeats. Ordinary computers are hopeless at that. Quantum computers, as of the last lesson, are excellent at it.

The quantum step

Build up every exponent at once, work out all the remainders in one go, and look at the result. What is left behind is a pattern that repeats at exactly the interval you want.

Feed that into the rhythm-finder from the last lesson. Look. Do the arithmetic. Done.

What it would actually take

That estimate has fallen sharply — the same researcher put it at 20 million qubits in 2019. The algorithms are improving faster than the hardware.

For comparison, today's largest machines have a few hundred to about a thousand qubits, and they are considerably more error-prone than those estimates assume.