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

CHAPTER 11

Primality Testing

Note that we are now using cryptosystems that require us to find and use large prime
numbers. How do we find large prime numbers? Do we pick a large random odd inte-
ger and try to factor it? No. Factoring takes a lot of time, and is not a good way of deter-
mining whether or not an integer is prime. In fact, this is exactly what makes the Rabin
cipher and others like it secure. If factoring the public key

n was not extremely difficult, any-

one could factor ). You may have

assumed that attempted factoring is the only way to determine whether or not a number is
prime. It isn't. We develop alternative methods to do this now.
First recall Fermat's Little Theorem (FLT): If

n and obtain the private key values p and q (the factors of n

a p 1 p is prime and p a , 1 (mod p ). (Note

a p 1

that the contrapositive of FLT says that if 1 (mod p ), p must be composite.) What about

a p 1

the converse of FLT? That is, if is prime? Sur-

prisingly, this is often true. We can see this if we raise 2 to some integer powers, as shown
in Table 11.1.
It appears that when

1 (mod p ), can we conclude that p

is
composite, we get a value not congruent to 1. However, this doesn't always hold. There are
composite integers

n is prime, we always get a value congruent to 1, and when n

for which 2 n 1

31.
When we raise 2 to the 340 power, we get a least nonnegative residue of 1 modulo 341. (Ver-
ify.) If the converse of FLT were true, we could conclude that 341 is prime; but it obviously
isn't, so the converse of FLT is not true.
There isn't anything special about the choice of 2 as our base, so we might want to sim-
ply try another base. For example, we apply “Fermat's test” on 341 using 3 as the base. We
get

n 1 (mod n ). Take the composite number 341 = 11

3 340 56 (mod 341).

This establishes immediately that 341 is composite. So, we might think we can get around
the failure of Fermat's test by just trying different bases modulo

n until we either

1. Obtain a least nonnegative residue not equal to 1, and conclude that n is composite.

2. Do not obtain a residue congruent to 1 modulo n after many tries with different bases,

and conclude that n is probably prime since we can't prove it isn't using this test.