A probabilistic test for primality

Suppose we want to test whether 247 is a prime number. Recall two facts about prime numbers $p$:

1.

$a^{p-1}\equiv1\hbox{ (mod }p)$ if $a\not\equiv 0$.

2.

If $a^2\equiv1\hbox{ (mod }p)$, then $a\equiv1$ or $a\equiv-1$. [ $(a+1)(a-1)\equiv0$]

Suppose we randomly choose $a=2$ and test for consistency with these conditions. Since $2^{246}\equiv220\hbox{ (mod }247)$ we can conclude immediately that 247 is not a prime.

Perhaps we were lucky with $a=2$. If we try $a=27$, we get $a^{246}\equiv1\hbox{ (mod }247)$. However,

$$27^{246}\equiv \left(27^{123}\right)^2\hbox{ and }27^{123}\equiv170\hbox{ (mod }247)$$

which is inconsistent with the second condition, again implying 247 is not a prime.

Not every choice of $a$ is inconsistent with the conditions. For example, $160^{123}\equiv-1$ (hence $160^{246}\equiv1$) and $178^{123}\equiv1$. However, the fact that some choices of $a$ give a proof that a number is not prime suggests the following test:

Rabin's Primality Test. Let $p-1=2^km$, where m is an odd number. Choose $a$ at random. Compute the sequence

$$a^m\quad a^{2m}\quad a^{4m} \dots a^{p-1}\qquad\hbox{mod $p$}$$

This sequence is consistent with $p$being a prime if $a^m\equiv1$ or if the sequence has $-1$ at some point, followed by 1 for all subsequent terms. In all other cases, $a$ provides a proof that $p$ is not prime (this is usually described by saying that $a$ is a witness that $p$ is not prime). Repeat this test for some number of random choices of $a$, and conclude that $p$ is a prime if none of the chosen $a$ is a witness.

Two features of the test should be emphasized. It does not provide an absolute guarantee that $p$ is a prime, only that it is probably a prime (we will analyze exactly how probable in the next section). Secondly, when we know $p$ is not a prime, we do not know what its factors are-- factoring is much more difficult than testing for primality.

[A different probabilistic test is described near the end of the RSA paper.]