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

anjanj
1 min read

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 TypeExample AlgorithmsBroken By (Quantum)
Integer factorizationRSAShor’s Algorithm
Discrete log problemDiffie-Hellman, DSAShor’s Algorithm
Elliptic curve cryptography (ECC)ECDSA, ECDHShor’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.

0
Subscribe to my newsletter

Read articles from anj directly inside your inbox. Subscribe to the newsletter, and don't miss out.

Written by

anj
anj