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

## Best Answer

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$