= (log n)(1 + m(m + 1)/2).

But by Theorem 5.6, we have

log r ≥ cx

r¤x

for some constant c > 0, from which it follows that

x ¤ c’1 (log n)(1 + m(m + 1)/2),

and the theorem follows. 2

From this theorem, it follows that the value of r found in step 2 ” which

need not be prime”will be O(len(n)5 ). From this, we obtain:

Theorem 22.3. Algorithm AKS can be implemented so as to run in time

O(len(n)16.5 ).

Proof. As discussed above, the value of r determined in step 2 will be

O(len(n)5 ). It is fairly straightforward to see that the running time of the

algorithm is dominated by the running time of step 5. Here, we have to per-

form O(r1/2 len(n)) exponentiations to the power n in the ring Zn [X]/(Xr ’1).

Each of these exponentiations takes O(len(n)) operations in Zn [X]/(Xr ’ 1),

each of which takes O(r2 ) operations in Zn , each of which takes time

O(len(n)2 ). This yields a running time bounded by a constant times

r1/2 len(n) — len(n) — r2 — len(n)2 = r2.5 len(n)4 .

Substituting the bound O(len(n)5 ) for r, we obtain the stated bound in the

theorem. 2

22.2.2 Correctness

As for the correctness of Algorithm AKS, we ¬rst show:

Theorem 22.4. If the input to Algorithm AKS is prime, then the output

is true.

Proof. Assume that the input n is prime. The test in step 1 will certainly

fail. If the algorithm does not return true in step 3, then certainly the test

22.2 The algorithm and its analysis 493

in step 4 will fail as well. If the algorithm reaches step 5, then all of the

tests in the loop in step 5 will fail”this follows from Theorem 22.1. 2

The interesting case is the following:

Theorem 22.5. If the input to Algorithm AKS is composite, then the output

is false.

The proof of this theorem is rather long, and is the subject of the remain-

der of this section.

Suppose the input n is composite. If n is a prime power, then this will be

detected in step 1, so we may assume that n is not a prime power. Assume

that the algorithm has found a suitable value of r in step 2. Clearly, the test

in 3 will fail. If the test in step 4 passes, we are done, so we may assume

that this test fails; that is, we may assume that all prime factors of n are

greater than r. Our goal now is to show that one of the tests in the loop in

step 5 must pass. The proof will be by contradiction: we shall assume that

none of the tests pass, and derive a contradiction.

The assumption that none of the tests in step 5 fail means that in the

ring Zn [X], the following congruences hold:

(X + j)n ≡ Xn + j (mod Xr ’ 1) (j = 1, . . . , 2 len(n) r1/2 + 1). (22.2)

For the rest of the proof, we ¬x any particular prime divisor p of n ”the

choice does not matter. Since p | n, we have a natural ring homomorphism

from Zn [X] to Zp [X] (see Example 9.48), which implies that the congruences

(22.2) hold in the ring of polynomials over Zp as well. From now on, we

shall work exclusively with polynomials over Zp .

Let us state in somewhat more abstract terms the precise assumptions we

are making in order to derive our contradiction:

(A0) n > 1, r > 1, and ≥ 1 are integers, p is a prime

dividing n, and gcd(n, r) = 1;

(A1) n is not a prime power;

(A2) p > r;

(A3) the congruences

(X + j)n ≡ Xn + j (mod Xr ’ 1) (j = 1, . . . , )

hold in the ring Zp [X];

(A4) the multiplicative order of [n]r ∈ Z— is greater than

r

2;

4 len(n)

> 2 len(n) r1/2 .

(A5)

494 Deterministic primality testing

The rest of the proof will rely only on these assumptions, and not on any

other details of Algorithm AKS. From now on, only assumption (A0) will

be implicitly in force. The other assumptions will be explicitly invoked as

necessary. Our goal is to show that assumptions (A1), (A2), (A3), (A4),

