#NoStupidQuestion: What are the algorithms that are considered uncrackable by traditional (classical) computer but can be broken by quantum computer?

The most famous type of code systems that regular computers can’t break, but quantum computers can, are ones that protect data using math problems like breaking big numbers into smaller ones or figuring out hidden patterns in numbers.
Breakable by Quantum:
Algorithm Type | Example Algorithms | Broken By (Quantum) |
Integer factorization | RSA | Shor’s Algorithm |
Discrete log problem | Diffie-Hellman, DSA | Shor’s Algorithm |
Elliptic curve cryptography (ECC) | ECDSA, ECDH | Shor’s Algorithm |
⚠️ Why Classical Computers Can’t Break Them:
Classical computers cannot factor large integers or solve discrete logarithms efficiently. The best classical algorithms (like the Number Field Sieve for factoring) are sub-exponential, not polynomial time.
Why Quantum Computers Can:
Shor’s Algorithm runs in polynomial time on a quantum computer for:
Factoring large integers (used in RSA)
Computing discrete logarithms (used in DH, DSA, ECC)
This makes quantum computers exponentially faster for these tasks.
Summary:
Uncrackable by classical, breakable by quantum:
RSA
Diffie-Hellman
ECC (Elliptic Curve Cryptography)
🔐 Shor’s Algorithm is the quantum algorithm that breaks them.
Subscribe to my newsletter
Read articles from anj directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by