Factoring 15

Shor's algorithm is the clearest demonstration that quantum computers can break the hardest problems in classical cryptography. Factoring $N = 15$ is the smallest non-trivial example: it is small enough to trace by hand yet rich enough to expose every component of the algorithm.

The full Shor pipeline

Shor's algorithm combines classical number theory with a single quantum subroutine. For $N = 15$ the five-step outline is:

Choose a random base $a$ with $1 \lt a \lt N$ and $\gcd(a, N) = 1$ . We pick $a = 7$ .
Detect a lucky shortcut. If $\gcd(a, N) \neq 1$ you already have a factor — but with a composite $N$ that is not a prime power this happens with negligible probability.
Run the quantum period-finding subroutine to find the order $r$ of $a$ modulo $N$ , i.e. the smallest positive $r$ with $a^r \equiv 1 \pmod{N}$ .
Classical post-processing: from $r$ extract a factor using $\gcd(a^{r/2} \pm 1,\, N)$ .
Verify. If the GCD step fails (rare), restart with a different $a$ .

Step 3 in detail: the quantum subroutine

The quantum subroutine uses quantum phase estimation (QPE) applied to the unitary $U_a$ defined by $U_a |y\rangle = |ay \bmod N\rangle$ . Its eigenstates are the states

$|u_s\rangle = \frac{1}{\sqrt{r}} \sum_{k=0}^{r-1} e^{-2\pi i sk/r} |a^k \bmod N\rangle, \qquad s = 0, 1, \ldots, r-1,$

with eigenvalue $e^{2\pi i s/r}$ . QPE estimates the phase $s/r$ , and the continued-fraction algorithm extracts the denominator $r$ from that rational approximation.

For $N = 15$ with $a = 7$ the period is $r = 4$ . You can verify this directly:

$7^1 \equiv 7,\quad 7^2 \equiv 4,\quad 7^3 \equiv 13,\quad 7^4 \equiv 1 \pmod{15}.$

A practical QPE circuit for $N = 15$ uses $n = \lceil \log_2 15 \rceil = 4$ work qubits in the target register and $t = 2n = 8$ counting qubits for sufficient precision. The full circuit has hundreds of gates; in this lesson we focus on the classical bookkeeping around the quantum call.

Step 4 in detail: classical post-processing

With the period $r = 4$ in hand, the factoring step is pure arithmetic.

Check applicability. Is $r$ even? Yes, $4$ is even. Is $a^{r/2} \equiv -1 \pmod{N}$ ? Compute $7^2 \bmod 15 = 49 \bmod 15 = 4$ . Since $4 \neq 14 \equiv -1 \pmod{15}$ , the condition is satisfied.

Apply the difference-of-squares identity. Since $a^r \equiv 1 \pmod{N}$ , we have

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

For $a = 7$ , $r = 4$ :

$(7^2 - 1)(7^2 + 1) = 48 \times 50 = 2400 = 160 \times 15.$

Extract factors with Euclid's algorithm.

$\gcd(7^2 - 1,\; 15) = \gcd(48,\; 15) = \gcd(3,\; 15) = 3,$ $\gcd(7^2 + 1,\; 15) = \gcd(50,\; 15) = \gcd(5,\; 15) = 5.$

Both $3$ and $5$ are proper factors of $15$ , and indeed $15 = 3 \times 5$ .

Why no classical algorithm matches this

The best classical factoring algorithm for a general integer $N$ is the general number field sieve (GNFS), which runs in time $\exp\!\bigl(O((\log N)^{1/3}(\log\log N)^{2/3})\bigr)$ — super-polynomial. Shor's quantum algorithm runs in $O((\log N)^3)$ gate operations, an exponential improvement. For $N = 15$ the difference is invisible; for a 2048-bit RSA modulus it means the difference between a few hours on a fault-tolerant quantum computer and the age of the universe on any classical machine.

Try it

The quantum subroutine has already run and returned period $r = 4$ for $a = 7$ , $N = 15$ . Your task is to complete the classical post-processing step: compute $\gcd(a^{r/2} - 1,\, N)$ using the provided helpers and return the factor.

Run your code to see the quantum state.