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}}\equiv{1}\hbox{ (mod }{p})$ if $a\not{\equiv} 0$.
2. If ${a^2}\equiv{1}\hbox{ (mod }{p})$, then $a{\equiv}1$ or $a{\equiv}-1$. [ $(a+1)(a-1){\equiv}0$]

Suppose we randomly choose $a=2$ and test for consistency with these conditions. Since ${2^{246}}\equiv{220}\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}}\equiv{1}\hbox{ (mod }{247})$. However,

$$27^{246}{\equiv} \left(27^{123}\right)^2\hbox{ and }{27^{123}}\equiv{170}\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}{\equiv}1$) and $178^{123}{\equiv}1$. 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{\equiv}1$ 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.]