Shor's Algorithm — How Quantum Computing Breaks RSA Encryption

Shor's algorithm, published by Peter Shor in 1994, was the first polynomial-time quantum algorithm for a problem believed to require exponential classical time: integer factorization. Factoring an n-bit number classically takes sub-exponential time (best: GNFS ~exp(n^(1/3))). Shor's quantum approach takes O(n³) quantum gates, threatening RSA-2048 and elliptic curve cryptography. It remains one of the most important algorithms in computer science.

1. RSA and the Factoring Problem

RSA key generation: 1. Choose two large primes p, q (each ~1024 bits for RSA-2048) 2. N = p \times q (the 2048-bit modulus, public) 3. φ(N) = (p-1)(q-1) (Euler's totient, private) 4. Choose public exponent e (usually 65537) 5. Private key: d = e⁻¹ mod φ(N) Encryption: C = Mᵉ mod N Decryption: M = Cᵈ mod N [works because Mᵉᵈ \equiv M (mod N) by Euler's theorem] Security: to find d, adversary needs φ(N), which requires factoring N = p\timesq. Classical factoring hardness: Trial division: O(\sqrtN) = O(2^1024) — completely infeasible Quadratic sieve: L_N[1/2, 1] = exp(\sqrt(ln N \cdot ln ln N)) GNFS (best known): L_N[1/3, (64/9)^(1/3)] \approx exp(N^(1/3)) For RSA-2048: estimated 10^23 operations classically (>universe age). For Shor's algorithm: O(n³) = O(2048³) \approx 10^10 quantum operations.

2. Factoring → Period Finding

Key insight: factoring N reduces to finding the ORDER (period) of an element in the multiplicative group Z*_N. Step 1: Choose random a with 1 < a < N, gcd(a, N) = 1. (If gcd(a,N) > 1, we already found a factor — done classically.) Step 2: Find the ORDER r = min positive integer such that: aʳ \equiv 1 (mod N) The sequence 1, a, a², a³, ..., a^(r-1), 1, a, a², ... is periodic with period r. Step 3: If r is even and a^(r/2) ≢ -1 (mod N): Factor using: gcd(a^(r/2) - 1, N) and gcd(a^(r/2) + 1, N) Because: a^(r/2) \equiv 1 (mod N) \to (a^(r/2) - 1)(a^(r/2) + 1) \equiv 0 (mod N) N divides the product, but N is not a factor of either term individually \to GCD will extract a non-trivial factor. Example: N=15, a=7 7¹=7, 7²=4, 7³=13, 7⁴=1 (mod 15) \to r=4 a^(r/2) = 7² = 49 \equiv 4 (mod 15) gcd(4-1, 15) = gcd(3, 15) = 3 ✓ factor found! gcd(4+1, 15) = gcd(5, 15) = 5 ✓ other factor! Classical period finding: O(\sqrtr) by baby-step giant-step = still exponential. Quantum period finding: O(n²) quantum gates — the hard part is done quantumly.

3. Quantum Fourier Transform

The Quantum Fourier Transform (QFT) is the quantum analog of the discrete Fourier transform, acting on quantum states instead of classical bit strings:

Classical DFT: X_k = Σ_{j=0}^{N-1} x_j · e^{2πijk/N} QFT on computational basis |j⟩: QFT|j⟩ = (1/√N) Σ_{k=0}^{N-1} e^{2πijk/N} |k⟩ QFT circuit (n qubits, N=2ⁿ): Uses n Hadamard gates and n(n-1)/2 controlled-phase rotation gates. Total: O(n²) quantum gates vs. O(n·2ⁿ) for classical DFT on 2ⁿ-element input. The QFT exploits quantum parallelism: |j⟩ represents a specific number j, but it's used in superposition to process all basis states simultaneously. Key property: after applying QFT to a periodic superposition of states with period r, the result has strong amplitudes at multiples of N/r. This lets us read off r from the measurement outcome.

4. The Quantum Circuit

