Simplified justification of the probabilistic Miller–Rabin test for primality

S. B. Gashkov

Diskretnaya Matematika, Tome 10 (1998) no. 4, pp. 35-38

Résumé

Let $m$ be a positive integer and $\mathbb Z_m^*$ be the set of all positive integeres which are no greater than $m$ and relatively prime to $m$. A number $s\in\mathbb Z_m^*$ is called a witness of primality of $m$ if the sequence $$ s^{(m-1)2^{-i}} \pmod m,\quad i = 0,1,\ldots, r,\quad m-1 = 2^{r}t, $$ where $t$ is odd, consists only of ones, or begins with ones and continues by minus one and, may be, then by other integers. We give a simple proof of the following known assertion that is a ground of the Miller–Rabin primality test: The cardinality of the set of witnesses of primality of a composite $m$ is no greater than $\varphi(m)/4$, where $\varphi(m)$ is Euler's totient function. This work was supported by the Russian Foundation for Basic Research, grant 96–01–068.