Shor’s algorithm and RSA
Lesson 12 of 23 in the course “Quantum”. Free, with animations and a quiz.
A lock made of primes
When you open a site over HTTPS, sign a document or pay by card, the RSA scheme is often at work; it was invented in 1977. The idea is simple: multiplying two large primes is easy, but factoring the result back is very hard. You can work out 61 × 53 in a minute, but finding the factors of 3233 takes longer. RSA-2048 uses a 617-digit number, and classical computers couldn’t factor it within the age of the universe.
Shor’s trick: turn factoring into rhythm
In 1994 mathematician Peter Shor of Bell Labs noticed that factoring a number can be reduced to finding a rhythm. Take N = 15 and the number 7. Raise 7 to powers and take the remainder after dividing by 15: you get 1, 7, 4, 13, then 1, 7, 4, 13 again. The rhythm repeats every 4 steps. Knowing the rhythm, school arithmetic gives the factors: 3 and 5. For small numbers you can see the rhythm by eye; for numbers with hundreds of digits it’s astronomically long, and that’s where a quantum computer is needed.
How a quantum computer hears the rhythm
Step one: a superposition of all powers at once, with a repeating pattern hidden in the amplitudes. Step two: the quantum Fourier transform, or QFT. It does what a music player’s equaliser does: it splits a signal into frequencies. Thanks to interference, the right frequency is amplified and all others cancel. Measure and you get a number from which the period is computed. That’s the exponential speedup: a billion-year task becomes one of hours or days.
How many qubits it takes, and why the number keeps falling
On paper Shor broke RSA long ago, but it needs a large error-corrected computer. The estimates are falling fast. In 2019 Craig Gidney and Martin Ekerå counted about 20 million physical qubits and 8 hours. In May 2025 Gidney showed under a million qubits and under a week. In February 2026 the startup Iceberg Quantum claimed a design with under 100,000 qubits, and at the end of March a Caltech team estimated that 10,000–20,000 neutral atoms might be enough. Both estimates assume special architectures that don’t exist yet. Today’s best chips have thousands of qubits, and the quality isn’t there yet. But the gap is closing from both sides.
It’s not just RSA under threat
The same Shor algorithm also breaks elliptic curves. Bitcoin and Ethereum signatures and HTTPS key exchange rest on them. In March 2026 a Google team with co-authors including cryptographer Dan Boneh estimated that Bitcoin’s curve needs fewer than 500,000 physical qubits, and once a public key is exposed, the attack takes about 9 minutes. Symmetric ciphers like AES and hashes like SHA-256, however, don’t suffer from Shor: they only face Grover’s “square root.” More on crypto in the last level.
Why protection has to start now
If a big quantum computer is years away, why rush? Because of the “harvest now, decrypt later” tactic. An attacker can record encrypted traffic today and store it until the day they can crack it. Medical data, state secrets and private chats must stay secret for decades. That’s why in 2024 NIST approved the first post-quantum standards, and Signal, iMessage and Chrome have already switched such protection on for ordinary users.
Check yourself
- What fact makes RSA vulnerable to a quantum computer?
Correct answer: Factoring reduces to period-finding, and QFT finds periods well. Shor turns factoring into finding a rhythm, and the QFT picks out the rhythm through interference. That gives the exponential speedup. - Why protect data now if Q-Day is years away?
Correct answer: Traffic can be recorded now and decrypted later. The “harvest now, decrypt later” tactic makes the threat real today for long-lived data. - Which of these does Shor not break?
Correct answer: AES-256. AES is a symmetric cipher with no “rhythm” for Shor. Only Grover works against it, and a 256-bit key withstands that.