order 2 (see Theorem 8.31), it must be equal to [52 ]2e ; however, it is clear

e’3

≡ ’1 (mod 2e ). Let H ⊆ Z—e be the

from the above calculation that 52 2

subgroup generated by [’1]2e . Then from the above, G © H = {[1]2e }, and

hence by Theorem 8.28, G — H is isomorphic to the subgroup G · H of Z—e . 2

10.3 The Miller“Rabin test 247

But since the orders of G — H and Z—e are equal, we must have G · H = Z—e .

2 2

That proves the theorem.

Exercise 10.1. Show that if n is a positive integer, the group Z— is cyclic

n

if and only if

n = 1, 2, 4, pe , or 2pe ,

where p is an odd prime and e is a positive integer.

Exercise 10.2. Let n = pq, where p and q are distinct primes such that

p = 2p + 1 and q = 2q + 1, where p and q are themselves prime. Show

that the subgroup (Z— )2 of squares is a cyclic group of order p q .

n

Exercise 10.3. Let n = pq, where p and q are distinct primes such that

p (q ’ 1) and q (p ’ 1).

(a) Show that the map that sends [a]n ∈ Z— to [an ]n2 ∈ (Z— 2 )n is a group

n n

isomorphism.

(b) Consider the element ± := [1 + n]n2 ∈ Z— 2 ; show that for any non-

n

negative integer k, ±k = [1 + kn]n2 , and conclude that ± has multi-

plicative order n.

(c) Show that the map from Zn — Z— to Z— 2 that sends ([k]n , [a]n ) to

n n

n]

[(1 + kn)a n2 is a group isomorphism.

10.3 The Miller“Rabin test

We describe in this section a fast (polynomial time) test for primality, known

as the Miller“Rabin test. The algorithm, however, is probabilistic, and

may (with small probability) make a mistake.

We assume for the remainder of this section that the number n we are

testing for primality is an odd integer greater than 1.

Several probabilistic primality tests, including the Miller“Rabin test, have

the following general structure. De¬ne Z+ to be the set of non-zero elements

n

of Zn ; thus, |Z+ | = n ’ 1, and if n is prime, Z+ = Z— . Suppose also that we

n n n

+ such that:

de¬ne a set Ln ⊆ Zn

• there is an e¬cient algorithm that on input n and ± ∈ Z+ , determines

n

if ± ∈ Ln ;

• if n is prime, then Ln = Z— ;

n

• if n is composite, |Ln | ¤ c(n ’ 1) for some constant c < 1.

248 Probabilistic primality testing

To test n for primality, we set an “error parameter” t, and choose random

elements ±1 , . . . , ±t ∈ Z+ . If ±i ∈ Ln for all i = 1, . . . , t, then we output

n

true; otherwise, we output false.

It is easy to see that if n is prime, this algorithm always outputs true, and

if n is composite this algorithm outputs true with probability at most ct . If

c = 1/2 and t is chosen large enough, say t = 100, then the probability that

the output is wrong is so small that for all practical purposes, it is “just as

good as zero.”

We now make a ¬rst attempt at de¬ning a suitable set Ln . Let us de¬ne

Ln := {± ∈ Z+ : ±n’1 = 1}.

n

Note that Ln ⊆ Z— , since if ±n’1 = 1, then ± has a multiplicative inverse,

n

n’2 . Using a repeated-squaring algorithm, we can test if ± ∈ L

namely, ± n

3 ).

in time O(len(n)

Theorem 10.4. If n is prime, then Ln = Z— . If n is composite and Ln

n

— , then |L | ¤ (n ’ 1)/2.

Zn n

Proof. Note that Ln is the kernel of the (n ’ 1)-power map on Z— , and hence

n

—.

is a subgroup of Zn

If n is prime, then we know that Z— is a group of order n ’ 1. Since the

n

order of a group element divides the order of the group, we have ±n’1 = 1

for all ± ∈ Z— . That is, Ln = Z— .

n n

Suppose that n is composite and Ln Z— . Since the order of a subgroup

n

— | = m|L | for some integer m > 1.

divides the order of the group, we have |Zn n

From this, we conclude that

n’1

1— 1

|Zn | ¤ |Z— | ¤ .2

|Ln | =

2n

m 2

Unfortunately, there are odd composite numbers n such that Ln = Z— .

n

Such numbers are called Carmichael numbers. The smallest Carmichael

number is

561 = 3 · 11 · 17.

Carmichael numbers are extremely rare, but it is known that there are in-

¬nitely many of them, so we can not ignore them. The following theorem

puts some constraints on Carmichael numbers.

Theorem 10.5. A Carmichael number n is of the form n = p1 · · · pr , where

the pi are distinct primes, r ≥ 3, and (pi ’ 1) | (n ’ 1) for i = 1, . . . , r.

10.3 The Miller“Rabin test 249

Proof. Let n = pe1 · · · per be a Carmichael number. By the Chinese remain-

r

1

der theorem, we have an isomorphism of Z— with the group

n

Z—e1 — · · · — Z—er ,

pr

p 1

and we know that each group Z—ei is cyclic of order pi i ’1 (pi ’ 1). Thus,

e

pi

the power n ’ 1 kills the group Z— if and only if it kills all the groups Z—ei ,

n p i

pei ’1 (pi

’ 1) | (n ’ 1). Now, on the one hand,

which happens if and only if i

n ≡ 0 (mod pi ). On the other hand, if ei > 1, we would have n ≡ 1 (mod pi ),

which is clearly impossible. Thus, we must have ei = 1.

It remains to show that r ≥ 3. Suppose r = 2, so that n = p1 p2 . We have

n ’ 1 = p1 p2 ’ 1 = (p1 ’ 1)p2 + (p2 ’ 1).

Since (p1 ’ 1) | (n ’ 1), we must have (p1 ’ 1) | (p2 ’ 1). By a symmetric

argument, (p2 ’ 1) | (p1 ’ 1). Hence, p1 = p2 , a contradiction. 2

To obtain a good primality test, we need to de¬ne a di¬erent set Ln , which

we do as follows. Let n ’ 1 = 2h m, where m is odd (and h ≥ 1 since n is

assumed odd), and de¬ne

h

Ln := {± ∈ Z+ : ±m2 = 1 and