From Period to Factors

Shor's algorithm has two parts: a quantum subroutine that finds the period $r$ of the function $f(x) = a^x \bmod N$ , and a classical post-processing step that converts that period into a factor of $N$ . This lesson is about the classical step, which relies on a beautiful theorem from number theory.

Why the period gives factors

Suppose $\gcd(a, N) = 1$ (otherwise $a$ itself or $N/a$ is already a factor). The period $r$ is the smallest positive integer satisfying

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

If $r$ is even we can write

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

so $N$ divides the product of the two factors on the right. Unless $a^{r/2} \equiv -1 \pmod{N}$ (a failure case), at least one of those factors shares a non-trivial common divisor with $N$ . The Euclidean algorithm extracts it:

$p = \gcd\!\bigl(a^{r/2} - 1,\; N\bigr).$

If $p \neq 1$ and $p \neq N$ then $p$ is a proper factor of $N$ , and we are done. The other factor follows immediately as $q = N / p$ .

A worked example: factoring 21

Let $N = 21$ and $a = 2$ . The quantum period-finding circuit would measure the period $r = 6$ (since $2^6 = 64 \equiv 1 \pmod{21}$ ). Check: $64 - 1 = 63 = 3 \times 21$ .

Post-processing:

$r = 6$ is even, so we proceed.
$a^{r/2} = 2^3 = 8$ . Since $8 \not\equiv -1 \equiv 20 \pmod{21}$ , the condition is satisfied.
$\gcd(8 - 1,\; 21) = \gcd(7, 21) = 7$ .
The two factors are $7$ and $21/7 = 3$ .

Indeed $21 = 3 \times 7$ .

Euclidean gcd in JavaScript

The Euclidean algorithm is iterative and takes only a few lines:

function gcd(x, y) {
  while (y !== 0) {
    const t = y;
    y = x % y;
    x = t;
  }
  return x;
}

Each step replaces $(x, y)$ with $(y, x \bmod y)$ ; when $y$ reaches zero, $x$ holds the answer.

Try it

The quantum subroutine has already done the hard work and returned $r = 6$ for $N = 21$ , $a = 2$ . Implement the classical post-processing and return the non-trivial factor.

Run your code to see the quantum state.