Shor's Algorithm Explained: How It Breaks RSA and ECC

What is Shor's algorithm?

Peter Shor published it in 1994 while he was at Bell Labs, and it changed the funding landscape for quantum computing more or less overnight. Before Shor, a quantum computer was a fascinating physics project. After Shor, it was a machine that could read everyone's mail. Governments started writing cheques.

The result itself is narrow. Shor gave us a quantum algorithm that finds the prime factors of an integer, plus a close cousin that solves the discrete logarithm problem, and both run in time that grows polynomially with the number of bits. Our best classical method, the general number field sieve, grows sub-exponentially.

That gap is not a matter of degree. Classically, going from RSA-1024 to RSA-2048 turns a hard problem into an impossible one. Under Shor's algorithm it roughly doubles the runtime of an attack that already works.

And here is the uncomfortable part. Every piece of public-key cryptography running on the web right now sits on one of the two problems Shor solved: the RSA key in your certificate, the ECDSA signature on it, the ECDH handshake that negotiates your session key. All of it. That is the entire reason post-quantum cryptography is a field.

How Shor's algorithm works

Most write-ups drown you in linear algebra. You don't need that to reason about the threat. You need the shape of the thing, so here it is in three steps.

Step one is entirely classical. Shor's real insight was that factoring an integer N is secretly a question about repetition. Pick a random a that shares no factor with N, then write out a¹ mod N, a² mod N, a³ mod N and keep going. The sequence always cycles eventually. Call that cycle length r, the order of a. If r turns out to be even, then a^(r/2) − 1 and a^(r/2) + 1 each share a factor with N, and a greatest common divisor (cheap, classical, instant) hands you p and q.

So all that cryptographic difficulty collapses into one sub-problem: find the period r. Classically that's no easier than factoring was, because for a 2048-bit modulus the cycle is astronomically long and you'd have to walk it.

Step two is where the quantum computer earns its keep. A quantum register can hold a superposition of every exponent at once. Compute a^x mod N across that superposition and the state now encodes the whole periodic sequence. On its own that's useless, since measuring just spits out one random value. The trick is the quantum Fourier transform. Think of it as an interference machine: amplitudes that disagree with the period cancel each other out, amplitudes that agree reinforce. Measure at the end and you almost always get something tied to r.

Step three is classical again. What you measured is a fraction approximating something over r, and continued fractions pull r back out. Multiply to check your work. If the run fails, because r came out odd or you drew a bad a, you just run it again. A few attempts and you're through with high probability.

A worked example: factoring 15

Fifteen is the textbook case. Small enough to do in your head, and it happens to be the number most physical implementations have actually managed to run.

• Take N = 15 and pick a = 7. They share no common factor, so we continue.
• Compute the powers: 7¹ = 7, 7² = 49 = 4 (mod 15), 7³ = 28 = 13 (mod 15), 7⁴ = 91 = 1 (mod 15). The sequence hit 1, so the period is r = 4.
• r is even, so compute a^(r/2) = 7² = 49. Then gcd(49 − 1, 15) = gcd(48, 15) = 3 and gcd(49 + 1, 15) = gcd(50, 15) = 5.
• 15 = 3 × 5. Factored, without ever searching for a factor.

Notice that only step two needed a quantum computer, and only because for a real modulus the period is unreachably large. The rest is arithmetic you could do on paper. Keep that in mind next time you read that a lab "ran Shor's algorithm": the classical scaffolding is trivial and always was. What they're testing is whether the order-finding circuit survives the noise.

Why Shor's algorithm breaks RSA

An RSA public key is a modulus n and a public exponent e. That modulus is two big secret primes multiplied together, p and q, and the private exponent d comes out of the same two primes. Both halves of the keypair trace back to them. The whole security assumption is that nobody can run the derivation backwards from n.

Shor's algorithm runs it backwards. Factor n, recover p and q, compute d with the extended Euclidean algorithm, done. You hold the private key. No brute forcing, no side channel, no need to go anywhere near the server. The public key is enough, and that key is published in every certificate, every handshake, and every CT log.

