Let $N$ be a general odd number, which written as its prime factorisation is $N = {p_1}^{\alpha_1} {p_2}^{\alpha_2} \dots {p_s}^{\alpha_s}$. If $x$ is chosen uniformly at random from $\mathbb{Z}^{*}_N$ (group of numbers coprime to $N$) and $r$ is the order of $x$ modulo N. Then \begin{equation} \mathbb{P} [r\text{ is even and }x^{r/2} \not\equiv -1 \text{ mod } N] \geq 1 - \frac{1}{2^{s}} \end{equation}


We need to show that, \begin{equation*} \mathbb{P} [r\text{ is odd or }x^{r/2} \equiv -1 \text{ mod } N] \leq \frac{1}{2^s} \end{equation*}

The Chinese remainder theorem states that $\mathbb{Z}^{*}_N \cong \mathbb{Z}^{*}_{{p_1}^{\alpha_1}} \times \mathbb{Z}^{*}_{{p_2}^{\alpha_2}} \times \dots \times \mathbb{Z}^{*}_{{p_s}^{\alpha_s}}$ from which we can deduce that choosing $x$ uniformly at random from $\mathbb{Z}^{*}_N$ is equivalent to choosing $x_i$ uniformly at random from $\mathbb{Z}^{*}_{{p_j}^{\alpha_j}}$.

Let $r_j$ be the order of $x_j$ modulo ${p_j}^{\alpha_j}$ and let $2^{m_j}$ be the largest power of $2$, which divides $r_j$. So $k_j 2^{m_j} = r_j$ and $k_j$ odd.

Assume that $r$ is odd, which implies that $r_j$ must be odd for each $j$ (so $m_j = 0$), which occurs with probability $2^{-s}$ (from a previous result).

Now assume that $r$ is even, but $x^{r/2} \equiv -1 \text{ mod } N$. Then $x^{r/2} \equiv -1 \text{ mod } {p_j}^{\alpha_j}$. This implies that $r_j$ does not divide $\dfrac{r}{2}$, to see this suppose $r_j \Big| \dfrac{r}{2} \implies cr_j = \dfrac{r}{2}$ and therefore $x_j^{r/2} \equiv x_{j}^{cr_j} \equiv (x_{j}^{r_j})^c \equiv 1 \text{ mod } {p_j}^{\alpha_j} \not\equiv -1 \text{ mod } {p_j}^{\alpha_j}$ giving a contradiction.

Therefore we must have that all $m_j$ are equal to a common value $m$.

It is proving this final statement where I am stuck. The notes, which I am using say;

"Because $r_j$ all divide $r$ and in fact $r$ is a common multiple of the $r_j$, so if one of the $m_j$ has an extra power of $2$ removing this the others should still divide $\dfrac{r}{2}$. But we have shown this is not true."

My Attempt of a Proof (WLOG $r_1$ has extra power of $2$) \begin{align*} r &= c r_1 r_2 \dots r_s \text{(since r is common multiple)}\\ r &= c (k_1 2^{m+1}) r_2 \dots r_s \\ \dfrac{r}{2} &= c (k_1 2^{m}) r_2 \dots r_s \end{align*} and therefore $r_j, \Big| \dfrac{r}{2}$ for $j = 2 \dots s$ the contradiction.

However, surely we can repeat this proof when all $m_j$ are equal an obtain the same contradiction? So where I am going wrong?


When you write $$r = c r_1 r_2 \cdots r_s \quad \text{(since r is common multiple)}$$ $c$ is not generally an integer, so it doesn't follow directly from $$ \frac{r}{2} = c (k_1 2^{m_1-1})r_2\cdots r_s $$ that $r_2\mid \frac{r}{2}$. It also relies on the facts that $2^{m_1}\mid r$ and $m_1>m_2$ (the last only being true WLOG when not all $m_j$ are equal).

If all $m_i=m_2$ then $2^{m_2}$ is the highest power of $2$ that divides the least common multiple of the $r_i$ and so may be the highest power of $2$ that divides $r$ (which may be any common multiple, possibly the LCM), in which case $r_2\not \mid \frac{r}{2}$. It is only guaranteed that $r_2 \mid \frac{r}{2}$ if $m_i>m_2$ for some $i$.

To illustrate, consider $N=13\times 29\times 53$ and $x=2$ whence $$ p_1=13,p_2=29,p_3=53 \\ r_1=12,r_2=28,r_3=52 \\ m_1=m_2=m_3=2 \\ r = \frac{1}{16} r_1 r_2 r_3 $$ The highest power of $2$ that divides $r$ is $2^2$ and none of $r_1,r_2,r_3$ divides $r/2$.

  • 1
    $\begingroup$ I think I have that $2^{m_1} | r$ since $r_i | r$ so that bit is fine. Could you explain more about why $m_1 > m_2$ is needed. Then I would have that all $m_j$ would need to be equal and then finish the proof. Thanks! @Zander $\endgroup$ – Zach Dean Mar 4 '15 at 18:52
  • $\begingroup$ I'm not sure why but maybe @Zander can elaborate on his answer? $\endgroup$ – Stephen Nand-Lal Mar 5 '15 at 23:25
  • $\begingroup$ @ZachDean I've tried to clarify. $\endgroup$ – Zander Mar 6 '15 at 1:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.