Shor's Algorithm

Breaking RSA - period finding and integer factorization on a quantum computer

Breaking Cryptography with Quantum Computers

Shor's algorithm (1994) showed that a quantum computer could factor large integers in polynomial time — an exponential speedup over the best known classical algorithms. Since RSA encryption relies on the difficulty of factoring, Shor's algorithm threatens the security of nearly all current public-key cryptography.

The key insight: factoring reduces to period finding, which reduces to the Quantum Fourier Transform — a problem quantum computers solve efficiently. This connection between number theory and quantum physics is one of the most beautiful results in computer science.

Period Finding: The Heart of Shor's Algorithm

Given N to factor, pick a random a and compute f(x) = ax mod N. This function is periodic — it repeats with some period r. Finding r is hard classically but easy for a quantum computer using QFT. Once you know r, simple arithmetic gives the factors. Try different values of a and N to see the periodic patterns.

N:a:

Factoring Step by Step

Walk through Shor's algorithm from start to finish. Choose N, pick a random base a, use quantum period-finding to get r, then compute gcd(ar/2±1, N) to extract the factors. Not every choice of a works — if r is odd or gives trivial factors, you try again. On average, only a few attempts are needed.

N:a:
Step 1 / 6

Why does this work? If ar ≡ 1 (mod N) and r is even, then (ar/2 − 1)(ar/2 + 1) ≡ 0 (mod N). Since neither factor is 0 mod N (usually), gcd with N gives a non-trivial factor.

Breaking RSA Encryption

RSA security rests on the assumption that factoring N = p × q is hard when p and q are large primes. The public key (e, N) is published; the private key d requires knowing φ(N) = (p−1)(q−1), which requires the factors. This demo shows how Shor's algorithm recovers the factors and breaks the encryption.

p:q:msg:

Classical vs Quantum Factoring Scaling

The best classical factoring algorithm (General Number Field Sieve) scales as exp(n1/3) — sub-exponential but still impossibly slow for large keys. Shor's algorithm scales as n³ — polynomial. For RSA-2048 (the current standard), classical factoring would take longer than the age of the universe. Shor's would take minutes on a sufficiently large quantum computer.

Classical GNFS (General Number Field Sieve) has sub-exponential complexity ~exp(n1/3). Shor's algorithm has polynomial complexity O(n³). The gap grows dramatically with key size. Hover over table rows for details.

Key Takeaways

  • Factoring → Period finding — Shor reduced integer factoring to finding the period of modular exponentiation
  • QFT detects periods — The Quantum Fourier Transform efficiently finds periodicities in quantum states
  • Exponential speedup — Classical: sub-exponential exp(n1/3). Quantum: polynomial O(n³). The gap is enormous for real key sizes.
  • RSA is vulnerable — A sufficiently large quantum computer would break RSA, ECC, and other factoring/discrete-log-based cryptography
  • Post-quantum crypto — NIST has standardized lattice-based and hash-based schemes that resist quantum attacks. The transition is underway.