Learn · 06
How Shor's algorithm finds factors
Multiply 61 by 53 and you get 3,233 in a few seconds. Starting from 3,233 and finding 61 and 53 takes much longer. For numbers hundreds of digits long, the gap becomes enormous: ordinary computers multiply them in a blink, but the best known methods would take longer than the age of the universe to split them. RSA encryption, which protects website certificates and software updates, relies on that gap.
Shor’s algorithm, published by Peter Shor in 1994, closes it. Most of the algorithm is ordinary arithmetic. The quantum part does one job: it finds how often a pattern repeats.
The pattern. To factor a number N, pick a smaller number a and look at the remainders of a, a², a³ and so on after dividing by N. For N = 15 and a = 7:
- 7¹ = 7, remainder 7
- 7² = 49, remainder 4
- 7³ = 343, remainder 13
- 7⁴ = 2,401, remainder 1
After a remainder of 1 the same four remainders come round again, forever: 7, 4, 13, 1, 7, 4, 13, 1. The pattern repeats every 4. That number is called the period.
From the period to the factors. Take a to the power of half the period: 7² = 49, remainder 4. One less than that is 3, and one more is 5. Each shares a factor with 15, and here they are the factors: 15 = 3 × 5. For bigger numbers the two neighbours aren’t the factors themselves, but a quick, standard calculation (the greatest common divisor) pulls the shared factor out of each. Sometimes it fails, because the period is odd or the neighbours share nothing useful. Then you pick another a and try again, and most choices of a work.
Why the period is hard. For a 617-digit number, the period can be hundreds of digits long too. Walking through the remainders one by one to find where they repeat takes about as long as factoring by any other known method.
The quantum step. A quantum computer holds a superposition of many powers x at once and computes the remainder for all of them in one pass. Measuring now would give one random remainder, which is useless. Instead, a sequence of gates called the quantum Fourier transform makes the amplitudes interfere. Powers that are a whole number of periods apart line up and reinforce each other. Everything else cancels.
What survives is a short list of likely readings, evenly spaced. With 64 possible readings and a period of 4, the only readings left are 0, 16, 32 and 48, each a quarter of the way along. Divide a reading by 64 and you get a simple fraction, here 0, 1/4, 1/2 or 3/4, and the period is hiding in its bottom number. A reading of 16 gives 1/4, so the period is 4. A reading of 32 gives 1/2, which suggests 2; checking shows 7² leaves 4 rather than 1, so you measure again.
Try both numbers. With 21, the period is 6, which doesn’t divide 64 evenly, so the readings spread over neighbouring values and the fraction has to be rounded:
On 15 and 21 an ordinary computer finds the period instantly, so the simulation gains nothing. The point is how the work grows. To find the period of a number with n digits, the quantum step needs a number of operations that grows with roughly n³. The best ordinary methods grow almost exponentially. Going from a 100-digit number to a 600-digit one multiplies the quantum work by about 200. By the usual estimate, the ordinary work goes up by a factor of about 10 billion billion.
The catch is size and reliability. Factoring a 2048-bit RSA key takes around 1,400 error-free logical qubits running for days, and with today’s error rates each logical qubit needs hundreds of physical qubits. The largest number genuinely factored by Shor’s algorithm on real hardware is still 15. The Q-Day tracker follows how quickly the estimates are falling and how quickly machines are growing.
A related version of the algorithm breaks the elliptic-curve cryptography used by Bitcoin and most web traffic, and on smaller machines than RSA needs. That’s why new post-quantum methods, built on problems that have no known repeating pattern to find, are already being rolled out.