What is Shor's algorithm?

Why factoring matters

Multiplying two large prime numbers is easy. Going backwards, taking the product and finding the two primes, is extremely hard. For a number around 600 digits long, the size used in RSA keys, the best known classical method, the general number field sieve, is far beyond the reach of every computer on Earth.

The RSA encryption system relies on exactly that difficulty. So when Peter Shor showed in 1994 that a quantum computer could factor numbers efficiently, in a time that grows only polynomially with the number of digits, it became the most famous result in quantum computing.

The trick: turn factoring into finding a pattern

Shor's key insight is that factoring a number N can be reduced to finding the period of a repeating sequence. The steps are:

1. Pick a random number a smaller than N.
2. Look at the sequence a¹, a², a³, … each taken modulo N (the remainder after dividing by N). This sequence always repeats eventually. Call the length of the cycle r, the period.
3. If r is even, work out a^(r/2) modulo N, then take the greatest common divisor of N with that number plus one and with that number minus one. With good probability, this gives you the factors of N.

Steps 1 and 3 are easy on an ordinary computer. Step 2, finding the period, is the hard part, and it is the only part that needs a quantum computer.

A worked example: factoring 15

Take N = 15 and pick a = 7. Work out the powers of 7, keeping the remainder after dividing by 15:

• 7¹ = 7
• 7² = 49, which leaves 4
• 7³ leaves 4 × 7 = 28, which leaves 13
• 7⁴ leaves 13 × 7 = 91, which leaves 1

The sequence goes 7, 4, 13, 1 and then repeats, so the period is r = 4.

Now 7^(r/2) = 7² leaves 4. The greatest common divisor of 15 and 4 − 1 = 3 is 3, and of 15 and 4 + 1 = 5 is 5. And indeed 15 = 3 × 5.

For 15 you can find the period by hand. For a number with 600 digits, the period can be astronomically long, and no classical computer can find it in reasonable time.

Where the quantum part comes in

The quantum computer finds the period like this:

1. Put a register of qubits into a superposition of every value of x.
2. Compute aˣ modulo N into a second register, for all those values at once. The two registers become entangled.
3. Apply the quantum Fourier transform to the first register. Just as a classical Fourier transform picks out the frequencies in a sound, this makes amplitudes interfere so that only values related to the period survive.
4. Measure. The result, processed with a classical method called continued fractions, reveals r after a few repetitions.

Note what the speedup relies on: not "trying every answer at once", but interference that concentrates the amplitudes onto the answers that reveal the period.

How big a quantum computer does it need?

Far bigger than any that exists. Running Shor's algorithm on the 2048-bit numbers used in real RSA keys needs billions of operations without errors, which requires quantum error correction. A 2025 estimate by Craig Gidney of Google put the cost at under a million noisy physical qubits running for under a week. Today's machines have at most a few thousand physical qubits, with error rates still too high for that scale.

In practice, Shor's algorithm has only been demonstrated on tiny numbers such as 15 and 21.

What happens next

Because a large enough machine would break RSA and elliptic-curve cryptography, governments and tech companies are already moving to new post-quantum encryption. Can quantum computers break encryption? covers what is at risk and what is being done.