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.
6 min read
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.
In 1994, mathematician Peter Shor described a quantum algorithm that factors large integers and computes discrete logarithms in polynomial time — efficiently, rather than the exponential time the best known classical algorithms need. Those two problems — integer factorization and the discrete logarithm problem — are exactly what RSA, finite-field Diffie-Hellman, and elliptic-curve cryptography (ECC) rest their security on.
| 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.
Marking a lesson complete only updates this browser.