In this chapter, we discuss some simple and e¬cient probabilistic tests for

primality.

10.1 Trial division

Suppose we are given an integer n > 1, and we want to determine whether n

is prime or composite. The simplest algorithm to describe and to program

is trial division. We simply divide n by 2, 3, and so on, testing if any of

these numbers evenly divide n. Of course, we don™t need to go any further

√

than n, since if n has any non-trivial factors, it must have one that is no

√

greater than n (see Exercise 1.1). Not only does this algorithm determine

whether n is prime or composite, it also produces a non-trivial factor of n

in case n is composite.

Of course, the drawback of this algorithm is that it is terribly ine¬cient:

√

it requires ˜( n) arithmetic operations, which is exponential in the binary

length of n. Thus, for practical purposes, this algorithm is limited to quite

small n. Suppose, for example, that n has 100 decimal digits, and that a

computer can perform 1 billion divisions per second (this is much faster than

any computer existing today). Then it would take on the order of 1033 years

√

to perform n divisions.

In this chapter, we discuss a much faster primality test that allows 100

decimal digit numbers to be tested for primality in less than a second. Unlike

the above test, however, this test does not ¬nd a factor of n when n is

composite. Moreover, the algorithm is probabilistic, and may in fact make

a mistake. However, the probability that it makes a mistake can be made

so small as to be irrelevant for all practical purposes. Indeed, we can easily

make the probability of error as small as 2’100 ” should one really care

about an event that happens with such a miniscule probability?

244

10.2 The structure of Z— 245

n

10.2 The structure of Z—

n

Before going any further, we have to have a ¬rm understanding of the group

Z— , for integer n > 1. As we know, Z— consists of those elements [a]n ∈ Zn

n n

such that a is an integer relatively prime to n. Suppose n = pe1 · · · per is the

r

1

factorization of n into primes. By the Chinese remainder theorem, we have

the ring isomorphism

Zn ∼ Z e1 — · · · — Z er

= pr

p1

which induces a group isomorphism

Z— ∼ Z—e1 — · · · — Z—er .

n= p pr

1

Thus, to determine the structure of the group Z— for general n, it su¬ces

n

e , where p is prime. By Theorem 2.13,

to determine the structure for n = p

we already know the order of the group Z—e , namely, φ(pe ) = pe’1 (p ’ 1).

p

The main result of this section is the following:

Theorem 10.1. If p is an odd prime, then for any positive integer e, the

group Z—e is cyclic. The group Z—e is cyclic for e = 1 or 2, but not for e ≥ 3.

p 2

— is isomorphic to the additive group Z — Z

For e ≥ 3, Z2e 2e’2 .

2

In the case where e = 1, this theorem is a special case of Theorem 9.16,

which we proved in §9.2.3. Note that for e > 1, the ring Zpe is not a ¬eld,

and so Theorem 9.16 cannot be used directly. To deal with the case e > 1,

we need a few simple facts.

Theorem 10.2. Let p be a prime. For integer e ≥ 1, if a ≡ b (mod pe ),

then ap ≡ bp (mod pe+1 ).

Proof. We have a = b + cpe for some c ∈ Z. Thus, ap = bp + pbp’1 cpe + dp2e

for an integer d. It follows that ap ≡ bp (mod pe+1 ). 2

Theorem 10.3. Let p be a prime. Let e ≥ 1 be an integer and assume

pe > 2. If a ≡ 1 + pe (mod pe+1 ), then ap ≡ 1 + pe+1 (mod pe+2 ).

Proof. By Theorem 10.2, ap ≡ (1 + pe )p (mod pe+2 ). Expanding (1 + pe )p ,

we have

p’1

p ek

ep e

p + pep .

(1 + p ) = 1 + p · p +

k

k=2

By Exercise 1.12, all of the terms in the sum on k are divisible by p1+2e , and

1 + 2e ≥ e + 2 for all e ≥ 1. For the term pep , the assumption that pe > 2

means that either p ≥ 3 or e ≥ 2, which implies ep ≥ e + 2. 2

246 Probabilistic primality testing

Now consider Theorem 10.1 in the case where p is odd. As we already

know that Z— is cyclic, assume e > 1. Let x ∈ Z be chosen so that [x]p

p

— . Suppose the multiplicative order of [x] e ∈ Z— is m. Then

generates Zp p pe

as xm ≡ 1 (mod pe ) implies xm ≡ 1 (mod p), it must be the case that

p ’ 1 divides m, and so [xm/(p’1) ]pe has multiplicative order exactly p ’ 1.

By Theorem 8.38, if we ¬nd an integer y such that [y]pe has multiplicative

order pe’1 , then [xm/(p’1) y]pe has multiplicative order (p ’ 1)pe’1 , and we

are done. We claim that y := 1 + p does the job. Any integer between 0

and pe ’ 1 can be expressed as an e-digit number in base p; for example,

y = (0 · · · 0 1 1)p . If we compute successive pth powers of y modulo pe , then

by Theorem 10.3 we have

y mod pe = (0 ··· 0 1 1)p ,

y p mod pe = (— ··· — 1 0 1)p ,

2

y p mod pe = (— ··· — 1 0 0 1)p ,

.

.

.

e’2

yp mod pe = (1 0 · · · 0 1)p ,

e’1

yp mod pe = (0 ··· 0 1)p .

Here, “—” indicates an arbitrary digit. From this table of values, it is clear

(see Theorem 8.37) that [y]pe has multiplicative order pe’1 . That proves

Theorem 10.1 for odd p.

We now prove Theorem 10.1 in the case p = 2. For e = 1 and e = 2, the

theorem is easily veri¬ed. Suppose e ≥ 3. Consider the subgroup G ⊆ Z—e 2

e ’1 as e-digit binary

generated by [5]2e . Expressing integers between 0 and 2

numbers, and applying Theorem 10.3, we have

5 mod 2e = (0 ··· 0 1 0 1)2 ,

52 mod 2e = (— ··· — 1 0 0 1)2 ,

.

.

.

e’3

52 mod 2e = (1 0 · · · 0 1)2 ,

e’2

52 mod 2e = (0 ··· 0 1)2 .

So it is clear (see Theorem 8.37) that [5]2e has multiplicative order 2e’2 .

We claim that [’1]2e ∈ G. If it were, then since it has multiplicative order

/

2, and since any cyclic group of even order has precisely one element of