Which is why "just use a bigger key" isn't a plan. Classical factoring effort explodes as the key grows; quantum factoring effort grows roughly with the cube of the bit length. Doubling 2048 to 4096 multiplies the attacker's qubit and runtime budget by a single-digit factor. You've moved the date, not the outcome. If you're weighing key sizes and curves for today's traffic, our ECC vs RSA certificates guide covers the practical side.

Does it break ECC and ECDSA too?

Yes, and this one catches people out, because ECC gets sold as the stronger, more modern option. Classically it is. A 256-bit curve gives you roughly the strength of a 3072-bit RSA key at a fraction of the size.

Against Shor's algorithm the advantage flips. The discrete logarithm variant applies straight to elliptic curve groups, and because the group is small (256 bits, not 2048) the circuit needs fewer logical qubits than factoring an RSA modulus of similar classical strength. Published resource estimates put a 256-bit curve at roughly a third of the logical qubits RSA-2048 demands. So in a quantum future, ECDSA and ECDH go first, not last.

That sweeps up a lot: TLS certificate signatures on P-256 and P-384, the key exchange in every modern handshake, your SSH keys, and the signatures holding up most cryptocurrencies. One algorithm, and it takes the whole deployed public-key stack with it.

What quantum computing does not break

Symmetric cryptography is in much better shape, and the distinction matters a lot when you're deciding what to migrate first. Shor's algorithm feeds on mathematical structure: periodicity in modular arithmetic, group structure in elliptic curves. AES and SHA-2 were built without that kind of structure to grab onto. The best known quantum attack on them is Grover's algorithm, which searches an unsorted space in the square root of the classical time.

A square-root speedup halves the effective security level in bits. So AES-128 drops to about 64 bits of quantum work in the friendliest theoretical model, and even that model ignores how badly Grover parallelises, which makes the real number considerably worse for the attacker. AES-256 drops to 128 bits, still nowhere near reachable with any physics we know. SHA-256 collision resistance sits in similarly comfortable territory.

Read that table as: your session encryption is fine, your key exchange and signatures are not. That's the reason hybrid key exchange rolled out first. It patches the confidentiality hole immediately, while the signature and PKI migration grinds on for years.

How many qubits does Shor's algorithm need?

This is where the headlines and the reality part ways, and it comes down to one distinction: logical versus physical qubits.

A logical qubit is a perfect, noise-free qubit, which is what the algorithm assumes it has. Shor needs a few thousand of them for RSA-2048, roughly 2n to 3n for an n-bit modulus, so call it 4,000 to 6,000. If anyone had 6,000 perfect qubits, RSA would already be finished.

Nobody does. Real qubits decohere in microseconds and gates fail roughly once in a thousand operations, while the algorithm needs billions of operations in sequence without one uncorrected error slipping through. Closing that gap means quantum error correction, and error correction builds each logical qubit out of a whole lattice of physical ones. At today's error rates that's thousands of physical qubits per logical qubit.

Multiply it out and you land on the number worth memorising: Gidney and Ekerå's 2021 estimate of roughly 20 million noisy physical qubits running for about 8 hours to factor a 2048-bit RSA integer. Later work has chipped away at it, and it will keep falling as error correction gets better. But the largest machines today are in the hundreds to low thousands of physical qubits. That's several orders of magnitude, not a rounding error.

Running Shor's algorithm on real hardware

You can go and run it this afternoon. IBM Quantum publishes a Qiskit tutorial that builds the order-finding circuit, runs it on a simulator or a real backend, and does the continued-fractions post-processing for you. It's the fastest way to turn the algorithm from abstract into concrete. It also makes the resource problem impossible to ignore, because you can watch the circuit depth balloon as you nudge the modulus upward.

