Primality Testing - Introduction to Cryptography with Java Applets - page 216

You are invited to verify the values obtained here. When an integer n fails Miller's test,

n is definitely composite, but if it passes, we still don't know for sure whether or not it is

prime. However, there exist no composite integers that can fool Miller's test to every base
b

. We will not
prove this, but will state a proposition to this effect. The proposition actually says something
much stronger; it puts an upper bound on the number of bases for which a composite inte-
ger can fool Miller's test.

; even Carmichael numbers must eventually fail Miller's test for some base b

PROPOSITION 36

Suppose n is an odd, composite positive integer. Then n fails Miller's

test for at least 75 percent of the test bases 1.

For example, take the Carmichael number 561; it passes Fermat's test, but fails Miller's
test for the base 2. (See Table 11.5.)
The failure of Miller's test establishes definitely that 561 is composite. Note that Propo-
sition 36 says that there can be nothing akin to Carmichael numbers for Miller's test. In
fact, Proposition 36 allows us to establish a “probability” that an integer is prime. Suppose,
for example, that we take a very large integer

b where 1 ≤ b ≤ n

n and it passes Miller's test for some base b

between 1 and can pass Miller's test for at most 75 percent of such bases,

there is no more than a 25 percent chance that

n 1. Since n

n is composite, or equivalently, no less than

a 75 percent chance that n is prime.

11.2

THE RABIN-MILLER TEST
If we then repeat Miller's test on n with different bases, we can either discover that n is
composite, or force the probability that it is prime as close to 1 as desired. This is in fact what
modern computers do when searching for large primes, and this particular method of find-
ing “probable” primes is called the Rabin-Miller test.
Succinctly: if an integer n passes Rabin-Miller for q different bases, then the probabil-
ity that n is prime is no less than 1 (1/4) q . It is important to note that the bases used for
the Rabin-Miller test be chosen as randomly as possible. The study of pseudo-random num-
ber generation is a broad topic of great interest to cryptographers; see Chapter 16 on cryp-
tographic applications.

Java Algorithm The Java BigInteger class provides a constructor to generate probable
primes. The test used is different than Rabin-Miller as we have presented it; their version
establishes after q passes that n is prime with probability 1 (1/2) q . (Most likely, they are

TABLE 11.5

Status

Test

2 560

≡ 1 (mod 561) Passes Fermat's test

2 280

≡ 1 (mod 561) Pass

2 140

≡ 67 (mod 561) FAIL-STOP