Shor’s algorithm doesn’t break encryption yet—but it proved RSA was never quantum-safe.
Shor’s algorithm is a quantum algorithm for integer factorisation, developed by Peter Shor in 1994. It runs in polynomial time in log N and places factorisation in BQP. It is asymptotically faster than the general number field sieve.
That integer factorisation lies in BQP—the class of problems efficiently solvable by a quantum computer.
How it was done
Shor’s algorithm reduces integer factorisation to order-finding using classical computation, then solves order-finding on a quantum computer via quantum phase estimation and continued fractions.
What holds up
The asymptotic speedup holds: it runs in polynomial time in log N, while the general number field sieve runs in sub-exponential time.
What does not
It does not run on any existing quantum computer. It assumes fault-tolerant, scalable quantum hardware with low error rates—none of which existed in 1994 or exists today.
Why it matters beyond the lab
It established a concrete cryptographic vulnerability: widely used public-key encryption (e.g., RSA) would collapse if large-scale quantum computers were built.
Is it worth your time
Yes—if you need to understand why quantum computing threatens RSA cryptography, or why factoring is not provably hard for quantum machines.