Source-verifiedLevel 4

Shor's Algorithm

Shor's algorithm factors large integers in polynomial time O((log N)^3), providing an exponential speedup over the best known classical algorithms and threatening RSA cryptography.

What it means

Shor's algorithm (1994) factors an integer N in polynomial time by reducing factoring to period-finding using the Quantum Fourier Transform.The algorithm: (1) chooses random a < N, (2) uses quantum period-finding to determine the period r of f(x) = a^x mod N, (3) if r is even, computes gcd(a^(r/2) +/- 1, N) to find factors.The QFT enables efficient period-finding which is exponentially hard classically.This algorithm motivates post-quantum cryptography research since it can break RSA, Diffie-Hellman, and elliptic curve cryptography with a sufficiently large quantum computer.Current quantum computers are too small and noisy to factor cryptographically relevant numbers.

Everyday analogy

Shor's algorithm is like finding the secret rhythm of a complex musical piece -- quantum mechanics can detect the hidden periodicity that classical methods cannot efficiently find.
Think of it as tuning into the resonant frequency of a locked safe: once you find the right frequency (period), the lock opens easily.

Common misconceptions

  • Shor's algorithm does NOT instantly break all encryption -- it specifically targets integer factoring and discrete logarithm problems.
  • Current quantum computers CANNOT run Shor's algorithm on cryptographically relevant numbers -- they lack sufficient qubits and error correction.

Key takeaways

  • Factors integers in polynomial time O((log N)^3) -- exponential speedup over classical.
  • Reduces factoring to quantum period-finding using the QFT.
  • Motivates the entire field of post-quantum cryptography.

Check your understanding

What mathematical problem does Shor's algorithm reduce integer factoring to?

  1. A.Matrix multiplication
  2. B.Period finding
  3. C.Graph coloring
  4. D.Sorting
Show the answer

Answer: B. Period finding

Why: Shor's algorithm reduces integer factoring to period-finding, which can be solved efficiently using the Quantum Fourier Transform.

Builds on

QubitSuperpositionQuantum Fourier TransformQuantum MeasurementQuantum Entanglement

Primary source: Shor, SIAM J. Comput. 26, 1484 (1997), doi:10.1137/S0097539795293172

Hardware-status sentences ('current quantum computers cannot factor...') are explicitly era-qualified honesty statements protecting against hype; algorithm itself is established mathematics.

Learn it hands-on

This concept is part of a 46-level curriculum with an interactive simulator and Lumen, a tutor whose answers are verified before you see them. Levels 1–5 are free.

Start freeSee the curriculum