Probability bound in factoring to order-finding
Given a positive integer $N$ and an integer $x$ ($1\leq x < N$) co-prime to $N$. The order of $x$ modulo $N$ is the smallest positive integer $r$ such that $x^r \equiv 1 \pmod{N}$. Order-finding problem then aims to solve $r$ given $N$ and $x$. A probalistic result, Theorem A4.13, is given in Appendix 4.3 of (Nielsen and Chuang 2010)1.
As mentioned by Yihan Guo, the bound in (Nielsen and Chuang 2010)1 could be incorrect. After a detailed checking, I agree with Yihan and a modified version of Theorem A4.13 should be as follows.
Probability of Random Choosing an Even Order Number
Theorem Suppose $N = p_1^{\alpha_1} \cdots p_m^{\alpha_m}$ is the prime factorization of an odd composite positive integer. Let $x$ be chosen uniformly at random from $\mathbb{Z}_N^*$, and let $r$ be the order of $x$, modulo $N$. Then
\[\mathbb{P} \left(r \text{ is even and } x^{r/2} \not\equiv -1 \pmod{N} \right) \geq 1 - \frac{1}{2^{m-1}}.\]
In the above Theorem, \(\mathbb{Z}_N^*\) is the set of all elements in \(\mathbb{Z}_N\), which are co-prime to $N$. The size of \(\mathbb{Z}_N^*\) is \(\varphi(N)\), which is known as Euler \(\varphi\) function. The proof of Theorem relies on the Chinese remainder theorem and Lemma A4.12 in (Nielsen and Chuang 2010)1. We cite the statement of Lemma A4.12 in this post.
Lemma A4.12 Let $p$ be an odd prime. Let $2^D$ be the largest power of 2 dividing $\varphi(p^\alpha)$. Then with probability exactly one-half $2^D$ divides the order modulo $p^{\alpha}$ of a randomly chosen element of $\mathbb{Z}_{p^\alpha}^*$.
Proof of Theorem. We prove that \(\begin{equation} \label{eq:ineq} \mathbb{P} \left(r \text{ is odd or } x^{r/2} \equiv -1 \pmod{N} \right) \leq \frac{1}{2^{m-1}}. \end{equation}\)
Given an integer $x \in \mathbb{Z}_N^*$ with $r$ being its order modulo $N$. Since $p_i^{\alpha_i}$ is a factor of $N$, we have,
\[\begin{equation*} x^r \equiv 1 \pmod{N} \Longrightarrow x^r \equiv 1 \pmod{p_i^{\alpha_i}} \quad i = 1, 2, \dots, m. \end{equation*}\]We define ${x_i}_{i=1}^m$ as, \(\begin{equation} \label{eq:xieqx} x_i \equiv x \pmod{p_i^{\alpha_i}} \quad i = 1, 2, \dots, m, \end{equation}\) with $r_i$ being their orders modulo $p_i^{\alpha_i}$ respectively, i.e.,
\[\begin{equation*} x_i^{r_i} \equiv 1 \pmod{p_i^{\alpha_i}}. \end{equation*}\]We take to $r$-th power of \eqref{eq:xieqx} and obtain, \(\begin{equation} \label{eq:mod1} x_i^r \equiv x^r \equiv 1 \pmod{p_i^{\alpha_i}}. \end{equation}\) Hence we conclude that $r_i$ divides $r$, i.e., $r_i \mid r$.
We further denote $d$ and $d_i$ be the largest power of 2 divide $r$ and $r_i$, respectively.
Now we consider the cases in the probability statement \eqref{eq:ineq}: 1) $r$ is odd; and 2) $r$ is even and $x^{r/2} \equiv -1 \pmod{N}$.
When $r$ is odd, we have that all $r_i$ are odd. Hence we have $d = d_1 = \cdots = d_m = 0$.
When $r$ is even and $x^{r/2} \equiv -1 \pmod{N}$, we have similar modulo congruence formula, \(\begin{equation} \label{eq:modn1} x_i^{r/2} \equiv x^{r/2} \equiv -1 \pmod{p_i^{\alpha_i}}. \end{equation}\) Comparing \eqref{eq:mod1} and \eqref{eq:mod1}, we know that $r_i \nmid \frac{r}{2}$. Together with $r_i \mid r$, we know that $r$ and $r_i$ have the same power of 2 factor, i.e., $d_i = d$ for $i=1, 2, \dots, m$.
Now we are ready to bound the probability \eqref{eq:ineq}. By Chinese remainder theorem, uniform sampling from \(\mathbb{Z}_N^*\) is equivalent to uniform sampling from \(\mathbb{Z}_{p_i^{\alpha_i}}^*\) independetly. Further we denote the the largest power of 2 dividing $\varphi(p_i^{\alpha_i})$ as $D_i$. By Lemma A4.12, we know that
\[\begin{equation*} \mathbb{P}\left(r_i = 2^{D_i}\{odd\}\right) = \frac{1}{2}. \end{equation*}\]The above analysis on $r$ shows that the statement in the probability must obeys that $d = d_1 = \cdots = d_m$. Hence we could rewrite \eqref{eq:ineq} as,
\[\begin{equation*} \begin{split} & \mathbb{P} \left(r \text{ is odd or } x^{r/2} \equiv -1 \pmod{N} \right) \\ \leq & \sum_{d = 0}^{\min_i{D_i}} \prod_{i=1}^m \mathbb{P} \left(r_i = 2^{d}\{odd\}\right) \\ \leq & \sum_{d = 0}^{\min_i{D_i}-1} \prod_{i=1}^m \mathbb{P} \left(r_i = 2^{d}\{odd\} \right) + \frac{1}{2^m}\\ \leq & \prod_{i=1}^m \sum_{d = 0}^{\min_i{D_i}-1} \mathbb{P} \left(r_i = 2^{d}\{odd\} \right) + \frac{1}{2^m} \\ \leq & \prod_{i=1}^m (1-\frac{1}{2}) + \frac{1}{2^m} \\ = & \frac{1}{2^{m-1}}. \end{split} \end{equation*}\]Hence we proved Theorem.
Revisit the Bound
Through the above proof, we find that the original bound $1-\frac{1}{2^m}$ as in Theorem A4.13 in (Nielsen and Chuang 2010)1 could still hold if we change the assumption in the statement. Hence we give the following Corollar.
Corollary Suppose $N = p_1^{\alpha_1} \cdots p_m^{\alpha_m}$ is the prime factorization of an odd composite positive integer, and $D_i$ is the largest power of 2 dividing $\varphi(p_i^{\alpha_i})$. Assume $D_i$ are not all equal to each other. Let $x$ be chosen uniformly at random from $\mathbb{Z}_N^*$, and let $r$ be the order of $x$, modulo $N$. Then
\[\mathbb{P} \left(r \text{ is even and } x^{r/2} \not\equiv -1 \pmod{N}\right) \geq 1 - \frac{1}{2^m}.\]
Proof of Corollary.
All other parts of the proof remain the same as that of Theorem. We would rederive the bound on the probability. Without loss of generality, we assume $D_1$ is greater than the minimum of $D_i$, i.e., $D_1 > \min_i D_i$. By Lemma A4.12, we have
\[\sum_{d=0}^{\min_i D_i} \mathbb{P} \left(r_1 = 2^d\{odd\} \right) \leq \frac{1}{2}.\]Then we could rewrite \eqref{eq:ineq} as,
\[\begin{equation*} \begin{split} & \mathbb{P}\left(r \text{ is odd or } x^{r/2} \equiv -1 \pmod{N} \right) \\ \leq & \sum_{d = 0}^{\min_i{D_i}} \prod_{i=1}^m \mathbb{P} \left(r_i = 2^{d}\{odd\} \right) \\ \leq & \left( \sum_{d = 0}^{\min_i{D_i}} \mathbb{P}\left( r_1 = 2^{d}\{odd\} \right) \right) \prod_{i=2}^m \frac{1}{2}\\ \leq & \frac{1}{2^m}. \end{split} \end{equation*}\]Hence we proved Corollary.
Example 1 ($N=3$)
Through the proof of Theorem, we find that the Theorem should also hold for odd prime numbers. We take $N = 3$ as an example (as provided by Yihan Guo).
| Number | Order $r$ | $x^{r/2}$ mod $N$ | Check |
|---|---|---|---|
| 1 | 1 |  |
|
| 2 | 2 | -1 | |
The probability is 0 and the bound is also 0, i.e.,
\[0 = \mathbb{P} \left(r \text{ is even and } x^{r/2} \not\equiv -1 \pmod{3} \right) \geq 1 - \frac{1}{2^{1-1}} = 0.\]Example 2 ($N=15$)
We take $N = 15$ as another example.
| Number | Order $r$ | $x^{r/2}$ mod $N$ | Check |
|---|---|---|---|
| 1 | 1 | |
|
| 2 | 4 | 4 |  |
| 4 | 2 | 4 | |
| 7 | 4 | 4 | |
| 8 | 4 | 4 | |
| 11 | 2 | 11 | |
| 13 | 4 | 4 | |
| 14 | 2 | -1 | |
The probability is $\frac{6}{8}$ and the bound is $\frac{1}{2}$, i.e.,
\[\frac{3}{4} = \mathbb{P} \left(r \text{ is even and } x^{r/2} \not\equiv -1 \pmod{3} \right) \geq 1 - \frac{1}{2^{2-1}} = \frac{1}{2}.\]In this case, the original Theorem A4.13 in (Nielsen and Chuang 2010)1 also holds. By the argument around Corollary, we have $D_1 = 1$ and $D_2 = 2$, which are not equal to each other. Hence Corollary holds and so is the bound in Theorem A4.13.
Example 3 ($N=63$)
We take $N = 63 = 3^2 \cdot 7$ as the last example.
| Number | Order $r$ | $x^{r/2}$ mod $N$ | Check |
|---|---|---|---|
| 1 | 1 | |
|
| 2 | 6 | 8 | |
| 4 | 3 | |
|
| 5 | 6 | -1 | |
| 8 | 2 | 8 | |
| 10 | 6 | 55 | |
| 11 | 6 | 8 | |
| 13 | 6 | 55 | |
| 16 | 3 | |
|
| 17 | 6 | -1 | |
| 19 | 6 | 55 | |
| 20 | 6 | -1 | |
| 22 | 3 | |
|
| 23 | 6 | 8 | |
| 25 | 3 | |
|
| 26 | 6 | -1 | |
| 29 | 6 | 8 | |
| 31 | 6 | 55 | |
| 32 | 6 | 8 | |
| 34 | 6 | 55 | |
| 37 | 3 | |
|
| 38 | 6 | -1 | |
| 40 | 6 | 55 | |
| 41 | 6 | -1 | |
| 43 | 3 | |
|
| 44 | 6 | 8 | |
| 46 | 3 | |
|
| 47 | 6 | -1 | |
| 50 | 6 | 8 | |
| 52 | 6 | 55 | |
| 53 | 6 | 8 | |
| 55 | 2 | 55 | |
| 58 | 3 | |
|
| 59 | 6 | -1 | |
| 61 | 6 | 55 | |
| 62 | 2 | -1 | |
The probability is $\frac{18}{36}$ and the bound is $\frac{1}{2}$, i.e.,
\[\frac{1}{2} = \mathbb{P} \left(r \text{ is even and } x^{r/2} \not\equiv -1 \pmod{3} \right) \geq 1 - \frac{1}{2^{2-1}} = \frac{1}{2}.\]In this case, the original Theorem A4.13 in (Nielsen and Chuang 2010)1 does not hold.
Yingzhou Li
Reference
Discussion
I'm a faculty at Fudan University. Follow me on Github and Bitbucket. Hopefully, you will find my code useful. You are also welcome to either email me or post comments below to discuss on these posts.