Shor's Algorithm: Breaking RSA Encryption Guide
The Problem Shor’s Algorithm Solves
Integer factorization is the problem of decomposing a composite integer N into its prime factors p and q where N = p × q. The presumed hardness of factorization underpins RSA, the most widely deployed public-key cryptosystem on the internet. The best classical algorithm, the general number field sieve (GNFS), has sub-exponential complexity L_N[1/3, c] ≈ exp(c (log N)^{1/3} (log log N)^{2/3}). For RSA-2048 (617 decimal digits), this runtime is measured in billions of years with current technology. Shor’s algorithm, discovered by Peter Shor in 1994, factors integers in polynomial time O((log N)³), fundamentally changing the security landscape of modern cryptography (Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM Journal on Computing, 1997). The discovery of this algorithm was the primary catalyst for the entire field of post-quantum cryptography and remains the most famous example of exponential quantum speedup.
Why Factorization Matters
RSA encryption depends on the computational asymmetry between multiplying two large primes (easy) and factoring their product (hard). If factoring becomes tractable, RSA is broken. This threat extends beyond RSA: the Diffie-Hellman key exchange and Elliptic Curve Cryptography (ECDSA) are also vulnerable because Shor’s algorithm generalizes to compute discrete logarithms. Almost all internet security protocols — TLS, SSH, PGP, DNSSEC, code signing — rely on these cryptosystems. NIST began the post-quantum cryptography standardization process in 2016, selecting CRYSTALS-Kyber (key encapsulation) and CRYSTALS-Dilithium (digital signatures) in 2024, plus SPHINCS+ and FALCON for backup. The migration of the internet’s PKI infrastructure to post-quantum algorithms is expected to take a decade or more (NIST, “Post-Quantum Cryptography Standardization,” 2024). The “harvest now, decrypt later” threat — where encrypted data is collected today for future decryption — makes this migration urgent. Intelligence agencies and major technology companies are already preparing for the transition.
How Shor’s Algorithm Works
Shor’s algorithm reduces factorization to the order-finding (period-finding) problem. Given N, choose a random integer a coprime to N. Find the smallest positive integer r (the order) such that aʳ ≡ 1 (mod N). If r is even, then aʳ/² - 1 and aʳ/² + 1 share factors with N: gcd(aʳ/² - 1, N) and gcd(aʳ/² + 1, N) reveal factors with high probability. If r is odd or the gcd yields trivial factors, repeat with a different random a. The probability of success per attempt is at least 1/2 for composite N with at least two distinct prime factors. The algorithm thus converts a hard problem (factoring) into a structured problem (period-finding) that quantum computers excel at solving. This reduction is the key conceptual insight — the quantum computer only needs to solve the period-finding subroutine, while the classical part handles the rest.
Quantum Order-Finding
Order-finding is classically hard but efficient on quantum computers using Quantum Phase Estimation (QPE). The algorithm operates on two registers: the first register stores the phase estimation result (t qubits, where t ≈ 2 log₂ N for high probability), and the second register stores the modular exponentiation result (log₂ N qubits). The steps: prepare the first register in equal superposition, apply controlled-U^(2^k) operations where U|x⟩ = |aˣ mod N⟩ and k ranges from 0 to t-1, apply the inverse quantum Fourier transform to the first register, and measure to obtain a phase estimate φ ≈ s/r for some integer s. The continued fractions algorithm extracts r from φ. The entire circuit requires O((log N)³) gates. The quantum subroutine is probabilistic, requiring multiple runs to extract the period with high confidence. The number of runs needed is O(log log N), making the overall algorithm efficient in practice.
The Quantum Fourier Transform
The quantum Fourier transform (QFT) is the quantum analog of the discrete Fourier transform and the engine behind Shor’s algorithm. On t qubits, QFT maps the computational basis state |j⟩ to (1/√2ᵗ) Σ_k exp(2πi jk/2ᵗ) |k⟩. The QFT can be implemented using O(t²) gates: Hadamard gates for creating superpositions and controlled-phase gates for introducing relative phases. The inverse QFT, used in Shor’s algorithm, reverses this process. The QFT is exponentially faster than the classical FFT when the result is not fully extracted: computing the full QFT on t qubits requires O(t²) gates while the classical FFT requires O(t 2ᵗ) operations. However, the QFT does not produce the Fourier coefficients as explicit output — those coefficients are the amplitudes of the quantum state, which are only accessible through measurement. The approximate QFT (AQFT) trades a small amount of precision for reduced gate count, which can be beneficial on noisy hardware. The QFT is also the core subroutine in quantum phase estimation, making it one of the most important quantum algorithmic primitives.
Modular Exponentiation
Modular exponentiation — computing aˣ mod N — is the computational bottleneck of Shor’s algorithm. The circuit implements exponentiation by repeated squaring: aˣ = a^(x₀ + 2x₁ + 4x₂ + …) = a^x₀ · (a²)^x₁ · (a⁴)^x₂ · … where x_k are the bits of x. Each controlled multiplication is implemented as a reversible quantum circuit using O((log N)²) gates. Optimized implementations use specialized adder circuits — the Cuccaro ripple-carry adder (2004) and the Draper BCD adder — to minimize qubit count. The total cost for RSA-2048 factoring is approximately 10⁹ Toffoli gates, requiring a quantum circuit depth of roughly 10⁹. At superconducting gate speeds of ~100 ns, this translates to ~100 seconds of coherent computation — achievable with fault-tolerant error correction but far beyond NISQ capabilities. Windowed arithmetic techniques reduce the number of multiplications by processing multiple bits of the exponent simultaneously, improving the time-space tradeoff.
Resource Requirements
The resource requirements for RSA-2048 factorization have been analyzed extensively. The most comprehensive study is by Gidney and Ekerå (2021), who designed an optimized factoring circuit using 20 million physical qubits with a runtime of 8 hours. This represents a dramatic improvement over earlier estimates of 1 billion qubits. The optimization uses windowed arithmetic for modular exponentiation, a rotated surface code layout for efficient error correction, and optimized T gate distillation factories. The key insight is that with physical qubit error rates of 0.1% (routinely achieved by current hardware), the surface code requires roughly 1,300 physical qubits per logical qubit, and the factoring circuit requires approximately 8,000 logical qubits before error correction overhead (Gidney and Ekerå, “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits,” Quantum, 2021). Subsequent work has further refined these estimates, exploring tradeoffs between qubit count and runtime. These resource estimates continue to improve as both error correction techniques and arithmetic circuit optimization advance.
Post-Quantum Cryptography Migration
The migration to post-quantum cryptography is one of the largest cryptographic transitions in history. NIST’s selected algorithms — CRYSTALS-Kyber (ML-KEM) for key agreement and CRYSTALS-Dilithium (ML-DSA) for signatures — are based on the hardness of lattice problems (Learning With Errors), which are believed resistant to quantum attacks. The migration timeline is driven by “harvest now, decrypt later” threats: encrypted data captured today can be stored and decrypted once a fault-tolerant quantum computer exists. In 2024, the US National Security Agency (NSA) announced CNSA 2.0, mandating post-quantum algorithms for US government systems by 2030. Major technology companies including Google (hybrid Kyber+X25519 in Chrome), Cloudflare, and Signal have already deployed post-quantum key agreement in production. The transition involves updating cryptographic libraries, protocols, and hardware security modules across the global internet infrastructure — a process comparable in scale to the Y2K remediation effort. Organizations should begin inventorying their cryptographic assets and planning migration timelines now.
Experimental Demonstrations
Shor’s algorithm has been implemented for small integers on various quantum platforms, though cryptographically relevant factorizations remain far beyond current hardware. In 2001, IBM demonstrated Shor’s algorithm factoring N=15 on a 7-qubit NMR quantum computer, the first experimental implementation. In 2012, researchers at UC Santa Barbara factored N=21 using a 5-qubit superconducting processor. In 2019, an IBM team factored N=35 using a 7-qubit device with iterative phase estimation, requiring 3 qubits for computation and 4 for readout. These demonstrations use simplifications specific to small numbers, including known period information and optimized circuits that do not generalize to cryptographic sizes. The largest number factored by Shor’s algorithm is N=21 on a trapped-ion system. Scaling to RSA-2048 requires approximately 20 million physical qubits with surface code error correction — roughly four orders of magnitude more than current hardware. Intermediate milestones include factoring 100-bit numbers (requiring ~1 million physical qubits) and demonstrating quantum error correction at the scale needed for fault-tolerant arithmetic.
Frequently Asked Questions
How many qubits are needed to break RSA-2048? Approximately 20 million physical qubits with surface code error correction, or about 8,000 logical qubits before error correction overhead.
Has Shor’s algorithm been implemented experimentally? Shor’s algorithm has been demonstrated for small numbers (N = 15, 21, 35) on various quantum platforms, but scaling to cryptographically relevant sizes requires fault-tolerant quantum computing with millions of qubits.
How does Shor’s algorithm compare to Grover’s? Shor’s algorithm provides an exponential speedup for factoring and discrete logarithms. Grover’s algorithm provides a quadratic speedup for unstructured search.
What happens to RSA when quantum computers are powerful enough? Migration to post-quantum cryptography (lattice-based, hash-based, code-based cryptosystems) is already underway and expected to be complete within 10-15 years.
How does the quantum Fourier transform work? QFT maps computational basis states to superposition states with Fourier coefficients as amplitudes, implemented using O(t²) Hadamard and controlled-phase gates on t qubits.
Related: Grover’s Algorithm | Quantum Supremacy | Quantum Algorithms Guide