How does Shor's algorithm work?

Multiplying two large prime numbers is easy. Going backwards, finding the two primes from their product, is extremely hard for ordinary computers when the numbers have hundreds of digits. The RSA encryption that has protected much of the internet since the late 1970s relies on that difficulty. Shor's algorithm, published by Peter Shor in 1994, would make it easy for a large enough quantum computer.

Shor turned factoring into a different question: find the period of a repeating pattern. Take the number to factor, say 15, and pick any smaller number, say 7. Work out 7, 7×7, 7×7×7 and so on, each time keeping only the remainder after dividing by 15:

• 7 → 7
• 7² = 49 → 4
• 7³ = 343 → 13
• 7⁴ = 2,401 → 1
• 7⁵ → 7 again, and the pattern repeats.

The pattern 7, 4, 13, 1 repeats every 4 steps. The period is 4.

The two numbers do different jobs. 15 is the number you want to split, and you only ever divide by it. 7 is just a starting point, and a different start can give a different period: start from 4 and the remainders go 4, 1, 4, 1, so the period is 2.

1. A period of 4 means 7⁴ leaves a remainder of 1 when you divide by 15. So 7⁴ − 1, which is 2,400, divides exactly by 15.

2. 2,400 splits neatly into two pieces, one either side of 7²: (7² − 1) × (7² + 1) = 48 × 50. That's why you halve the period: half of 4 is 2, and 7² is 49.

3. 15 divides 48 × 50, but it doesn't divide 48 or 50 on its own. So 48 and 50 share 15's factors between them: part of 15 hides inside 48 and the rest inside 50.

4. Pull them out by finding the biggest number each piece shares with 15. Euclid's method does that without knowing any factors, using only division and remainders. Divide the bigger number by the smaller one, then divide the smaller one by the remainder, and repeat until the remainder is 0. The last number you divided by is the answer.

   • 48 and 15: 48 ÷ 15 is 3, remainder 3. Then 15 ÷ 3 is 5, remainder 0. The answer is 3.
   • 50 and 15: 50 ÷ 15 is 3, remainder 5. Then 15 ÷ 5 is 3, remainder 0. The answer is 5.

   And 3 × 5 = 15.

Sometimes 15 divides one of the pieces on its own, or the period is odd. Then that start is useless, and you pick another.

Step 4 never needed to know that 15 is 3 × 5. That matters, because for a 600-digit number nobody knows the factors: that's the whole problem. Euclid's method is over 2,000 years old, and even with 600-digit numbers it takes at most a few thousand quick steps.

So every step after the period is quick for an ordinary computer. Finding the period is the only hard part. That's the quantum computer's job.

The same four steps, three times.

• Split 15, start from 7. The remainders go 7, 4, 13, 1, so the period is 4. Half of 4 is 2, and 7² = 49. Either side: 48 and 50. Euclid's method finds 3 for 48 and 15, and 5 for 50 and 15. So 15 = 3 × 5.
• Split 21, start from 2. The remainders go 2, 4, 8, 16, 11, 1, so the period is 6. Half of 6 is 3, and 2³ = 8. Either side: 7 and 9. Euclid's method finds 7 for 7 and 21, and 3 for 9 and 21. So 21 = 3 × 7.
• Split 35, start from 4. The remainders go 4, 16, 29, 11, 9, 1, so the period is 6. Half of 6 is 3, and 4³ = 64. Either side: 63 and 65. Euclid's method finds 7 for 63 and 35, and 5 for 65 and 35. So 35 = 5 × 7.

For 15 you can find the period by hand. For a 600-digit number the pattern can be astronomically long, and no ordinary computer can trace it. A quantum computer works on all positions of the pattern in superposition, then applies a step called the quantum Fourier transform, which makes the amplitudes interfere so that only answers related to the period survive (chapter 4). One measurement reveals the period with good odds. Everything else is ordinary arithmetic.

In 2001 an IBM team factored 15 using molecules in a liquid as qubits. Since then, small demonstrations have factored a few slightly larger numbers, often with shortcuts that only work because the answer is already known. Factoring numbers used in real encryption needs a large error-corrected machine, estimated at under a million noisy qubits running for under a week in a 2025 study. Chapter 13 covers the threat and the switch to new encryption.