Shor's algorithm
April 2, 2025
Shor’s algorithm factors integers by reducing factoring to period finding, then solves period finding with the quantum Fourier transform and classical post-processing.
Why it matters
This is a flagship example of a super-polynomial quantum speedup for a problem believed to be hard classically (factoring).
Implementing Shor at cryptographically relevant scales requires large, fault-tolerant quantum computers that do not exist yet. Treat this page as conceptual background.
Where to go next
Return to the tutorial index and reinforce the basics with exercises, or read external references on the Resources page.