Shor’s Algorithm Explained — Why RSA and ECC Will Break

Shor’s algorithm is the entire reason post-quantum cryptography exists as a field. Understanding the mechanism — even at a conceptual level — clarifies why specific cryptographic systems are doomed and others survive.

What Shor’s algorithm actually does

Given a composite integer N (e.g., the public modulus of an RSA key), Shor finds N’s prime factors p and q in polynomial time. The hard step in factorisation is finding the period of the function f(x) = aˣ mod N for a random a coprime to N. Classically, finding this period requires exponential time. Quantumly, Shor’s algorithm finds it in O((log N)³) using:

1. A quantum register prepared in superposition over many values of x.
2. Modular exponentiation to compute aˣ mod N for all x in superposition (entangling x with f(x)).
3. A quantum Fourier transform that extracts the period from the entangled state.
4. Classical post-processing of the period to derive p and q.

The quantum part — superposition + entanglement + Fourier — is what gives the exponential speedup. Steps 1 and 4 are bookkeeping; the magic is in steps 2 and 3.

Why factorisation breaking matters

RSA encryption: ciphertext = plaintextᵉ mod N, where N = p × q. Decrypting requires knowing p and q (to compute the private exponent d). RSA’s security rests entirely on the assumption that factoring N is hard. When Shor breaks factoring, RSA falls.

It’s not “RSA is partially weakened.” It’s “RSA is recovered key — full key, not just session key.” Anyone with a CRQC and a captured RSA public key can derive the private key in hours, possibly minutes for RSA-2048.

How Shor extends to ECC

Elliptic-Curve Cryptography (ECDSA, ECDH) doesn’t use factorisation. It uses the elliptic curve discrete logarithm problem (ECDLP): given P and Q = nP on a curve, find n.

Shor’s algorithm has a sister algorithm — also from Shor’s 1994 paper — that solves discrete logarithms in polynomial time. ECDLP is just discrete log in a different group; the algorithm extends naturally.

Ironically, ECC is BROKEN MORE EASILY by quantum computers than RSA at equivalent classical strength, because ECC keys are smaller (256 bits) than equivalent RSA keys (3072 bits) — so the quantum circuit is smaller and faster. ECC’s elegance against classical attackers is its weakness against quantum ones.

Hardware requirements — the actual gating factor

Shor’s algorithm in math is one thing. Running it on a real noisy quantum computer is another. Estimates of physical qubits needed for RSA-2048:

• Naive Shor: ~6,000 logical qubits, but each logical qubit requires ~1,000-10,000 physical qubits for error correction. Total: ~20 million physical qubits.
• Optimised Shor (Gidney-Ekerå 2021): ~1,500 logical qubits, ~20 million physical qubits, 8 hours of computation.
• Latest optimisations (2024-2025 papers): ~1,000 logical qubits possible with better factoring approaches, lowering physical qubit count to ~4 million.

Current state of the art (late 2025):

• IBM Heron: ~133-156 physical qubits, no error correction at scale.
• Google Sycamore: ~70-100 physical qubits, recent advances toward early error correction.
• IonQ Forte: ~36 trapped-ion physical qubits, higher gate fidelity.
• QuEra Aquila: ~256 neutral-atom qubits.

The gap between today and “Shor-capable” CRQC is 5-6 orders of magnitude. Closing it is the engineering challenge. Most specialists believe it closes by 2030-2040.

Mosca’s theorem — the threat-model framing

Cryptographer Michele Mosca formalised the question with three numbers:

• X = years your data needs to remain secret.
• Y = years to migrate your systems to PQ.
• Z = years until a CRQC exists.

If X + Y > Z, you have a problem — your data will be vulnerable before you’re done migrating.

For typical Indian enterprise: X = 5-25 years (depending on data type), Y = 3-7 years (typical migration program), Z = 10-15 years. The arithmetic says many enterprises are already over budget; migration must start now.

Common misunderstandings

• “RSA-4096 is safe because it’s bigger.” No. Shor scales with log N; doubling key size doubles quantum circuit time, doesn’t make it intractable. RSA-4096 buys ~hours not days.
• “We can layer two RSA encryptions for safety.” No. Multiple Shor runs against multiple keys is just multiple Shor runs — still fast in aggregate.
• “Current quantum computers can factor 21 = 3 × 7. We have decades.” Maybe. But 21 → 4096 is engineering, not math. Engineering closes faster than expected sometimes.
• “AES-256 is fine forever.” True for symmetric encryption (Grover only halves security to 128-bit, still secure). But AES-256 doesn’t help if the AES key was exchanged via RSA/ECDH that Shor breaks — the session key falls with the asymmetric crypto.

FAQ

Has anyone actually run Shor against a real RSA key?

Largest published Shor demonstration factored 21 (in 2012, with significant simplifications). No real RSA key has been broken by Shor. The capability is theoretical-but-imminent, not demonstrated.

What about variational quantum algorithms — are those a threat too?

Variational/heuristic quantum approaches (VQE, QAOA) target different problem classes. They’re not known to break factoring or DLP. Specialists track them; they’re not the leading concern.

How will I know when CRQC arrives?

NIST, NSA, GCHQ, NCSC will issue formal advisories. Major tech companies will accelerate PQ migration. There won’t be a single “moment”; capability scales gradually. Watch for the first published Shor factorisation of a 1024-bit RSA modulus — that’s the canary.

Should I move from RSA to ECC for protection?

No. Both fall to Shor. ECC is smaller and faster classically, but quantum-broken at the same time as RSA. Migrate to PQ algorithms (Kyber, Dilithium), not from one classical algorithm to another.

Is there hope of finding a faster classical factoring algorithm before quantum?

Researchers continue working. The current best classical (general number field sieve) is sub-exponential. A polynomial-time classical algorithm would also break RSA — and obviate the need for quantum migration. Most cryptographers consider this unlikely but possible.

⚖️ Module 3 of 20. Shor’s algorithm is the central threat driver. Module 4 covers Grover (the symmetric-side weakening); Module 5 introduces NIST’s PQ replacements.