1, n, p ∈ C(h(·)). By lemma 22.7, for all integers k of the form nu pv , where

u and v range over all non-negative integers, we have

k ∈ C(g(·)) and k ∈ C(h(·)).

For any such k, since „ (g(·)) = „ (h(·)), we have „ (g(·))k = „ (h(·))k , and

hence

0 = „ (g(·))k ’ „ (h(·))k

= „ (g(·)k ) ’ „ (h(·)k ) („ is a homomorphism)

= „ (g(· k )) ’ „ (h(· k )) (k ∈ C(g(·)) and k ∈ C(h(·)))

= g(ζ k ) ’ h(ζ k ) (de¬nition of „ ).

Thus, the polynomial f := g ’ h ∈ Zp [X] is a non-zero polynomial of degree

at most t ’ 1, having roots ζ k in the ¬eld F for all k of the form nu pv .

Now, t is by de¬nition the number of distinct residue classes of the form

[nu pv ]r ∈ Z— . Also, since ζ has multiplicative order r, for integers k, k , we

r

have ζ k = ζ k if and only if k ≡ k (mod r). Therefore, as k ranges over

all integers of the form nu pv , ζ k ranges over precisely t distinct values in F .

But since all of these values are roots of the polynomial f , which is non-zero

and of degree at most t ’ 1, this is impossible (Theorem 9.14). 2

We are now (¬nally!) in a position to complete the proof of Theorem 22.5.

Under assumptions (A1), (A2), and (A3), Lemmas 22.9 and 22.10 imply that

t1/2

2min(t, ) ’ 1 ¤ |S| ¤ n2 . (22.3)

The contradiction is provided by the following:

Lemma 22.11. Under assumptions (A4) and (A5), we have

t1/2

2min(t, ) ’ 1 > n2 .

Proof. Observe that log2 n ¤ len(n), and so it su¬ces to show that

t1/2

2min(t, ) ’ 1 > 22 len(n) ,

and for this, it su¬ces to show that

min(t, ) > 2 len(n) t1/2 ,

since for any integers a, b with a > b ≥ 1, we have 2a > 2b + 1.

To show that t > 2 len(n) t1/2 , it su¬ces to show that t > 2 len(n)t1/2 ,

or equivalently, that t > 4 len(n)2 . But observe that by de¬nition, t is the

order of the subgroup of Z— generated by [n]r and [p]r , which is at least as

r

500 Deterministic primality testing

large as the multiplicative order of [n]r in Z— , and by assumption (A4), this

r

2.

is larger than 4 len(n)

Finally, directly by assumption (A5), we have > 2 len(n) t1/2 . 2

That concludes the proof of Theorem 22.5.

Exercise 22.1. Show that if Conjecture 5.26 is true, then the value of r

discovered in step 2 of Algorithm AKS satis¬es r = O(len(n)2 ).

22.3 Notes

The algorithm presented here is due to Agrawal, Kayal, and Saxena. The

paper is currently available only on the Internet [6]. The analysis in the

original version of the paper made use of a deep number-theoretic result of

Fouvry [36], but it was subsequently noticed that the algorithm can be fully

analyzed using just elementary arguments (as we have done here).

If fast algorithms for integer and polynomial arithmetic are used, then

using the analysis presented here, it is easy to see that the algorithm runs

in time O(len(n)10.5+o(1) ). More generally, it is easy to see that the algo-

rithm runs in time O(r1.5+o(1) len(n)3+o(1) ), where r is the value determined

in step 2 of the algorithm. In our analysis of the algorithm, we were able

to obtain the bound r = O(len(n)5 ), leading to the running-time bound

O(len(n)10.5+o(1) ). Using Fouvry™s result, one can show that r = O(len(n)3 ),

leading to a running-time bound of O(len(n)7.5+o(1) ). Moreover, if Conjec-

ture 5.26 on the density of Sophie Germain primes is true, then one could

show that r = O(len(n)2 ) (see Exercise 22.1), which would lead to a running-

time bound of O(len(n)6+o(1) ).

Prior to this algorithm, the fastest deterministic, rigorously proved pri-

mality test was one introduced by Adleman, Pomerance, and Rumely [5],

called the Jacobi sum test, which runs in time

O(len(n)c len(len(len(n))) )

for some constant c. Note that for numbers n with less than 2256 bits, the

value of len(len(len(n))) is at most 8, and so this algorithm runs in time

O(len(n)8c ) for any n that one could ever actually write down.

We also mention the earlier work of Adleman and Huang [3], who gave a

probabilistic algorithm whose output is always correct, and which runs in

expected polynomial time (i.e., a Las Vegas algorithm, in the parlance of

§7.2).

Appendix: Some useful facts

A1. Some handy inequalities. The following inequalities involving expo-

nentials and logarithms are very handy.

(i) For all real x, we have

1 + x ¤ ex ,

or, taking logarithms,

log(1 + x) ¤ x.

(ii) For all real x ≥ 0, we have

e’x ¤ 1 ’ x + x2 /2,

or, taking logarithms,

’x ¤ log(1 ’ x + x2 /2).

(iii) For all real x with 0 ¤ x ¤ 1/2, we have

2

1 ’ x ≥ e’x’x ≥ e’2x ,

or, taking logarithms,

log(1 ’ x) ≥ ’x ’ x2 ≥ ’2x.

A2. Estimating sums by integrals. Using elementary calculus, it is easy

to estimate sums over a monotone sequences in terms of a de¬nite

integral, by interpreting the integral as the area under a curve. Let

f be a real-valued function that is continuous and monotone on the

closed interval [a, b], where a and b are integers. Then we have

b b

min(f (a), f (b)) ¤ f (i) ’ f (x)dx ¤ max(f (a), f (b)).

a

i=a

501

502 Appendix: Some useful facts

A3. Integrating piece-wise continuous functions. In discussing the Rie-

b

mann integral a f (x)dx, many introductory calculus texts only dis-

cuss in any detail the case where the integrand f is continuous on

the closed interval [a, b], in which case the integral is always well de-

¬ned. However, the Riemann integral is well de¬ned for much broader

classes of functions. For our purposes in this text, it is convenient

and su¬cient to work with integrands that are piece-wise contin-

uous on [a, b], that is, there exist real numbers x0 , x1 , . . . , xk and

functions f1 , . . . , fk , such that a = x0 ¤ x1 ¤ · · · ¤ xk = b, and

for i = 1, . . . , k, the function fi is continuous on the closed interval

[xi’1 , xi ], and agrees with f on the open interval (xi’1 , xi ). In this

case, f is integrable on [a, b], and indeed

k

b xi

f (x)dx = fi (x)dx.

a xi’1

i=1

It is not hard to prove this equality, using the basic de¬nition of the

Riemann integral; however, for our purposes, we can also just take

the value of the expression on the right-hand side as the de¬nition of

the integral on the left-hand side.

We also say that f is piece-wise continuous on [a, ∞) if for all b ≥ a,

f is piece-wise continuous on [a, b]. In this case, we may de¬ne the

∞ b

improper integral a f (x)dx as the limit, as b ’ ∞, of a f (x)dx,

provided the limit exists.

A4. In¬nite series. It is a basic fact from calculus that if an in¬nite

series ∞ xi of non-negative terms converges to a value y, then any

i=1

in¬nite series whose terms are a rearrangement of the xi converges

to the same value y.