Shor’s Algorithm

The quantum algorithm that factors integers exponentially faster than any known classical algorithm, threatening RSA encryption.

Shor’s algorithm, discovered by Peter Shor in 1994, efficiently factors large integers. This is devastating for RSA and similar cryptosystems that rely on factoring being hard.

The Impact

Classical factoring of an $n$-bit number: $O(e^{n^{1/3}})$ (best known) Quantum factoring with Shor’s: $O(n^3)$ or better

For a 2048-bit RSA key:

• Classical: Millions of years
• Quantum: Hours to days (with a large fault-tolerant quantum computer)

How It Works

Shor’s algorithm has two main parts:

1. Classical Reduction

Factoring is reduced to period finding:

• Pick random $a<N$ (the number to factor)
• Find the period $r$ of $f(x)=a^x\mathrm{mod}N$
• Use $r$ to find factors via $\gcd (a^{r/2}\pm 1,N)$

2. Quantum Period Finding

This is the quantum part:

1. Create superposition over all $x$: ${\sum }_x|x⟩|0⟩$
2. Compute $f(x)$ quantumly: ${\sum }_x|x⟩|a^x\mathrm{mod}N⟩$
3. Apply Quantum Fourier Transform to first register
4. Measure to get information about the period $r$

The QFT causes interference that reveals the period with high probability.

Circuit Overview

|0⟩^n ──H^⊗n──┬─── QFT ── Measure ──→ period info
              │
|0⟩^m ────────⊕── (modular exponentiation)

Resource Requirements

To factor an $n$-bit number:

• Qubits: $O(n)$ (roughly $2n-3n$ qubits)
• Gates: $O(n^3)$ (dominated by modular exponentiation)
• T-gates: Many millions for cryptographically relevant sizes

Current Status

We’re far from breaking real-world RSA. But it’s a matter of engineering, not fundamental obstacles.

Implications

1. Cryptographic transition: Moving to post-quantum cryptography
2. Security timeline: Data encrypted today could be decrypted later (“harvest now, decrypt later”)
3. Motivation for quantum computing: Major driver of quantum research and funding

Variants

• Simplified Shor’s: For specific numbers with known structure
• Quantum resource estimation: Ongoing research to reduce requirements
• Hybrid approaches: Some classical preprocessing

Historical Note

Shor’s algorithm was the “killer app” that launched serious interest in quantum computing. It showed quantum computers could solve a problem of real-world importance exponentially faster.

See also: Quantum Fourier Transform, Quantum Phase Estimation, Post-Quantum Cryptography, Quantum Advantage