Modular Exponentiation

Shor's algorithm factors an integer $N$ by finding the period of the function $f(x) = a^x \bmod N$ for a randomly chosen base $a$. Before the quantum part can shine, a classical circuit must evaluate $f(x)$ for every $x$ in superposition. That building block is called modular exponentiation.

What modular arithmetic means

The expression $a^x \bmod N$ asks: raise $a$ to the power $x$, then take the remainder on dividing by $N$. For example,

$7^1 \bmod 15 = 7, \quad 7^2 \bmod 15 = 49 \bmod 15 = 4, \quad 7^3 \bmod 15 = 7 \cdot 4 \bmod 15 = 28 \bmod 15 = 13.$

Because there are only $N$ possible remainders $(0, 1, \ldots, N-1)$, the sequence of values $f(0), f(1), f(2), \ldots$ must eventually repeat. The length of that repeating block is the period $r$, defined by

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

For $a = 7$, $N = 15$ you can check that $7^4 = 2401 = 160 \times 15 + 1$, so $r = 4$.

Repeated squaring

Computing $a^x \bmod N$ directly by multiplying $a$ together $x$ times is far too slow for large $x$. Repeated squaring (also called fast modular exponentiation) reduces the cost to $O(\log x)$ multiplications by exploiting the binary representation of $x$:

$a^{13} = a^{8+4+1} = a^8 \cdot a^4 \cdot a^1.$

The algorithm squares the running base and takes its remainder mod $N$ at each step, multiplying it into the running result whenever the current low bit of the exponent is 1:

$\text{result} \leftarrow 1, \quad \text{base} \leftarrow a \bmod N.$

Then, while $x > 0$:

1. If $x$ is odd, set $\text{result} \leftarrow (\text{result} \times \text{base}) \bmod N$.
2. Set $\text{base} \leftarrow \text{base}^2 \bmod N$.
3. Set $x \leftarrow \lfloor x/2 \rfloor$.

For $a = 7$, $x = 4$, $N = 15$:

| Step | exponent bit | base | result | |------|-------------|------|--------| | start | — | 7 | 1 | | $x=4$ (even) | 0 | $7^2 \bmod 15 = 4$ | 1 | | $x=2$ (even) | 0 | $4^2 \bmod 15 = 1$ | 1 | | $x=1$ (odd) | 1 | $1^2 \bmod 15 = 1$ | $(1 \times 1) \bmod 15 = 1$ |

Result: $7^4 \bmod 15 = 1$.

Why this matters for quantum circuits

In the full Shor algorithm the quantum register holds a superposition $\sum_{x=0}^{2^n-1} |x\rangle |0\rangle$. A controlled unitary then maps this to $\sum_{x} |x\rangle |a^x \bmod N\rangle$ in one step — but the gate that performs this mapping is exactly the quantum version of modular exponentiation. Understanding the classical algorithm is the first step to understanding how that controlled unitary is constructed.

Try it

Implement the classical modpow(a, x, N) function using repeated squaring and return $7^4 \bmod 15$. The grader checks that your answer equals 1.

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