Project: End-to-End Shor

Shor's algorithm is the headline result of quantum computing: it factors an $n$-bit integer in time polynomial in $n$, breaking RSA in principle. Yet most of the algorithm is classical. The only quantum step is order finding — and everything around it is number theory you can run on a laptop. This capstone assembles the full pipeline and asks you to write the classical glue that turns a measured period into a factor.

The reduction: factoring to order finding

Pick an integer $1 < a < N$ coprime to $N$ (if $\gcd(a, N) \neq 1$ you already have a factor). Define the order $r$ as the smallest positive integer with

If $r$ is even, then $a^{r/2}$ is a square root of $1 \bmod N$. Provided $a^{r/2} \not\equiv -1 \pmod N$, it is a nontrivial square root, and

so $N$ divides the product but neither factor alone. Therefore $\gcd(a^{r/2} \pm 1, N)$ gives a nontrivial factor of $N$.

What the quantum part contributes

The order $r$ is the period of the function $f(x) = a^x \bmod N$. Quantum phase estimation applied to the modular-multiplication unitary $U_a|y\rangle = |ay \bmod N\rangle$ measures a phase $s/r$ for a random $s$, and continued fractions recover $r$ from that estimate. This is the only piece that needs a quantum computer; for a full register of $a^x \bmod 15$ the simulator could run it, but at the scale of cryptographic $N$ it is classically intractable — which is the whole point.

The worked instance $N = 15$, $a = 7$

The order of $7$ modulo $15$ is $r = 4$, because

Since $r = 4$ is even, compute $a^{r/2} = 7^2 = 49 \equiv 4 \pmod{15}$. As $4 \neq 14 = N - 1$, this run succeeds, and

We have factored $15 = 3 \times 5$.

Try it

Implement factorFromPeriod(N, a, r) for the worked instance. Handle the two failure conditions by returning 0, otherwise return the smaller recovered factor. The grader checks you return $3$ for $N = 15$, $a = 7$, $r = 4$.

Sign in on the full site to ask questions and join the discussion.