# 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

\[\mathbb{P} \left(r \text{ is even and } x^{r/2} \not\equiv -1 \pmod{N} \right) \geq 1 - \frac{1}{2^{m-1}}.\]

TheoremSuppose $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

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.12Let $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.

\[\mathbb{P} \left(r \text{ is even and } x^{r/2} \not\equiv -1 \pmod{N}\right) \geq 1 - \frac{1}{2^m}.\]

CorollarySuppose $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

**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