Just be honest with yourself about what the demonstrations prove. Published physical runs have factored 15, 21 and 35, and quite a few of them used compiled circuits that were simplified using advance knowledge of the answer. Those experiments validate the physics of the components. They are not an unaided factoring capability. No credible public result has factored a cryptographically relevant integer, and the claims that pop up every few months usually turn out to be quantum annealing on a specially constructed number, which doesn't scale.

If you happen to administer systems on a quantum platform, we cover the TLS configuration side separately in our IBM Quantum Platform SSL/TLS guide.

What this means for your certificates

Work out what's actually exposed. Your certificate isn't the asset at risk. It expires in a few months regardless. The real problem is harvest now, decrypt later: somebody records your encrypted traffic today and opens it whenever a capable machine turns up. Ask yourself whether the data you're transmitting still matters in ten or fifteen years. Health records, legal files, state secrets, long-lived credentials — that traffic is arguably exposed already, whatever the hardware does. If what you send is worthless by next Tuesday, this is mostly an interesting read and not a project.

Turn on hybrid key exchange wherever your stack supports it. Modern browsers and TLS libraries already negotiate X25519 paired with ML-KEM, and that closes the harvest-now-decrypt-later hole without anyone waiting on the PKI. It's a server config change, not a certificate change, which makes it the cheapest win available. Our post-quantum cryptography guide walks the migration end to end.

Get good at rotating keys. Crypto-agility sounds like a buzzword until you have to swap an algorithm under time pressure, at which point it's the difference between a bad week and a bad year. You're being pushed there anyway: maximum certificate validity is falling to 199 days, manual renewal is finished as a practice, and the automation you build for that is the same automation that swaps your key algorithm later. While you're at it, keep an inventory of where RSA and ECC keys actually live: servers, load balancers, internal CAs, code signing, embedded gear. The boxes everyone forgets are the ones still running P-256 in 2040.

Timeline: when does this actually matter?

Nobody credible will give you a date, and you should be wary of anyone who does. What we have instead are policy anchors, and honestly those are more useful for planning than any forecast would be.

• 1994 — Shor publishes the algorithm; the expanded paper follows in SIAM in 1997.
• 2016–2022 — NIST runs its post-quantum standardisation competition, narrowing hundreds of submissions to a handful of lattice- and hash-based winners.
• 2024 — NIST finalises FIPS 203 (ML-KEM), FIPS 204 (ML-DSA), and FIPS 205 (SLH-DSA). Hybrid post-quantum key exchange starts shipping in mainstream browsers and servers.
• 2030 — NIST's draft transition guidance (IR 8547) deprecates 112-bit classical public-key security, which covers RSA-2048 and P-256.
• 2035 — the same guidance disallows those algorithms outright, and US federal policy targets completing the migration. Treat this as the deadline that governs procurement and compliance, whatever the hardware ends up doing.

So where does that leave you? A cryptographically relevant quantum computer isn't imminent, the estimates move in both directions every year, and the migration will take longer than the threat needs to arrive if everyone sits and waits for certainty. Plan against the 2030 and 2035 policy dates instead of against a prediction. You'll be neither panicked nor caught out, which is roughly the best posture available here.

Methodology and review

The algorithm description follows Shor's 1997 SIAM paper and IBM Quantum's Qiskit tutorial implementation. Resource figures are quoted from peer-reviewed estimates rather than vendor material: the 20-million-physical-qubit, 8-hour figure for RSA-2048 comes from Gidney and Ekerå (Quantum 5, 433, 2021), and logical-qubit counts follow the standard 2n–3n scaling for an n-bit modulus. Where estimates are contested or have improved since publication, we say so rather than quoting a single number as settled. Migration dates come from NIST IR 8547 and the FIPS 203/204/205 announcements, not from press coverage.

Written by Daniel Rehak, TLS and PKI engineer at My-SSL.com, who has spent the last decade working on certificate lifecycle and key management for production TLS estates. Technically reviewed by the My-SSL Security Team on 31 July 2026. We re-check this article whenever NIST updates its transition guidance or a significant new resource estimate is published.

Frequently asked questions