Shor's Algorithm — Quantum Factoring

Peter Shor published his factoring algorithm in 1994, six years before the first few-qubit quantum computers were built. Its impact was immediate and lasting: it demonstrated that quantum computers, when sufficiently powerful, would break the cryptographic foundation of the internet.

Shor's algorithm reduces integer factorisation to period finding in a modular arithmetic sequence — a problem that the Quantum Fourier Transform (QFT) solves exponentially faster than any classical algorithm. The QFT is the quantum version of the Fast Fourier Transform, computing all N frequency components simultaneously via quantum interference.

The Reduction: Factoring → Period Finding

To factor N: 1. Choose random a coprime to N 2. Find the period r of f(x) = a^x mod N — the smallest r such that a^r ≡ 1 (mod N) 3. If r is even: p = gcd(a^(r/2)-1, N) and q = gcd(a^(r/2)+1, N) are factors 4. If r is odd or gcd gives 1 or N: try different a

Classical period finding requires O(exp(n^(1/3))) steps. Quantum period finding (QFT-based) requires O(n²) steps — exponential speedup.

from math import gcd
from random import randrange

def classical_period_finding(a, N):
    """Classical (slow) period finding — O(sqrt(N)) in practice."""
    x = 1
    for r in range(1, N):
        x = (x * a) % N
        if x == 1:
            return r
    return None

def shor_classical_sim(N):
    """Shor's algorithm with classical period finding (slow part)."""
    if N % 2 == 0: return 2, N//2
    for _ in range(20):  # try multiple random a values
        a = randrange(2, N)
        g = gcd(a, N)
        if g > 1: return g, N//g  # lucky — found factor directly
        r = classical_period_finding(a, N)
        if r is None or r % 2 != 0: continue
        p = gcd(a**(r//2) - 1, N)
        q = gcd(a**(r//2) + 1, N)
        if 1 < p < N: return p, N//p
        if 1 < q < N: return q, N//q
    return None

# Factor small numbers
for N in [15, 21, 35, 77, 143]:
    result = shor_classical_sim(N)
    print(f'{N} = {result}')

The Quantum Part — QFT Period Finding

The quantum speedup comes from the Quantum Fourier Transform (QFT). Classically, finding the period r in a^x mod N requires O(r) steps — potentially O(N). The QFT finds r using O(n²) quantum gates by: 1. Creating superposition over all x values simultaneously 2. Applying the modular exponentiation function to all x at once 3. Applying QFT to extract the period r from the frequency domain

The QFT step runs in O(n²) quantum gates vs O(n × 2^n) for classical FFT on the same input — exponential speedup.

Cryptographic Impact and Timeline

| Algorithm | Problem | Quantum Attack | Status | |---|---|---|---| | RSA-2048 | Factor n=p×q | Shor: O(n³) | Broken by CRQC | | ECC P-256 | ECDLP | Shor variant | Broken by CRQC | | AES-128 | Symmetric | Grover: 2^64 | Weakened | | AES-256 | Symmetric | Grover: 2^128 | Still secure | | CRYSTALS-Kyber | Lattice (ML-KEM) | None known | PQ-secure |

CRQC = Cryptographically Relevant Quantum Computer. Required: ~4000 logical qubits (millions of physical). Current hardware: ~1000 noisy physical qubits. Timeline estimates: 2030-2040 for CRQC.

Frequently Asked Questions