Abstract
Shor’s algorithm, developed by Peter Shor (1994), is a quantum algorithm that efficiently solves the integer factorization problem and the discrete logarithm problem. These tasks are computationally infeasible for classical computers when it comes to large numbers. Since the security of widely used public-key cryptosystems (e.g., RSA) relies on the hardness of these problems, Shor’s algorithm will pose a significant threat to modern encryption when quantum computing becomes a reality. This essay examines Shor’s algorithm, its Quantum Fourier Transform (QFT)-based approach to factorization, and the implications for RSA encryption.
Introduction
Public-key cryptography, particularly RSA encryption, depends on the computational complexity of factoring large integers. Classical algorithms require sub-exponential time, which makes factorization impractical for sufficiently large keys (say, 2048-bit RSA). However, Shor’s algorithm leverages quantum parallelism and interference to solve factorization in polynomial time, and this renders RSA insecure against a sufficiently powerful quantum computer.
For instance, Shor’s algorithm transforms GNFS (General Number Field Sieve) from
O\left( e^{\left(\frac{64}{9}\right)^{1/3} (\log n)^{1/3} (\log \log n)^{2/3}} \right) \quad \text{to} \quad O\left( (\log n)^3 \right)
$$
The Quantum Components of Shor’s Algorithm
Quantum Parallelism & Superposition: A quantum computer operates on qubits, which can exist in superpositions of states. For a function f(x), a quantum circuit can evaluate all possible inputs simultaneously:
|\psi\rangle = \frac{1}{\sqrt{Q}} \sum_{x=0}^{Q-1} |x\rangle |f(x)\rangle
$$
, where Q is a sufficiently large power of 2 for precision.
Quantum Fourier Transform (QFT): The QFT maps a quantum state ∣x⟩ to:
\text{QFT} |x\rangle = \frac{1}{\sqrt{Q}} \sum_{k=0}^{Q-1} e^{\frac{2\pi i x k}{Q}} |k\rangle
$$
The QFT is exponentially faster than the classical FFT and is crucial for extracting the period r.
Phase Estimation & Period Extraction
Shor’s algorithm uses phase estimation to find r:
Step 1: Prepare a superposition.
$$
\frac{1}{\sqrt{Q}} \sum_{x=0}^{Q-1} |a^x \bmod N\rangle
$$
Step 2: Measure the second register, collapsing the first register into a periodic state
\sum_j |x_0 + jr\rangle
$$
Step 3: Apply QFT to the first register, revealing peaks at multiples of Q/r
Step 4: Classical post-processing recovers r via continued fractions
Breaking RSA with Shor’s Algorithm
1. How the RSA Cryptosystem works
Public Key: (N,e), where N=p⋅q, and e⊥ϕ(N)
p,q are large primes
ϕ(N)=(p−1)(q−1) is Euler’s totient function
Private Key: d ≡ e^(−1) modϕ(N),
where d is the modular inverse of e modulo ϕ(N)
Encryption: c ≡ m^(e) mod N
Encrypt message m to get ciphertext c
Decryption: m ≡ c^(d) mod N
Decrypt ciphertext c to recover message m
2. Attack via Factorization
Shor’s algorithm factors N into p & q, and this enables computation of ϕ(N) & d. Once d is known, an attacker can decrypt any message.
Current quantum computers (e.g., IBM, Google) lack sufficient qubits and error correction to factor large RSA keys. Some estimates suggest ~20 million physical qubits may be needed for 2048-bit RSA.
The Solution: Post-Quantum Cryptography
Post-Quantum Cryptography (PQC) refers to cryptographic algorithms that are designed to be secure against both classical and quantum computers. In general, PQC algorithms rely on mathematical problems that are considered harder even for quantum computers to solve.
Here are the key PQC families that are currently being developed:
Lattice-based cryptography, where security is driven by the hardness of lattice problems – e.g., shortest vector problem (SVP), learning with errors (LWE). Notable schemes include Kyber, Dilithium, and NTRU Prime.
Hash-based signatures that rely on the collision resistance of cryptographic hash functions (e.g., SHA-3, SHA-256). Notable schemes include SPHINCS+, XMSS, and LMS.
Code-based cryptography that relies on the hardness of decoding random linear codes (e.g., the syndrome decoding problem). Notable schemes include McEliece, BIKE, and HQC.
Multivariate cryptography, where security is based on the hardness of solving systems of multivariate quadratic equations over finite fields. Notable schemes include Rainbow, GeMSS, and LUOV.
Isogeny-Based Cryptography that depends on the hardness of computing isogenies (morphisms) between elliptic curves. Notable schemes include SIKE (Supersingular Isogeny Key Encapsulation) and CSIDH.
Each family has its own strengths & limitations. For instance, lattice-based or hash-based cryptography are often associated with larger signature sizes. Code-based cryptography has a slower decryption rate due to error correction. Some schemes have been broken in Multivariate Cryptography due to advances in algebraic cryptanalysis. Isogeny-based cryptography is computationally expensive.
Since 2016, NIST (National Institute of Standards and Technology) has been leading the effort to standardize PQC algorithms and released the final standards in 2024. It is estimated that post-2030, RSA/ECC will be phased out in favour of quantum-resistant algorithms.
Closing Comments
Shor’s algorithm remains one of the most significant theoretical threats to modern cryptography as it fundamentally breaches RSA’s security assumptions. While we are possibly a few years away from efficiently factoring 2048-bit keys, the urgency to transition to quantum-safe encryption is real. It’s time to assume the threat model has changed. The cryptographic community must transition to post-quantum algorithms to ensure long-term security. Understanding Shor’s algorithm is essential for preparing for the quantum computing era.
References
Shor, P. W. (1994). Algorithms for quantum computation: discrete logarithms and factoring.
Nielsen, M. A., & Chuang, I. L. (2010). Quantum Computation and Quantum Information.
Gidney, C., & Ekerå, M. (2021). How to factor 2048-bit RSA integers in 8 hours using 20 million noisy qubits.
PS: 30-40% of this paper was written with the help of generative AI.