A probabilistic test for primality

- if .
- If , then or . [ ]

Perhaps we were lucky
with . If we try , we get
. However,

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

Not every choice of is inconsistent with the conditions.
For example,
(hence
) and
. However, the fact that some choices of give a
proof that a number is not prime suggests the following test:

**Rabin's Primality Test.** Let , where m is an odd number.
Choose at random. Compute the sequence

This sequence is consistent with being a prime if or if the sequence has at some point, followed by 1 for all subsequent terms. In all other cases, provides a proof that is not prime (this is usually described by saying that is a

Two features of the test should be emphasized. It does not provide
an absolute guarantee that is a prime, only that it is probably a prime
(we will analyze exactly how probable in the next section). Secondly,
when we know 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.]

2002-12-14