Reduction to Period Finding

Shor's algorithm does not directly decompose a large integer. Instead it transforms the factoring problem into a completely different one — period finding — and then solves that with the quantum Fourier transform. This lesson traces that transformation step by step.

Why period finding breaks factoring

Let $N$ be the integer you want to factor, and pick any $a$ with $1 \lt a \lt N$ and $\gcd(a, N) = 1$ (a is coprime to $N$ ). Consider the sequence

$a^0 \bmod N,\; a^1 \bmod N,\; a^2 \bmod N,\; a^3 \bmod N, \ldots$

Because there are only $N$ possible remainders, this sequence must eventually repeat. The smallest positive integer $r$ such that

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

is called the order (or period) of $a$ modulo $N$ . It always exists when $\gcd(a, N) = 1$ .

From the period to a factor

Once you know $r$ , a single algebraic identity yields a factor with high probability.

Step 1. If $r$ is odd, or if $a^{r/2} \equiv -1 \pmod{N}$ , the argument fails — restart with a different $a$ . Both bad cases happen with probability at most $\tfrac{1}{2}$ for any composite $N$ that is not a prime power, so on average two random choices of $a$ suffice.

Step 2. If $r$ is even and $a^{r/2} \not\equiv -1 \pmod{N}$ , write the identity

$a^r - 1 \equiv 0 \pmod{N}$

and factor the left side as a difference of squares:

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

Since neither factor is $0 \pmod{N}$ (by assumption), the product is divisible by $N$ but neither factor alone is. That means $N$ shares a non-trivial common factor with at least one of $a^{r/2} - 1$ and $a^{r/2} + 1$ .

Step 3. Compute $\gcd(a^{r/2} - 1, N)$ and $\gcd(a^{r/2} + 1, N)$ . At least one of these is a proper factor of $N$ .

Worked example: factoring 15

Choose $a = 7$ , $N = 15$ . The period is $r = 4$ (even, and $7^2 = 49 \equiv 4 \not\equiv -1 \pmod{15}$ ).

Compute $a^{r/2} = 7^2 = 49 \equiv 4 \pmod{15}$ .

$\gcd(4 - 1,\; 15) = \gcd(3, 15) = 3, \qquad \gcd(4 + 1,\; 15) = \gcd(5, 15) = 5.$

Both GCDs are proper factors, confirming $15 = 3 \times 5$ .

The only remaining difficulty is computing $r$ efficiently. Classically, evaluating $a^k \bmod N$ for all $k$ up to $r$ takes time exponential in the bit-length of $N$ . The quantum speedup comes entirely from the next step: using the quantum Fourier transform to read off the period from a superposition of all powers at once.

The full reduction in one sentence

Shor's algorithm replaces the classically hard question "what are the prime factors of $N$ ?" with the quantumly easy question "what is the order of $a$ modulo $N$ ?", then extracts factors from the order using three lines of classical arithmetic.