Shor's Algorithm in Plain English: How Quantum Breaks RSA and Why Post Quantum Cryptography Replaces It
Category: Education
Shor's Algorithm in Plain English: How Quantum Breaks RSA and Why Post Quantum Cryptography Replaces It
11 min read
The One Paragraph Version
Shor's algorithm is a quantum program, written in 1994 by mathematician Peter W. Shor, that can factor large numbers and solve discrete logarithms exponentially faster than any known classical algorithm. RSA, Diffie-Hellman, and Elliptic Curve Cryptography (ECC, including ECDSA and Ed25519) all rely on the assumption that these math problems are intractable for a normal computer. Shor's algorithm shows that a sufficiently large quantum computer would solve them in hours, not the billions of years current encryption assumes. That is why the world needs Post Quantum Cryptography (PQC), and why NIST finalized FIPS 203 (ML-KEM), FIPS 204 (ML-DSA), and FIPS 205 (SLH-DSA) on August 13, 2024.
Why RSA Works Today (And Why It Will Not Tomorrow)
RSA encrypts data by picking two large prime numbers, multiplying them to get a big composite number N, and using N as part of a public key. If an attacker can factor N back into those two primes, they can read every message encrypted with the key. The best classical algorithm we know, the General Number Field Sieve, takes sub-exponential time. On a laptop, factoring a 2048-bit RSA key would take longer than the age of the universe.
Shor's algorithm changes the equation. It reduces factoring to a problem called period finding, which a quantum computer can solve efficiently using the quantum Fourier transform. The polynomial time cost (roughly cubic in the number of bits) means doubling the RSA key size does not double the attack time, it merely adds a modest amount. There is no RSA key size that survives Shor.
Discrete Logarithms: The Same Story for Diffie-Hellman and ECC
Diffie-Hellman key exchange and the entire Elliptic Curve Cryptography family (ECDH, ECDSA, Ed25519, X25519) rely on a problem called the discrete logarithm problem. Given the result of modular exponentiation, find the exponent. On classical machines, this is hard. Shor's algorithm cracks it in the same polynomial time as factoring.
This is why the cryptographic community cannot "just pick a bigger curve" to survive quantum. The math that makes elliptic curves efficient is the same math that makes them vulnerable.
The Actual Mechanics, Without the Math
Skipping the linear algebra, Shor's algorithm works in three phases:
- Reduce the problem to period finding. Factoring N is equivalent to finding the period of a particular function f(x) that involves modular exponentiation of a random base.
- Run the period finder on a quantum computer. Prepare a superposition over many inputs, apply f(x) in parallel across the entire superposition, then apply the quantum Fourier transform to extract the period.
- Classical post-processing. A small amount of classical math converts the period into the factors of N.
The heavy lifting, the part that would crush any classical computer, happens in step 2. This is where quantum's exponential speedup lives.
How Big a Quantum Computer Do You Need?
This is the critical question for post-quantum timing. Estimates for breaking RSA-2048 with Shor range widely. A well-cited 2021 analysis by Craig Gidney and Martin Ekera (arXiv:1905.09749) estimates around 20 million noisy physical qubits for a day-scale attack, with specific assumptions about error-corrected code distance.
For comparison, the largest quantum processors publicly announced as of April 2026 are:
| System | Qubits | Type | Cryptographically relevant? |
|---|---|---|---|
| IBM Condor (Dec 2023) | 1,121 | Superconducting | No |
| Google Willow (Dec 2024) | 105 | Superconducting | No |
| Zuchongzhi 3.0 (Mar 2025) | 105 | Superconducting | No |
| Atom Computing (Oct 2023) | 1,180 | Neutral atom | No |
None of these can run Shor on a real RSA key. The Global Risk Institute 2025 expert survey puts the likelihood of a cryptographically relevant quantum computer within 10 years between 28 percent (pessimistic) and 49 percent (optimistic), the highest 10-year estimate in the survey's seven-year history.
What PQC Does Instead
Post Quantum Cryptography uses mathematical problems that neither classical nor quantum computers are known to solve efficiently. The standardized families are:
- Lattice-based (ML-KEM, ML-DSA, FN-DSA). Relies on the Learning With Errors and related problems on high-dimensional lattices.
- Hash-based (SLH-DSA, LMS). Relies only on the security of the underlying hash function.
- Code-based (HQC, Classic McEliece). Relies on the hardness of decoding random linear codes.
Each family uses a different hard problem, giving defense in depth against a future mathematical breakthrough in any one family.
What You Should Do About It
If you are running a system that needs to protect data for more than a few years, the answer is hybrid PQC. Combine a classical algorithm like X25519 with a post-quantum algorithm like ML-KEM. An attacker must break both, not either, to read your data. Signal deployed this approach in September 2023 with PQXDH. Google Chrome shipped it by default in Chrome 131 in November 2024. Cloudflare reports over 60 percent of human-initiated TLS traffic now uses hybrid ML-KEM.
Frequently Asked Questions
Frequently Asked Questions
When did Peter Shor publish Shor's algorithm?
Peter W. Shor's algorithm was presented at the 35th Annual Symposium on Foundations of Computer Science (FOCS) in November 1994, with an expanded journal version appearing in SIAM Journal on Computing 26(5) in 1997.
Does Shor's algorithm break symmetric encryption like AES?
No. Shor's algorithm attacks public-key cryptography that relies on integer factorization or discrete logarithms. Symmetric ciphers like AES are affected by Grover's algorithm, which provides only a quadratic speedup, effectively halving the key strength. AES-256 remains secure even in a post-quantum world.
How many qubits are needed to run Shor on RSA-2048?
Estimates vary widely. Craig Gidney and Martin Ekera's 2021 analysis (arXiv:1905.09749) estimates approximately 20 million noisy physical qubits for a day-scale attack. The exact number depends on error correction assumptions and implementation choices. As of April 2026 no quantum computer approaches this scale.
Is hybrid PQC slower than classical encryption?
The overhead is small. ML-KEM-768 hybrid with X25519 adds roughly 1 to 2 kilobytes per TLS handshake and a handful of milliseconds of CPU time. For most applications this is unmeasurable.
Sources
- Shor, P. W. (1994). Algorithms for quantum computation. FOCS proceedings
- Shor arXiv preprint (1995)
- Gidney & Ekera (2021). How to factor 2048-bit RSA in 8 hours
- NIST FIPS 203 (ML-KEM) Final
- Global Risk Institute Quantum Threat Timeline 2025
Related Articles
- Grover's Algorithm Explained
- ML-KEM Explained (FIPS 203)
- Why RSA-2048 Will Break
- Why Hybrid Encryption Matters
- What is Post-Quantum Cryptography?
Protect Your Data Before Q-Day Arrives
QNSQY's NIST-standardized post-quantum encryption protects files against both current and quantum-era threats.
Originally published at quantumsequrity.com.
Top comments (0)