Exercise 3.3.25* (Rabin-Miller algorithm versus Solovay-Strassen algorithm)

Proof. Here $m$ is an odd positive integer, such that $m-1=2^{k}d$, where $2\nmid d$.

Recall that

Let $\alpha ={[a]}_m$ ( $a\in \mathbb{Z}$) be any element of $\mathscr{H}$. Then

• Assume first that $a^d\equiv 1(\mathit{mod}m)$. Then $a^{(m-1)∕2^k}\equiv 1(\mathit{mod}m)$, where $k\ge 1$, since $p-1$ is even. Hence

  $$a^{\frac{m-1}{2}}={\left(a^{\frac{m-1}{2^k}}\right)}^{2^{k-1}}\equiv 1(\mathit{mod}m).$$

  It remains to show that $\left(\frac{a}{m}\right)=1$. Since $a^d\equiv 1(\mathit{mod}m)$,

  $${\left(\frac{a}{m}\right)}^d=\left(\frac{a^d}{m}\right)=\left(\frac{1}{m}\right)=1,$$

  where $d$ is odd, and $\left(\frac{a}{m}\right)=\pm 1$, thus ${\left(\frac{a}{m}\right)}^d=\left(\frac{a}{m}\right)$, which gives

  $$\left(\frac{a}{m}\right)=1.$$

  So $a^{\frac{m-1}{2}}\equiv \left(\frac{a}{m}\right)=1(\mathit{mod}m)$. This shows that $\alpha ={[a]}_p\in 𝒢$.

• Assume now that $a^{2^{j}d}\equiv -1(\mathit{mod}m)$ for some integer $j$, $0\le j<k$.

  We begin by computing $\left(\frac{a}{p}\right)$ for the prime divisors $p$ of $m$. Let $p\mid m$ be such a prime divisor. Then $p$ is odd, and there are some integers $s,t$ such that $p-1=2^{s}t,2\nmid t,s\ge 1$. Since $t$ is odd,

  $${\left(a^{2^{j}d}\right)}^t\equiv {(-1)}^t=-1(\mathit{mod},).$$

  where $p\mid m$, thus

  $${\left(a^{2^{j}t}\right)}^d\equiv -1(\mathit{mod}p).$$

  Since $d$ is also odd,

  $$a^{2^{j}t}\equiv -1(\mathit{mod}p).$$

  By Fermat’s Theorem, $1\equiv a^{p-1}=a^{2^{s}t}(\mathit{mod}p)$. Assume, for the sake of contradiction, that $s\le j$. Then $1\equiv {\left(a^{2^{s}t}\right)}^{2^{j-s}}=a^{2^{j}t}\equiv -1(\mathit{mod}p)$. This is impossible, because $p$ is odd. This contradiction shows that $s\ge j+1$. Moreover

  • If $s=j+1$, then

    $$\begin{array}{lll}\hfill \left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}=a^{2^{s-1}t}=a^{2^{j}t}\equiv -1(\mathit{mod}p),& & \hfill \end{array}$$

    so $\left(\frac{a}{p}\right)=-1$.

  • If $s>j+1$, then

    $$\left(\frac{a}{p}\right)\equiv a^{2^{s-1}t}={\left(a^{2^{j}t}\right)}^{2^{s-j-1}}\equiv {(-1)}^{2^{s-j-1}}\equiv 1(\mathit{mod}p).$$

  To summarize, under the hypothesis $a^{d{2}^j}\equiv -1(\mathit{mod}m)$ $(0\le j<k)$, if $p=1+2^{s}t$ is a prime divisor of $m=1+2^{k}d$, then $s\ge j+1$, and

  $$\begin{array}{lll}\hfill \left(\frac{a}{p}\right)=\{\begin{array}{cc}-1\hfill & \text{if }s=j+1,\hfill \\ +1\hfill & \text{if }s>j+1.\hfill \end{array}& & \hfill \text{(1)}\end{array}$$

  Now we can compare $a^{(m-1)∕2}$ and $\left(\frac{a}{m}\right)$.

  • Suppose first that $j<k-1$. From $a^{2^{j}d}\equiv -1(\mathit{mod}m)$, we deduce

    $$a^{\frac{m-1}{2}}=a^{2^{k-1}d}={\left(a^{2^{j}d}\right)}^{2^{k-1-j}}\equiv {(-1)}^{2^{k-1-j}}=1(\mathit{mod}m).$$

    Write $m=p_1{p}_2\cdots p_l$, where the $p_i$ are not necessarily distinct. Then $\left(\frac{a}{m}\right)=\underset{i=1}{\overset{l}{\prod <!--\; FUNCTION\; APPLICATION\; -->}}\left(\frac{a}{p_i}\right)$. By equation (1), the only $p_i$ (distinct or not) whose contribution in this product is $-1$ are the $p_i=1+2^{s_i}{t}_i(2\nmid t_i)$ such that $s_i=j+1$, so that $p_i=1+2^{j+1}{t}_i$. If there are $q$ such prime factors $p_i$, then $\left(\frac{a}{m}\right)={(-1)}^q$. By renumbering the $p_i$, we may suppose that these $p_i$ are $p_1,p_2,\dots ,p_q$ and the others are $p_{q+1},\dots ,p_l$, which satisfy $p_i\equiv 1(\mathit{mod}{2}^{j+2})$ ( $q+1\le i\le l$), so that $p_i=1+2^{j+2}{u}_i$ for some integers $u_i$, and

    $$\begin{array}{llll}\hfill m=1+2^{k}d& =(1+2^{j+1}{t}_1)\cdots (1+2^{j+1}{t}_q)(1+2^{j+2}{u}_{q+1})\cdots (1+2^{j+2}{u}_l)& \hfill & \\ \hfill & \equiv {(1+2^{j+1})}^q(\mathit{mod}{2}^{j+2}).& \hfill & \end{array}$$

    Since $k\ge q+2$, $2^{k}d\equiv 0(\mathit{mod}{2}^{j+2})$, thus

    $$1\equiv {(1+2^{j+1})}^q(\mathit{mod}{2}^{j+2}).$$

    By the binomial formula,

    $$1\equiv 1+q{2}^{j+1}(\mathit{mod}{2}^{j+2}),$$

    thus $q\equiv 0(\mathit{mod}2)$, so $q$ is even and $\left(\frac{a}{m}\right)={(-1)}^q=1$. This shows that $a^{(m-1)∕2}\equiv \left(\frac{a}{m}\right)$, so $\alpha ={[a]}_p\in 𝒢$.

  • It remains the case where $j=k-1$. Then $a^{2^{k-1}d}\equiv -1(\mathit{mod}m)$, so $a^{(m-1)∕2}\equiv -1(\mathit{mod}p)$. With the same notations as in the previous case,

    $$m=1+2^{j+1}d\equiv {(1+2^{j+1})}^q(\mathit{mod}{2}^{j+2}).$$

    Therefore, since $d$ is odd, $1+2^{j+1}\equiv 1+q{2}^{j+1}(\mathit{mod}{2}^{j+2})$, thus $q\equiv 1(\mathit{mod}2)$, and $\left(\frac{a}{m}\right)={(-1)}^q=-1\equiv a^{(m-1)∕2}$. So $\alpha ={[a]}_p\in 𝒢$.

In all cases, $\alpha \in 𝒢$. We have proved that

□