# Derivation of Factoring to Order Finding Algorithm

group-theorynumber theoryquantum-computation

Suppose $$N=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_m^{\alpha_m}$$ is the prime factorization of an odd composite positive integer. Let $$x$$ is chosen uniformly at random from $$\mathbb{Z}_N^*$$, and $$r$$ be the order of $$x$$ modulo $$N$$. Then
$$Pr(r\text{ is even and }x^{r/2}\neq -1\pmod{N})\geq 1-\frac{1}{2^m}$$
or equivalently,$$Pr(r\text{ is odd or }x^{r/2}= -1\pmod{N})\leq \frac{1}{2^m}$$

By the Chinese Remainder theorem, choosing $$x$$ uniformly at random from $$\mathbb{Z}_N^*$$ is equivalent to choosing $$x_j$$ independently and uniformly at random from $$\mathbb{Z}_{p_j^{\alpha_j}}^*$$ such that $$x=x_j(mod\;{p_j^{\alpha_j}})$$ for each $$j$$.

Let, $$r_j$$ be the order of $$x_j$$ modulo $$p_j^{\alpha_j}$$, Let $$2^{d_j}$$ be the largest power of $$2$$ that divides $$r_j$$, $$2^{d}$$ be the largest power of $$2$$ that divides $$r$$.

Lemma : Let $$p$$ be an odd prime. Let $$2^{d'}$$ be the largest power of $$2$$ dividing $$\phi(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}^*.$$

$$Pr(2^{d'}|r)=Pr(2^{d'}\nmid r)=\frac{1}{2}$$

Part 1

$$r$$ is odd then all $$r_i$$ are odd. $$Pr(r_i\text{ is odd})\leq \frac{1}{2}$$. Since the $$x_i$$ are chosen independently then $$Pr(r\text{ is odd})\leq \frac{1}{2^m}$$

$$x^r=1\pmod{N}\implies x^r=1\pmod{p_i^{\alpha_i}}\\ x=x_i\pmod{p_i^{\alpha_i}}\implies x^r=x^r_i\pmod{p_i^{\alpha_i}}\\ \implies x^r_i=1\pmod{p_i^{\alpha_i}}\\ \implies r_i|r$$
$$\therefore$$ If $$r$$ is odd then all $$r_i$$ are odd. From Lemma, $$2^{d'}$$ divides the group $$\mathbb{Z}^*_{p_i^{\alpha_i}}$$ into two sets : 1) $$2^{d'}|r$$ 2) $$2^{d'}\nmid r$$

Odd $$r_i$$ does not fall in the set 1 and not all elements in set 2 are odd, therefore the probability of obtaining odd $$r_i$$ is less than $$1/2$$, which proves the claim.

Part 2

If $$r$$ is even and $$x^{r/2}=-1\pmod{N}$$ then all the $$r_i$$ can be expressed as $$2^d (odd\#)$$ for some fixed $$d$$ and $$Pr(r_i=2^d (odd\#))\leq 1/2$$

$$r$$ is even and
$$x^{r/2}=-1\pmod{N})\implies x^{r/2}=-1\pmod{p_i^{\alpha_i}}\\ x=x_i\pmod{p_i^{\alpha_i}}\implies x_i^{r/2}=-1\pmod{ p_i^{\alpha_i}}\\ \implies r_i|r\quad\&\quad r_i\nmid r/2\\$$
As defined, $$r_i=2^{d_i}(odd\;\#)=2^{d_i}\times \mathcal{O}_1$$ and $$r=2^d(odd\;\#)=2^d\times \mathcal{O}_2$$
$$r_i|r\implies d_i\leq d\\ r_i\nmid r/2\implies d_i>d-1\Longleftrightarrow d_i\geq d\\ \therefore d_i=d\quad \forall\quad i\\ i.e., r_i=2^d(odd\;\#)=2^{d}\times \mathcal{O}_1$$

How do I proceed further making use of Lemma and prove the claim in part two and show that $$Pr(r\text{ is even and }x^{r/2}\neq -1\pmod{N})\leq \frac{1}{2^m}$$ ?

For Actual reference :

Lemma implies that exactly half the elements of $$\mathbb{Z}^*_{p_j^{\alpha_j}}$$ have $$d_j=d'$$ where $$d'$$ is the largest power of $$2$$ dividing $$\phi({p_j^{\alpha_j}})$$, i.e., $$P$$($$d_j=d'$$) $$=1/2$$

Therefore, $$P$$($$d_j=$$ any particular value) $$\leq 1/2$$

From part 2, when $$r$$ is odd then $$r_j|r$$ for each $$j$$ and this implies $$r_j$$ is odd.$$\implies d_j=0$$ for all $$j$$.

This concludes, when $$r$$ is odd or $$x^{r/2}=-1\pmod{N}$$ the value of $$d_j$$ is the same for all $$j$$.

Since $$P$$($$d_j=$$ any particular value) $$\leq 1/2$$ we can obtain

$$P(r\text{ is odd or }x^{r/2}=-1\pmod{N})\leq1/2^m$$