i=0

be the canonical representation of ±. Since gcd(r, k) = 1, the map

π : {0, . . . , r ’ 1} ’ {0, . . . , r ’ 1} that sends i to ki mod r is a

permutation whose inverse is the permutation π that sends i to

k i mod r, where k is a multiplicative inverse of k modulo r. Then

we have

r’1 r’1 r’1

ki π(i)

gπ (i) · i .

σk (±) = gi · = gi · =

i=0 i=0 i=0

Thus, the action of σk is to permute the coordinate vector

(g0 , . . . , gr’1 ) of ±, sending ± to the element in E whose coordinate

vector is (gπ (0) , . . . , gπ (r’1) ). So we see that although we de¬ned

the maps σk in a rather “highbrow” algebraic fashion, their behavior

in concrete terms is actually quite simple.

Recall that the pth power map on E is a Zp -algebra homomorphism (see

Theorem 20.7), and so for all ± ∈ E, if ± = g(·) for g ∈ Zp [X], then (by

496 Deterministic primality testing

Theorem 17.1) we have

±p = g(·)p = g(· p ) = σp (±).

Thus, σp acts just like the pth power map on all elements of E.

We can restate assumption (A3) as follows:

σn (· + j) = (· + j)n (j = 1, . . . , ).

That is to say, the map σn acts just like the nth power map on the elements

· + j for j = 1, . . . , .

Now, although the σp map must act like the pth power map on all of

E, there is no good reason why the σn map should act like the nth power

map on any particular element of E, and so the fact that it does so on all

the elements · + j for j = 1, . . . , looks decidedly suspicious. To turn our

suspicions into a contradiction, let us start by de¬ning some notation. For

± ∈ E, let us de¬ne

C(±) := {k ∈ Z(r) : σk (±) = ±k },

and for k ∈ Z(r) , let us de¬ne

D(k) := {± ∈ E : σk (±) = ±k }.

In words: C(±) is the set of all k for which σk acts like the kth power map

on ±, and D(k) is the set of all ± for which σk acts like the kth power map

on ±. From the discussion above, we have p ∈ C(±) for all ± ∈ E, and it is

also clear that 1 ∈ C(±) for all ± ∈ E. Also, it is clear that ± ∈ D(p) for all

± ∈ E, and 1E ∈ D(k) for all k ∈ Z(r) .

The following two simple lemmas say that the sets C(±) and D(k) are

multiplicative.

Lemma 22.7. For any ± ∈ E, if k ∈ C(±) and k ∈ C(±), then kk ∈ C(±).

Proof. If σk (±) = ±k and σk (±) = ±k , then

σkk (±) = σk (σk (±)) = σk (±k ) = (σk (±))k = (±k )k = ±kk ,

where we have made use of the homomorphic property of σk . 2

Lemma 22.8. For any k ∈ Z(r) , if ± ∈ D(k) and β ∈ D(k), then ±β ∈

D(k).

Proof. If σk (±) = ±k and σk (β) = β k , then

σk (±β) = σk (±)σk (β) = ±k β k = (±β)k ,

where again, we have made use of the homomorphic property of σk . 2

22.2 The algorithm and its analysis 497

Let us de¬ne

• s to be the multiplicative order of [p]r ∈ Z— , and

r

• t to be the order of the subgroup of Z— generated by [p]r and [n]r .

r

Since r | (ps ’ 1), if we take any extension ¬eld F of degree s over Zp

(which we know exists by Theorem 20.11), then since F — is cyclic (Theo-

rem 9.15) and has order ps ’ 1, we know that there exists an element ζ ∈ F —

of multiplicative order r (Theorem 8.31). Let us de¬ne the polynomial eval-

uation map „ : Zp [X] ’ F that sends g ∈ Zp [X] to g(ζ) ∈ F . Since Xr ’ 1 is

ˆ

clearly in the kernel of „ , then by Theorem 9.27, the map „ : E ’ F that

ˆ

sends g(·) to g(ζ), for g ∈ Zp [X], is a well-de¬ned ring homomorphism, and

actually, it is a Zp -algebra homomorphism.

For concreteness, one could think of F as Zp [X]/(φ), where φ is an irre-

