Shor's Algorithm

1994. Peter Shor, AT&T Bell Labs, publishes a paper. It breaks RSA. Not in practice - in theory. But the theory is precise: given a quantum computer with sufficient qubits, every public-key certificate on the internet becomes readable. HTTPS connections from 2024 are being collected right now by intelligence agencies. The algorithm to decrypt them does not yet have the hardware to run on. The race is between quantum hardware scaling and cryptographic migration. NIST published post-quantum standards in 2024. Shor's algorithm is the reason.

• **RSA/ECC break**: Shor's algorithm factors RSA-2048 in hours (polynomial time) vs millions of years classically; it also solves discrete logarithm breaking Diffie-Hellman and all Elliptic Curve schemes used in TLS, SSH, and PGP
• **NIST PQC Standardization (2024)**: FIPS 203 (ML-KEM/Kyber), FIPS 204 (ML-DSA/Dilithium), FIPS 205 (SLH-DSA/SPHINCS+) published as official US standards; Google Chrome began deploying hybrid X25519+Kyber768 in 2023 serving 100M+ users
• **NSA CNSA 2.0 (2022)**: US National Security Agency deprecated all RSA/ECC cryptography for national security systems, mandating post-quantum algorithms by 2030-2033 - the first government mandate driven by Shor's algorithm threat

Period Finding: The Quantum Core

RSA encryption rests on one assumption: factoring large integers is computationally hard. Multiplying two 2048-bit primes takes microseconds. Factoring the result? The best classical algorithm (General Number Field Sieve) would take longer than the age of the universe on all computers combined. In 1994, Peter Shor showed this hardness assumption collapses on a quantum computer. The key insight: **factoring reduces to period finding**, and quantum computers can find periods exponentially faster than classical ones.

**Reduction: Factoring → Period Finding** Given N to factor: 1. Pick a random a < N, compute gcd(a, N). If gcd > 1, done. 2. Find the period r of the function f(x) = a^x mod N. That is, find smallest r such that a^r ≡ 1 (mod N). 3. With high probability, gcd(a^(r/2) - 1, N) and gcd(a^(r/2) + 1, N) are non-trivial factors of N. Step 2 (period finding) is classically exponential, quantumly polynomial.

The quantum speedup comes entirely from the period-finding step. The quantum computer creates a superposition of all possible values of x simultaneously, then applies the Quantum Fourier Transform (QFT) to extract the period from the interference pattern. Measuring collapses to a multiple of N/r, from which r can be recovered with continued fractions.

Quantum Fourier Transform in Shor's

The classical Discrete Fourier Transform (DFT) on N points takes O(N log N) with FFT. The **Quantum Fourier Transform** (QFT) operates on a superposition of N = 2^n basis states using only n qubits, and requires O(n^2) gates - exponentially fewer. In Shor's algorithm, the QFT converts a periodic superposition into a superposition of frequencies, revealing the period via measurement.

**QFT action on a periodic superposition:** If the input state has period r (i.e., amplitude at positions 0, r, 2r, 3r, ...), the QFT produces a superposition at frequencies N/r, 2N/r, 3N/r, ... Measuring gives a multiple of N/r. Apply continued fractions to recover r from N/r. The QFT on n qubits requires only O(n^2) Hadamard + controlled-phase gates vs O(2^n · n) for classical FFT on the same number of points.

The QFT requires O(n^2) gates but those gates must be **fault-tolerant**. Current noisy quantum computers (NISQ devices) cannot execute deep circuits reliably. Shor's algorithm on RSA-2048 is estimated to require ~4000 **logical** qubits (millions of physical qubits with error correction). The world's best quantum computers in 2024 have ~1000-2000 physical qubits with high error rates.

Full Shor's Algorithm

