The Exercise

Factoring an odd integer $N > 1$ by order finding begins with a unit $x$ drawn at random from $\mathbb{Z}_N^*$ , the group of residues modulo $N$ coprime to $N$ , under multiplication modulo $N$ . The quantum algorithm for order finding returns the order $r$ of $x$ , the least positive integer with $x^r \equiv 1 \pmod N$ , and the draw is of use when $x$ lies in the set of good units $G_N = \{\, x \in \mathbb{Z}_N^* : r \text{ is even and } x^{r/2} \not\equiv -1 \pmod N \,\}.$ (1) A unit drawn uniformly at random is good with probability $|G_N|/\varphi(N)$ , where Euler’s function $\varphi(N)$ is the number of units modulo $N$ .

Theorem 5.3 of the book bounds this probability from below in terms of the number $m$ of distinct primes dividing $N$ : a random unit is good with probability at least $1 - 1/2^m$ .

The Claim

Theorem 1. There is an odd integer $N > 1$ , with $m$ distinct prime factors, for which $\frac{|G_N|}{\varphi(N)} < 1 - \frac{1}{2^m}.$ (2)^✦

Theorem 2. Let $N > 1$ be an odd integer with $m$ distinct prime factors. Then $\frac{|G_N|}{\varphi(N)} \ge 1 - \frac{1}{2^{m-1}}.$ (3)^✦

This is the book’s Theorem 5.3 with $2^{m-1}$ in place of $2^m$ .

What Is Checked

Both theorems are stated over the integers modulo $N$ with their usual number theory: the unit group $\mathbb{Z}_N^*$ , the order of a unit, Euler’s function and the distinct primes dividing $N$ . What the library proves about them is the count of good units, (3) for every odd $N > 1$ and (2) for at least one.