Quantum Algorithms Database
Shor's Algorithm
Factors large numbers exponentially faster than any known classical algorithm, threatening RSA encryption.
Year
1994
Inventor(s)
Peter Shor
Speedup Type
Exponential Speedup
Difficulty
★★★★☆
The Problem
Finding the prime factors of a large composite number — believed to be intractable for classical computers at scale.
How It Works
Transforms factoring into a period-finding problem, solved efficiently using the Quantum Fourier Transform, then recovers factors via classical post-processing.
Real-World Impact
Directly motivates post-quantum cryptography; would break RSA and similar encryption if run on a large enough fault-tolerant quantum computer.