Shor's algorithm quantum subroutine: Registers: |0⟩_A |0⟩_B (A = control, n+1 qubits; B = target, n qubits) 1. Hadamard A: |0⟩_A → (1/√N) Σ_x |x⟩_A Creates uniform superposition over all x in {0,...,N-1}. 2. Modular exponentiation oracle: |x⟩_A |0⟩_B → |x⟩_A |aˣ mod N⟩_B This unitary can be implemented in O(n³) quantum gates using repeated squaring + quantum arithmetic. 3. State after oracle: (1/√N) Σ_x |x⟩_A |aˣ mod N⟩_B The B register encodes the periodic function aˣ mod N. 4. Measure B: collapse to some value v = aˢ mod N. A register collapses to superposition of all x with aˣ ≡ v (mod N): |A⟩ = (1/√(N/r)) Σ_k |s + kr⟩ (periodic with period r, phase s) 5. Apply Quantum Fourier Transform to A. 6. Measure A: get a value c ≈ k·N/r for random k. From c and N, extract r using continued fractions. Probability of success in one run: ≥ 1/(2 ln r) ≈ 1/n Repeat O(n) times → expected O(n) repetitions to find r.

5. Classical Post-Processing

After measuring c ≈ k·(N/r) from the QFT output: Goal: extract r from the ratio c/N. Method: continued fraction expansion of c/N. The continued fraction algorithm finds the best rational approximation p/q to c/N with q < N. This gives q = r with high probability. Continued fraction algorithm: x₀ = c/N a₀ = ⌊x₀⌋ x₁ = 1/(x₀ - a₀) a₁ = ⌊x₁⌋ ... Convergents pₖ/qₖ: q₀=1, q₁=a₁, qₖ=aₖqₖ₋₁ + qₖ₋₂ When |c/N - k/r| < 1/(2N), the convergent = k/r exactly. Example: N=15, r=4, k=2, c ≈ 2×15/4 = 7.5 → c=7 or c=8 c/N = 7/15 = 0.4666... Continued fraction: [0; 2, 7] → convergent 7/15, but also [0; 2] = 1/2 1/2 → q=2, and 2|r=4 → period r=4 recovered as 2q=4. Classical post-processing: O(n log n) with fast integer arithmetic.

6. Qubit Requirements for RSA-2048

Factoring an n-bit number requires: Logical qubits: ~2n + 3 = ~4099 logical qubits for RSA-2048 Quantum gates: O(n³) = O(2048³) \approx 8.5 \times 10⁹ gates Physical qubits (accounting for error correction): Surface code: ~1000 physical qubits per logical qubit Physical qubits for RSA-2048: ~4 MILLION physical qubits! Current state (2024): Google Willow: 105 physical qubits, ~99.7% 2-qubit gate fidelity IBM Quantum Condor: 1121 physical qubits (heavy hexagonal) Fault-tolerant threshold: still years away for cryptographic scale Best classical factoring record: RSA-250 (829 bits) factored in 2020: ~2700 CPU core-years. RSA-2048 (2048 bits): estimated > 10^23 operations. Optimistic timeline for quantum factoring of RSA-2048: Conservative estimate: 2030-2040 for demonstration at small key sizes Large-scale attack: 2030s-2050+ depending on hardware progress "Harvest now, decrypt later" attacks: adversaries collect encrypted data today to decrypt once quantum computers exist \to urgency for PQC migration.

7. Post-Quantum Cryptography

NIST standardized post-quantum cryptographic algorithms in 2024 (after 6+-year evaluation):

ML-KEM (ex-CRYSTALS-Kyber): Key encapsulation using module learning with errors (MLWE) lattice problem. Resistant to both classical and quantum attacks. Key size: 1568 bytes (Level 3). Now the primary KEM standard.
ML-DSA (ex-CRYSTALS-Dilithium): Digital signatures from lattice problems. Signature size: ~2701 bytes. Primary signature standard.
SLH-DSA (ex-SPHINCS+): Hash-based signatures with no mathematical assumptions beyond collision resistance of hash functions. Conservative choice.
FN-DSA (ex-FALCON): Compact lattice-based signatures (~666 bytes) for constrained environments.

Hybrid deployment (recommended 2024–2030): Use classical TLS 1.3 + post-quantum KEM simultaneously (X25519+ML-KEM-768). The classical algorithm protects against current attacks; PQC protects against harvest-now-decrypt-later. Both Google Chrome and Cloudflare have deployed hybrid TLS by 2024.

⚛️ Explore Quantum →