Factoring and Cryptography

The most celebrated application of quantum computing is Shor's algorithm: a quantum procedure that factors large integers in polynomial time. RSA — the cryptographic backbone of most encrypted internet traffic — derives its security from the fact that no efficient classical algorithm for factoring is known. Understanding why factoring breaks RSA, and why quantum computers can factor efficiently, is the conceptual foundation for everything that follows in this module.

RSA in one paragraph

RSA key generation works like this. Choose two large primes $p$ and $q$ (each hundreds of digits long) and form their product

$N = p \cdot q.$

The public key consists of $N$ and a small exponent $e$ . The private key is $d$ , computed from $e$ , $p$ , and $q$ using Euler's theorem:

$e \cdot d \equiv 1 \pmod{\varphi(N)}, \qquad \varphi(N) = (p-1)(q-1).$

To encrypt a message $m$ one computes $c = m^e \bmod N$ ; to decrypt, the key holder computes $m = c^d \bmod N$ . The security claim is simple: knowing $N$ but not $p$ and $q$ makes computing $\varphi(N)$ , and therefore $d$ , computationally infeasible.

Why factoring is the hard part

Given $p$ and $q$ it takes a single multiplication to produce $N$ . Given only $N$ , recovering $p$ and $q$ is the integer factorisation problem. No classical algorithm is known to solve it in time polynomial in the number of bits of $N$ .

The best classical algorithm, the General Number Field Sieve, runs in sub-exponential time roughly

$\exp\!\left( c \cdot (\ln N)^{1/3} (\ln \ln N)^{2/3} \right)$

for a small constant $c \approx 1.923$ . For a 2048-bit $N$ this is astronomically large. RSA therefore rests on the computational hardness assumption: factoring $N$ is hard when $N$ is the product of two comparable-sized primes.

Enter Shor's algorithm

In 1994, Peter Shor showed that a quantum computer can factor $N$ in time polynomial in $\log N$ — essentially $O((\log N)^3)$ elementary gate operations with some polylogarithmic overhead. That is an exponential speedup over the best known classical method.

Shor's algorithm does not directly factor $N$ . Instead it solves a related problem called order-finding (also called period-finding): given integers $a$ and $N$ with $\gcd(a, N) = 1$ , find the smallest positive integer $r$ such that

$a^r \equiv 1 \pmod{N}.$

The integer $r$ is called the order of $a$ modulo $N$ . Once $r$ is known, a simple classical calculation reveals the factors of $N$ with high probability.

The reduction from factoring to order-finding is entirely classical — the quantum part is order-finding itself, accomplished via the Quantum Fourier Transform (QFT), which is the subject of the next several lessons.

From order to factors

Here is the classical post-processing step, included now so the full picture is clear.

Suppose we have found the order $r$ of some randomly chosen $a$ . If $r$ is even and $a^{r/2} \not\equiv -1 \pmod{N}$ , then

$a^r - 1 = (a^{r/2} - 1)(a^{r/2} + 1) \equiv 0 \pmod{N}.$

Because $N = pq$ divides the left side but neither factor on the right is divisible by $N$ (by our assumptions), the greatest common divisors

$\gcd(a^{r/2} - 1,\; N) \quad \text{and} \quad \gcd(a^{r/2} + 1,\; N)$

are non-trivial divisors of $N$ , i.e., either $p$ or $q$ . Both GCDs are computed in $O((\log N)^2)$ time by the Euclidean algorithm.

A random $a$ has at least a $1 - 1/2^{k-1}$ chance of yielding an even $r$ with the required property, where $k$ is the number of distinct prime factors of $N$ . For $N = pq$ (two primes) this means success probability at least $1/2$ ; repeating a handful of times gives overwhelming confidence.

Why classical computers cannot keep up

The exponential gap between $O((\log N)^3)$ (Shor) and the sub-exponential GNFS is decisive in the long run. Doubling the bit length of $N$ approximately doubles the cost of Shor's algorithm but increases the GNFS cost by a far larger factor. This means that, as quantum hardware scales, longer RSA keys provide only a temporary fix.

Post-quantum cryptography addresses this by replacing RSA with problems believed to be hard even for quantum computers — lattice problems, hash-based signatures, and others. But those are outside this module. Our goal is to understand how Shor's quantum speedup works from the inside, starting with the Quantum Fourier Transform.

Roadmap for this module

The lessons ahead build Shor's algorithm layer by layer:

The Quantum Fourier Transform (QFT) — the engine that detects periodicity in a quantum superposition.
Quantum Phase Estimation (QPE) — uses the QFT to read out an eigenvalue of a unitary operator.
Modular exponentiation — how to implement $a^x \bmod N$ as a quantum circuit.
Full Shor's algorithm — putting QPE and modular exponentiation together to find $r$ .

By the end you will have written and run all the key sub-circuits on small instances such as $N = 15 = 3 \times 5$ .