and (A5) cannot all be true simultaneously.

De¬ne the Zp -algebra E := Zp [X]/(Xr ’1), and let · := [X]Xr ’1 ∈ E, so that

E = Zp [·]. Every element of E can be expressed uniquely as g(·) = [g]Xr ’1 ,

for g ∈ Zp [X] of degree less than r, and for an arbitrary polynomial g ∈ Zp [X],

we have g(·) = 0 if and only if (Xr ’ 1) | g. Note that · ∈ E — and has

multiplicative order r: indeed, · r = 1, and · s ’ 1 cannot be zero for s < r,

since Xs ’ 1 has degree less than r.

Assumption (A3) implies that we have a number of interesting identities

in the Zp -algebra E:

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

For the polynomials gj := X + j ∈ Zp [X], with j in the given range, these

identities say that gj (·)n = gj (· n ).

In order to exploit these identities, we study more generally functions

σk , for various integer values k, that send g(·) ∈ E to g(· k ), for arbitrary

g ∈ Zp [X], and we investigate the implications of the assumption that such

functions behave like the kth power map on certain inputs. To this end, let

Z(r) denote the set of all positive integers k such that gcd(r, k) = 1. Note

that the set Z(r) is multiplicative; that is, 1 ∈ Z(r) , and for all k, k ∈ Z(r) ,

we have kk ∈ Z(r) . Also note that because of our assumption (A0), both n

and p are in Z(r) . For integer k ∈ Z(r) , let σk : Zp [X] ’ E be the polynomial

ˆ

evaluation map that sends g ∈ Zp [X] to g(· k ). This is of course a Zp -algebra

homomorphism, and we have:

Lemma 22.6. For all k ∈ Z(r) , the kernel of σk is (Xr ’ 1), and the image

ˆ

of σk is E.

ˆ

Proof. Let J := ker(ˆk ), which is an ideal of Zp [X]. Let k be a positive

σ

integer such that kk ≡ 1 (mod r), which exists because gcd(r, k) = 1.

To show that J = (Xr ’ 1), we ¬rst observe that

σk (Xr ’ 1) = (· k )r ’ 1 = (· r )k ’ 1 = 1k ’ 1 = 0,

ˆ

and hence (Xr ’ 1) ⊆ J.

Next, we show that J ⊆ (Xr ’ 1). Let g ∈ J. We want to show that

(Xr ’ 1) | g. Now, g ∈ J means that g(· k ) = 0. If we set h := g(Xk ),

22.2 The algorithm and its analysis 495

this implies that h(·) = 0, which means that (Xr ’ 1) | h. So let us write

h = (Xr ’ 1)f , for some f ∈ Zp [X]. Then

g(·) = g(· kk ) = h(· k ) = (· k r ’ 1)f (· k ) = 0,

which implies that (Xr ’ 1) | g.

That ¬nishes the proof that J = (Xr ’ 1).

Finally, to show that σk is surjective, suppose we are given an arbitrary

ˆ

element of E, which we can express as g(·) for some g ∈ Zp [X]. Now set

h := g(Xk ), and observe that

σk (h) = h(· k ) = g(· kk ) = g(·). 2

ˆ

Because of lemma 22.6, then by Theorem 9.26, the map σk : E ’ E

that sends g(·) ∈ E to g(· k ), for g ∈ Zp [X], is well de¬ned, and is a ring

automorphism ” indeed, a Zp -algebra automorphism ” on E. Note that for

any k, k ∈ Z(r) , we have

• σk = σk if and only if · k = · k if and only if k ≡ k (mod r), and

• σk —¦ σk = σk —¦ σk = σkk .

So in fact, the set of all σk forms an abelian group (with respect to compo-

sition) that is isomorphic to Z— .

r

Remark. It is perhaps helpful (but not necessary for the proof) to

examine the behavior of the map σk in a bit more detail. Let ± ∈ E,

and let

r’1

gi · i