j+1 j

for j = 0, . . . , h ’ 1, ±m2 = 1 implies ±m2 = ±1}.

The Miller“Rabin test uses this set Ln , in place of the set Ln de¬ned

above. It is clear from the de¬nition that Ln ⊆ Ln .

Testing whether a given ± ∈ Z+ belongs to Ln can be done using the

n

following procedure:

β ← ±m

if β = 1 then return true

for j ← 0 to h ’ 1 do

if β = ’1 then return true

if β = +1 then return false

β ← β2

return false

It is clear that using a repeated-squaring algorithm, this procedure runs

in time O(len(n)3 ). We leave it to the reader to verify that this procedure

correctly determines membership in Ln .

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

n

|Ln | ¤ (n ’ 1)/4.

250 Probabilistic primality testing

The rest of this section is devoted to a proof of this theorem. Let n ’ 1 =

m2h , where m is odd.

Case 1: n is prime. Let ± ∈ Z— . Since Z— is a group of order n ’ 1,

n n

and the order of a group element divides the order of the group, we know

h

that ±m2 = ±n’1 = 1. Now consider any index j = 0, . . . , h ’ 1 such that

j+1 j j+1

±m2 = 1, and consider the value β := ±m2 . Then since β 2 = ±m2 = 1,

— is cyclic of even

the only possible choices for β are ±1 ” this is because Zn

order and so there are exactly two elements of Z— whose multiplicative order

n

divides 2, namely ±1. So we have shown that ± ∈ Ln .

Case 2: n = pe , where p is prime and e > 1. Certainly, Ln is contained

in the kernel K of the (n ’ 1)-power map on Z— . By Theorem 8.31, |K| =

n

gcd(φ(n), n ’ 1). Since n = pe , we have φ(n) = pe’1 (p ’ 1), and so

pe ’ 1 n’1

e’1 e

|Ln | ¤ |K| = gcd(p (p ’ 1), p ’ 1) = p ’ 1 = e’1 ¤ .

+ ··· + 1

p 4

Case 3: n = pe1 · · · per is the prime factorization of n, and r > 1. For

r

1

i = 1, . . . , r, let Ri denote the ring Zpei , and let

i

θ : R1 — · · · — Rr ’ Zn

be the ring isomorphism provided by the Chinese remainder theorem.

Also, let φ(pei ) = mi 2hi , with mi odd, for i = 1, . . . , r, and let :=

i

—

min{h, h1 , . . . , hr }. Note that ≥ 1, and that each Ri is a cyclic group

of order mi 2hi .

We ¬rst claim that for any ± ∈ Ln , we have ±m2 = 1. To prove this,

¬rst note that if = h, then by de¬nition, ±m2 = 1, so suppose that < h.

By way of contradiction, suppose that ±m2 = 1, and let j be the largest

j+1

index in the range , . . . , h ’ 1 such that ±m2 = 1. By the de¬nition

j

of Ln , we must have ±m2 = ’1. Since < h, we must have = hi for

some particular index i = 1, . . . , r. Writing ± = θ(±1 , . . . , ±r ), we have

m2j = ’1. This implies that the multiplicative order of ±m is equal to

±i i

j+1 (see Theorem 8.37). However, since j ≥

2 = hi , this contradicts the

m

fact that the order of a group element (in this case, ±i ) must divide the

—

order of the group (in this case, Ri ).

From the claim in the previous paragraph, and the de¬nition of Ln , it

’1

follows that ± ∈ Ln implies ±m2 = ±1. We now consider an experiment in

which ± is chosen at random from Z— (that is, with a uniform distribution),

n

m2 ’1 = ±1] ¤ 1/4, from which the theorem will follow.

and show that P[±

Write ± = θ(±1 , . . . , ±r ). As ± is uniformly distributed over Z— , each ±i is

n

— , and the collection of all the ± is a mutually

uniformly distributed over Ri i

independent collection of random variables.

10.3 The Miller“Rabin test 251

For i = 1, . . . , r and j = 0, . . . , h, let Gi (j) denote the image of the (m2j )-

—

power map on Ri . By Theorem 8.31, we have

mi 2hi

|Gi (j)| = .

gcd(mi 2hi , m2j )

¤ h and ¤ hi , a simple calculation shows that

Because

|Gi (h)| divides |Gi ( )| and 2|Gi ( )| = |Gi ( ’ 1)|.

In particular, |Gi ( ’ 1)| is even and is no smaller than 2|Gi (h)|. The fact

that |Gi ( ’ 1)| is even implies that ’1 ∈ Gi ( ’ 1).

’1

The event ±m2 = ±1 occurs if and only if either

’1

m2

(E1 ) ±i = 1 for i = 1, . . . , r, or

’1

m2 = ’1 for i = 1, . . . , r.

(E2 ) ±i

’1

m2

Since the events E1 and E2 are disjoint, and since the values ±i are

’1

m2

mutually independent, with each value ±i uniformly distributed over

Gi ( ’ 1) (see part (a) of Exercise 8.22), and since Gi ( ’ 1) contains ±1,

we have

r

1

’1

m2

= ±1] = P[E1 ] + P[E2 ] = 2

P[± ,

|Gi ( ’ 1)|

i=1

and since |Gi ( ’ 1)| ≥ 2|Gi (h)|, we have

r

1

’1 ’r+1

m2

= ±1] ¤ 2

P[± . (10.1)

|Gi (h)|

i=1

’1

If r ≥ 3, then (10.1) directly implies that P[±m2 = ±1] ¤ 1/4, and we

are done. So suppose that r = 2. In this case, Theorem 10.5 implies that

n is not a Carmichael number, which implies that for some i = 1, . . . , r, we

must have Gi (h) = {1}, and so |Gi (h)| ≥ 2, and (10.1) again implies that

’1

P[±m2 = ±1] ¤ 1/4.

That completes the proof of Theorem 10.6.

Exercise 10.4. Show that an integer n > 1 is prime if and only if there

exists an element in Z— of multiplicative order n ’ 1.

n