Quantum Information & Quantum Computing (Part 10): Shor’s Factoring Algorithm & The Cryptographic Crisis of RSA

In 1994, Peter Shor sent shockwaves through computer science and global intelligence agencies by demonstrating that a quantum computer can factor large composite integers and compute discrete logarithms in polynomial time. Modern asymmetric public-key cryptography—securing HTTPS, global banking networks, blockchain transactions, and military communications through RSA, Diffie-Hellman, and Elliptic Curve Cryptography (ECC)—relies entirely on the conjectured classical hardness of these two number-theoretic problems. Shor’s algorithm proved that this hardness is an artifact of classical Turing machines, not fundamental mathematics.

1. The Cryptographic Landscape: Why RSA Relies on Factoring

The RSA cryptosystem operates on a public modulus $N = p cdot q$, where $p$ and $q$ are large prime numbers (typically 2048 to 4096 bits). The encryption exponent $e$ and decryption exponent $d$ satisfy:

[
e cdot d equiv 1 pmod{phi(N)}, quad text{where } phi(N) = (p-1)(q-1) = N – (p+q) + 1
]

If an adversary can factor $N$ into $p$ and $q$, calculating $phi(N)$ and inverting $e pmod{phi(N)}$ via the Extended Euclidean Algorithm requires trivial microsecond arithmetic. The security of RSA hinges on the fact that the best known classical factoring algorithm, the General Number Field Sieve (GNFS), runs in sub-exponential time:

[
mathcal{O}left( expleft( left(sqrt[3]{frac{64}{9}} + o(1)right) (ln N)^{1/3} (ln ln N)^{2/3} right) right)
]

For a 2048-bit integer, GNFS requires on the order of $2^{112}$ computational operations—vastly exceeding the computational power of all classical supercomputers combined over the age of the universe.

2. Number Theoretic Reduction: Factoring to Period Finding

Shor’s core conceptual insight was that prime factorization can be efficiently reduced to order finding (or period finding) over the multiplicative group of integers modulo $N$, denoted $(mathbb{Z}/Nmathbb{Z})^times$.

Let $a$ be an integer randomly chosen such that $1 < a < N$ and $gcd(a, N) = 1$. Consider the modular exponential function:

[
f(x) = a^x bmod N
]

Because $(mathbb{Z}/Nmathbb{Z})^times$ is a finite group, by Euler’s theorem there exists a smallest positive integer $r$ (the order or period of $a$ modulo $N$) such that:

[
a^r equiv 1 pmod N iff a^r – 1 equiv 0 pmod N
]

If the period $r$ is an even integer, we can factor the algebraic expression as a difference of squares:

[
(a^{r/2} – 1)(a^{r/2} + 1) equiv 0 pmod N
]

This implies that $N$ divides the product $(a^{r/2} – 1)(a^{r/2} + 1)$. As long as $a^{r/2} notequiv -1 pmod N$ (which occurs with probability at least $1 – 1/2^{k-1} ge 1/2$ for a composite $N$ with $k$ distinct odd prime factors), the factors of $N$ cannot divide both terms entirely. Therefore, the greatest common divisor:

[
p = gcd(a^{r/2} – 1, N) quad text{and} quad q = gcd(a^{r/2} + 1, N)
]

yields a non-trivial factor of $N$! Since $gcd$ can be computed classically in $mathcal{O}((log N)^2)$ steps using Euclid’s algorithm, the entire challenge of factoring collapses to finding the period $r$.

3. The Quantum Order-Finding Subroutine

Finding the period $r$ classically requires evaluating $a^x bmod N$ for exponentially many values of $x$. Shor solved this using quantum superposition and the Quantum Fourier Transform.

Circuit Architecture and Execution:

1. Register Setup: Allocate two quantum registers:
   • Register 1 (Control): $t$ qubits initialized to $|0rangle^{otimes t}$, where $2^t approx N^2$ (typically $t = 2 lceil log_2 N rceil$).
   • Register 2 (Target): $n = lceil log_2 N rceil$ qubits initialized to $|1rangle = |00dots 01rangle$.
2. Uniform Superposition: Apply Hadamard transforms to Register 1:
   [
   |psi_1rangle = frac{1}{sqrt{2^t}} sum_{x=0}^{2^t-1} |xrangle |1rangle
   ]
3. Modular Exponentiation Oracle ($U_a$): Implement the coherent modular exponentiation unitary operator $U_a |xrangle |yrangle = |xrangle |y cdot a^x bmod Nrangle$:
   [
   |psi_2rangle = frac{1}{sqrt{2^t}} sum_{x=0}^{2^t-1} |xrangle |a^x bmod Nrangle
   ]
4. Target Register Measurement (or Tracing Out): Measuring Register 2 yields a random remainder $y_0 = a^{x_0} bmod N$. By the periodicity of $f(x)$, this collapses Register 1 into an entangled comb of states separated by the period $r$:
   [
   |psi_3rangle = frac{1}{sqrt{m}} sum_{j=0}^{m-1} |x_0 + j cdot rrangle
   ]
   where $m approx 2^t / r$.
5. Inverse Quantum Fourier Transform ($text{QFT}^dagger$): Applying $text{QFT}^dagger$ transforms the periodic state in the computational basis into sharp interference constructive peaks in the frequency domain:
   [
   |psi_4rangle = text{QFT}^dagger |psi_3rangle = frac{1}{sqrt{r}} sum_{s=0}^{r-1} left| leftlfloor frac{s cdot 2^t}{r} rightrceil rightrangle
   ]
6. Measurement and Continued Fractions: Measuring Register 1 yields an integer $y approx frac{s cdot 2^t}{r}$ with high probability. Dividing by $2^t$ gives:
   [
   frac{y}{2^t} approx frac{s}{r}
   ]
   Because $2^t ge N^2$, the fraction $s/r$ is uniquely determined. Applying the classical Continued Fractions Algorithm to $y/2^t$ extracts the exact denominator $r$ in polynomial time $mathcal{O}((log N)^3)$.

4. The Post-Quantum Cryptographic Transition

Because Shor’s algorithm also solves the discrete logarithm problem over finite fields and elliptic curves in $mathcal{O}(n^3)$ operations, the entire asymmetric cryptographic foundations of modern civilization are obsolete in the presence of a fault-tolerant quantum computer. This reality has catalyzed the NIST Post-Quantum Cryptography (PQC) standardization project, replacing factoring-based protocols with lattice-based cryptography (CRYSTALS-Kyber, CRYSTALS-Dilithium), hash-based signatures (SPHINCS+), and code-based systems that resist quantum Fourier analysis.

Shakil Mahmud Shazal

Senior Software Engineer based in Dhaka, Bangladesh. Building scalable web architectures and writing at the intersection of computer science, physical systems, history, and ideas.