Shor's algorithm: why RSA and elliptic curves fall

In 1994, Peter Shor, then at AT&T, found something that turned quantum computing from a physics curiosity into a security problem. He showed that a quantum computer could factor large numbers and compute discrete logarithms in polynomial time, meaning efficiently, with effort that grows gently as numbers get bigger.

From the public-key lesson you know what that means: RSA, Diffie-Hellman, DSA and elliptic-curve cryptography (ECDH, ECDSA, Ed25519) all fall. RSA: retiring after a long and distinguished career.

The surprising part is that most of Shor's algorithm is ordinary arithmetic you can do on paper. Only one step needs a quantum computer. Let's find it.

The big idea: factoring is secretly about rhythm

Take a number N you want to factor, say 15. Pick any smaller number a, say 7. Now compute powers of 7 and keep only the remainder after dividing by 15 ("mod 15"):

The sequence repeats: 1, 7, 4, 13, then 1, 7, 4, 13 again, forever. The length of the loop is called the period, written r. Here r = 4.

This always happens. For any a that shares no factor with N, the powers of a mod N eventually cycle back to 1 and repeat. Number theorists had known this for centuries. What Shor noticed is how much the period gives away.

From rhythm to factors

If r is even, take a to the power r/2. Here that's 7² = 49, which is 4 mod 15. Now look at the numbers either side of it: 3 and 5. Compute the greatest common divisor (gcd) of each with 15. The gcd is the largest number dividing both, and computers find it almost instantly, even for huge numbers, using Euclid's algorithm.

• gcd(3, 15) = 3
• gcd(5, 15) = 5

And 15 = 3 × 5. Factored. The same recipe works for numbers of any size: if you can find the period, you can factor.

Play with different N and a values. You'll hit three kinds of outcome:

• Success: an even period, and the gcd step splits N.
• Bad luck: the period is odd, or a^r/2 turns out to be −1 mod N (that is, N − 1). Then the trick gives only the useless factors 1 and N. You just pick another a and try again. For typical N most choices work, so a few tries are enough.
• Freak luck: your a already shares a factor with N, and the very first gcd hands you the answer. For a real 2048-bit key, this essentially never happens.

The quantum part: hearing the rhythm

So why can't an ordinary computer just do this? Because finding the period is the hard step. In the widget, we found r by computing powers one after another until we got back to 1. For real RSA numbers, the period can be about as large as N itself, a number hundreds of digits long. Counting to it is hopeless. No known classical method finds such periods efficiently.

A quantum computer attacks the problem differently. In outline:

1. Superpose. Put a register of qubits into a superposition of many values of x at once.
2. Compute. Run the arithmetic a^x mod N on that superposition. The result is a quantum state in which the repeating pattern is woven into the amplitudes.
3. Transform. Apply the quantum Fourier transform, which uses interference to make amplitudes pile up on values related to the period and cancel elsewhere.
4. Measure, then tidy up classically. The measurement gives a number that reveals r with good probability, after some ordinary arithmetic. If it doesn't, run again.

A good analogy is a prism. Sunlight looks white, but a prism splits it into the colors hidden inside. The Fourier transform is a prism for rhythms: it takes a signal and reveals its frequencies. A quantum computer can apply that prism to a pattern far too long to ever write down, then measure the strongest frequency.

Note what it doesn't do. It doesn't try every factor in parallel and pick the right one. As we saw in the last lesson, that wouldn't work. It uses interference to extract one global property, the period, from a pattern it never reads out in full.

Elliptic curves fall too

Shor's 1994 paper solved two problems: factoring and discrete logarithms. The discrete logarithm problem behind Diffie-Hellman also hides a periodic structure, and the same period-finding machinery extracts it. Variants of the algorithm do the same for the elliptic-curve version.

So the damage is total for today's public-key cryptography:

Elliptic curves' small keys were a classical advantage, not a quantum shield.

Why bigger keys don't save us

Against classical attacks, the standard response to progress is "use a bigger key." The work to break RSA classically grows far faster than the work to use it, so a modest key-size increase buys an enormous security margin.

Shor's algorithm breaks that bargain. Its cost grows only polynomially with key size. Doubling an RSA key makes the quantum attacker's job harder, but only by a modest factor, the same kind of factor by which it makes your own job harder. There's no key size that is comfortable for you and hopeless for a quantum attacker. The only real fix is to switch to different math, the post-quantum algorithms that the practitioner track covers.

How far away is this?

Running Shor's algorithm against RSA-2048 needs a large, error-corrected quantum computer. The published estimates keep shrinking:

• 2019: Gidney and Ekerå estimated about 8 hours with about 20 million noisy qubits.
• May 2025: Gidney estimated under a week with fewer than one million noisy qubits.

Both are engineering estimates, not predictions of when such a machine will exist. Nobody has built one. But the direction of travel matters: better algorithms and error correction keep lowering the bar while hardware climbs toward it.

Questions

Get five of six right to mark the lesson complete. They also feed the final exam.

Sources

• Shor (1994/1995), Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Gidney & Ekerå (2019), How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
• Gidney (2025), How to factor 2048 bit RSA integers with less than a million noisy qubits
• NIST IR 8547 (initial public draft): Transition to Post-Quantum Cryptography Standards

Drawn byKyeson Blake Utley

CourseQuantum Defense

Sheet4 of 18

PartI · Foundations

Rev.18 Oct 2026

Sources4 cited

Found an error?Send a correction