The Exercise

Shor’s algorithm factors a composite number $N$ through order finding. For $x$ coprime to $N$ , the order $r$ of $x$ modulo $N$ is the least positive integer with $x^r \equiv 1 \pmod N$ . Finding $r$ is the one step that needs a quantum computer, and the procedure around it is classical:

If $N$ is even, return the factor $2$ .
If $N$ is a perfect power, $N = a^b$ for natural numbers $a$ and $b$ with $b \geq 2$ , return $a$ .
Choose $x$ at random with $1 \leq x \leq N - 1$ . If the greatest common divisor $\gcd(x, N)$ exceeds $1$ , return it.
Find the order $r$ of $x$ modulo $N$ with the quantum subroutine.
If $r$ is even and $x^{r/2} \not\equiv -1 \pmod N$ , return $\gcd(x^{r/2} - 1, N)$ , a factor of $N$ other than $1$ and $N$ . Otherwise the run fails.

The exercise runs the procedure on $N = 91$ with $x = 4$ , which is coprime to $91$ . It asks whether $91$ gets past steps one and two, and then for the order of $4$ modulo $91$ and the factor that step five returns.

The Claim

The library states the run as six facts about the numbers $91$ and $4$ .

Theorem 1. Let $r$ be the order of $4$ modulo $91$ . Then $91 = 2k + 1 \quad \text{for some natural number $k$},$ (1)^✦ $91 \neq a^b \quad \text{for all natural numbers $a$ and $b$ with $b \geq 2$},$ (2)^✦ $r = 6,$ (3)^✦ $4^{r/2} \equiv 64 \pmod{91},$ (4)^✦ $4^{r/2} \not\equiv -1 \pmod{91},$ (5)^✦ and $\gcd(4^{r/2} - 1,\, 91) = 7.$ (6)^✦

Statements (1) and (2) take $91$ past steps one and two of the procedure.

What Is Checked

The theorem is stated over the integers modulo $91$ , the residues $0, 1, \dots, 90$ added and multiplied modulo $91$ , in which $-1$ is the residue $90$ : the order in (3) is the order of the residue $4$ , and (4) and (5) compare residues. The other three statements concern natural numbers; in (6), $4^{r/2} - 1$ is the integer $63$ .