What quantum computing changes
Shor's algorithm and what it breaks
The algorithm that gives public-key cryptography an expiration date, and the one qualifier that belongs next to every mention of it.
7 min read · 7 min 49 sec film
What you'll be able to do
- State what Shor's algorithm computes, and name the cryptographic problems that computation solves.
- List the specific algorithms — RSA, finite-field Diffie-Hellman, ECC — that Shor's algorithm breaks.
- Explain why "a large, fault-tolerant quantum computer" is a load-bearing qualifier, not a footnote.
Lesson film
Watch: Shor's algorithm and what it breaks
Factoring reduces to one question about repetition — and that single question is the only part a quantum computer answers differently.
7 min 49 sec · 10 scenes
7 min 49 sec, narrated by your browser's voice. Captions and a full transcript are below — nothing here needs sound.
In 1994, Peter Shor described a quantum algorithm that does two things efficiently that classical computers cannot.
With the player focused: Space plays or pauses, ← → seek ten seconds, Home restarts, M toggles narration.
Full transcript
1. One algorithm, 1994
2. Factoring becomes repetition
3. The one quantum line
4. Why size stops helping
5. What is on the list
6. One problem, three costumes
7. The load-bearing qualifier
8. What is not evidence
9. Why it is not theoretical
10. Takeaway
The written lesson
In 1994, mathematician Peter Shor described quantum algorithms that factor large integers and compute discrete logarithms in polynomial time. The best known general classical methods become impractical at deployed key sizes, but they should not all be described as exponential-time algorithms. Integer factorization and discrete logarithms underlie RSA, finite-field Diffie-Hellman, and elliptic-curve cryptography (ECC).
| Algorithm | What it protects | Why Shor's algorithm breaks it |
|---|---|---|
| RSA | Key exchange, digital signatures, certificates | Security rests on the difficulty of factoring the product of two large primes |
| Finite-field Diffie-Hellman (DH) | Key exchange | Security rests on the difficulty of the discrete logarithm problem |
| Elliptic-curve cryptography (ECC): ECDH, ECDSA, EdDSA | Key exchange and signatures, most modern TLS | Security rests on the elliptic-curve discrete logarithm problem, a variant of the same problem |
None of that makes the risk theoretical. Data captured today can stay confidential long enough to still matter whenever such a machine arrives — the subject of HNDL Fundamentals — which is why standards bodies published replacements well before any date for that machine is known.
What matters for this course is narrower and more certain: which algorithms Shor's algorithm breaks, not when. That list — RSA, DH, ECC — is exactly the public-key cryptography identified as exposed in the previous lesson.
Symmetric cryptography and hash functions do not appear on this list. They rest on different mathematical assumptions, the subject of the next lesson.
The useful complexity comparison is that Shor gives polynomial-time quantum algorithms for factoring and discrete logarithms, whereas the best known general classical methods for these problems are far less efficient at deployed sizes. It is inaccurate to describe every best classical method here as exponential. Neither mathematical result supplies a date for a machine able to attack deployed keys.
Primary reading and claim sources
Publication status checked on the date shown. Draft guidance can change.
- Polynomial-Time Algorithms for Prime Factorization and Discrete LogarithmsPeter Shor · Research paper · checked 2026-09-26
- Post-Quantum Cryptography FAQsNIST · Current project guidance · checked 2026-09-26
Marking a lesson complete only updates this browser.