Putting it together: Shor's algorithm runs in **O(n^3)** time (polynomial in the number of bits n), versus the best classical algorithm's sub-exponential O(exp(n^(1/3))). For RSA-2048, this is the difference between millions of years and hours. The algorithm has two parts: a classical pre/post-processing part (choose a, compute gcd, recover factors) and a quantum subroutine (modular exponentiation + QFT for period finding).

**Shor's complexity:** O(n^2 log n log log n) quantum gates, where n = log_2(N). The dominant cost is the quantum modular exponentiation circuit, not the QFT itself. In practice, the QFT requires O(n^2) gates but modular exponentiation requires O(n^3) gates - making it the bottleneck for large N.

The RSA Threat and Post-Quantum Cryptography

Shor's algorithm breaks RSA, Diffie-Hellman, and Elliptic Curve Cryptography - the three cryptographic primitives securing most of the internet's encrypted traffic. HTTPS, VPNs, SSH keys, TLS certificates, blockchain signatures: all are vulnerable to a sufficiently large quantum computer. The threat is not hypothetical: in 2024 Google and IBM have quantum processors with 1000+ qubits. RSA-2048 requires millions of error-corrected logical qubits, but the trajectory is clear.

**Harvest now, decrypt later (HNDL)**: nation-state actors may be storing encrypted traffic now to decrypt once quantum computers scale up. Long-lived secrets (classified communications, financial records, personal medical data from 2024 that must remain private in 2040) are already at risk. This is why NIST standardized post-quantum cryptography algorithms in 2024, even before large-scale quantum computers exist.

**Symmetric cryptography is mostly safe**: AES-256 is only weakened by Grover's algorithm (quadratic speedup), reducing effective security from 256 bits to 128 bits - still considered secure. SHA-3 and AES-256 are recommended for long-term symmetric security. The quantum threat is specifically to public-key cryptography (RSA, ECC, DH) that relies on factoring or discrete log hardness.

Key ideas

• **Factoring reduces to period finding**: Shor showed that finding r in a^r ≡ 1 (mod N) gives factors of N via gcd; this reduction is classical, the speedup comes from quantum period finding
• **QFT is the quantum core**: the Quantum Fourier Transform extracts the period from a periodic superposition in O(n^2) gates vs O(2^n · n) classically, providing the exponential speedup
• **RSA/ECC are broken in principle**: Shor runs in O(n^3) polynomial time vs classical sub-exponential; it also breaks Diffie-Hellman and ECDSA; symmetric cryptography (AES-256) is mostly safe
• **Post-quantum migration is urgent now**: harvest-now-decrypt-later attacks make Shor's relevant today; NIST standardized ML-KEM, ML-DSA, and SLH-DSA in 2024; transition to hybrid classical+PQC is underway

Related topics

Shor's algorithm connects quantum computing to cryptography and complexity theory:

• Quantum Fourier Transform (QFT) — The QFT is the quantum subroutine inside Shor's algorithm; understanding QFT circuit construction is required to understand how the period is extracted
• Grover's Search Algorithm — Grover provides a quadratic speedup for unstructured search, breaking symmetric cryptography half as severely as Shor breaks asymmetric
• Cryptography and PKI — RSA, ECDH, and digital signatures are the targets of Shor's algorithm; post-quantum replacements (Kyber, Dilithium) are built on lattice hardness

Вопросы для размышления

• Shor's algorithm requires millions of error-corrected logical qubits to break RSA-2048. Given current quantum hardware progress (roughly doubling qubit count every 2-3 years), when might this become practical - and what assumptions does that estimate rely on?
• Symmetric cryptography (AES-256) is weakened by Grover's algorithm to 128-bit effective security. Is 128-bit security considered safe long-term? What would it take for AES-256 to need replacement?
• Blockchain systems like Bitcoin and Ethereum use ECDSA for transaction signatures. If Shor's algorithm becomes practical, what happens to cryptocurrency wallets? Which wallets are most at risk first?

Связанные уроки

• crypto-02-modular-arithmetic