ducible factor of Xr ’ 1 of degree s. In this case, we could simply take ζ to

be [X]φ (see Example 20.1), and the map „ above would be just the natural

ˆ

map from Zp [X] to Zp [X]/(φ).

The key to deriving our contradiction is to examine the set S := „ (D(n)),

that is, the image under „ of the set D(n) of all elements ± ∈ E for which

σn acts like the nth power map.

Lemma 22.9. Under assumption (A1), we have

t1/2

|S| ¤ n2 .

Proof. Consider the set of integers

I := {nu pv : u, v = 0, . . . , t1/2 }.

We ¬rst claim that |I| > t. To prove this, we ¬rst show that each distinct

pair (u, v) gives rise to a distinct value nu pv . To this end, we make use of

our assumption (A1) that n is not a prime power, and so is divisible by some

prime q other than p. Thus, if (u , v ) = (u, v), then either

• u = u , in which case the power of q in the prime factorization of

nu pv is di¬erent from that in nu pv , or

• u = u and v = v , in which case the power of p in the prime factor-

ization of nu pv is di¬erent from that in nu pv .

The claim now follows from the fact that both u and v range over a set of

size t1/2 + 1 > t1/2 , and so there are strictly more than t such pairs (u, v).

Next, recall that t was de¬ned to be the order of the subgroup of Z— r

generated by [n]r and [p]r ; equivalently, t is the number of distinct residue

classes of the form [nu pv ]r , where u and v range over all non-negative in-

tegers. Since each element of I is of the form nu pv , and |I| > t, we may

498 Deterministic primality testing

conclude that there must be two distinct elements of I, call them k and k ,

that are congruent modulo r. Furthermore, any element of I is a product of

1/2

two positive integers each of which is at most n t , and so both k and k

1/2

lie in the range 1, . . . , n2 t .

Now, let ± ∈ D(n). This is equivalent to saying n ∈ C(±). We always

have 1 ∈ C(±) and p ∈ C(±), and so by lemma 22.7, we have nu pv ∈ C(±)

for all non-negative integers u, v, and so in particular, k, k ∈ C(±).

Since both k and k are in C(±), we have

σk (±) = ±k and σk (±) = ±k .

Since k ≡ k (mod r), we have σk = σk , and hence

±k = ±k .

Now apply the homomorphism „ , obtaining

„ (±)k = „ (±)k .

Since this holds for all ± ∈ D(n), we conclude that all elements of S are

roots of the polynomial Xk ’ Xk . Since k = k , we see that Xk ’ Xk is a

1/2

non-zero polynomial of degree at most max{k, k } ¤ n2 t , and hence can

1/2

roots in the ¬eld F (Theorem 9.14). 2

have at most n2 t

Lemma 22.10. Under assumptions (A2) and (A3), we have

|S| ≥ 2min(t, ) ’ 1.

Proof. Let m := min(t, ). Under assumption (A3), we have · + j ∈ D(n)

for j = 1, . . . , m. Under assumption (A2), we have p > r > t ≥ m, and

hence the integers j = 1, . . . , m are distinct modulo p. De¬ne

m m

ej

∈ Zp [X] : ej ∈ {0, 1} for j = 1, . . . , m, and

P := (X + j) ej < m .

j=1 j=1

{X + j : j =

That is, we form P by taking products over all subsets S

m ’ 1.

1, . . . , m}. Clearly, |P | = 2

De¬ne P (·) := {f (·) ∈ E : f ∈ P } and P (ζ) := {f (ζ) ∈ F : f ∈ P }.

Note that „ (P (·)) = P (ζ), and that by lemma 22.8, P (·) ⊆ D(n).

Therefore, to prove the lemma, it su¬ces to show that |P (ζ)| = 2m ’ 1.

Suppose that this is not the case. This would give rise to distinct polynomials

g, h ∈ Zp [X], both of degree at most t ’ 1, such that

g(·) ∈ D(n), h(·) ∈ D(n), and „ (g(·)) = „ (h(·)).

So we have n ∈ C(g(·)) and (as always) 1, p ∈ C(g(·)). Likewise, we have

22.2 The algorithm and its analysis 499