of theoretical interest, a variant in [51], which uses O( 2.5 + 1+o(1) len(q))

operations in F , and space for O( 1.5 ) elements of F , has proven to be quite

practical (Exercise 21.13 develops some of these ideas; see also Shoup [92]).

22

Deterministic primality testing

For many years, despite much research in the area, there was no known

deterministic, polynomial-time algorithm for testing whether a given integer

n > 1 is a prime. However, that is no longer the case ” the breakthrough

algorithm of Agrawal, Kayal, and Saxena, or AKS algorithm for short, is just

such an algorithm. Not only is the result itself remarkable, but the algorithm

is striking in both its simplicity, and in the fact that the proof of its running

time and correctness are completely elementary (though ingenious).

We should stress at the outset that although this result is an important

theoretical result, as of yet, it has no real practical signi¬cance: probabilistic

tests, such as the Miller“Rabin test discussed in Chapter 10, are much more

e¬cient, and a practically minded person should not at all bothered by the

fact that such algorithms may in theory make a mistake with an incredibly

small probability.

22.1 The basic idea

The algorithm is based on the following fact:

Theorem 22.1. Let n > 1 be an integer. If n is prime, then for all a ∈ Zn ,

we have the following identity in the ring Zn [X]:

(X + a)n = Xn + a (22.1)

Conversely, if n is composite, then for all a ∈ Z— , the identity (22.1) does

n

not hold.

Proof. Note that

n’1

n i n’i

(X + a)n = Xn + an + aX .

i

i=1

489

490 Deterministic primality testing

If n is prime, then by Fermat™s little theorem (Theorem 2.16), we have

an = a, and by Exercise 1.12, all of the binomial coe¬cients n , for i =i

1, . . . , n ’ 1, are divisible by n, and hence their images in the ring Zn vanish.

That proves that the identity (22.1) holds when n is prime.

Conversely, suppose that n is composite and that a ∈ Z— . Consider any

n

k m, where p m.

prime factor p of n, and suppose n = p

We claim that pk n . To prove the claim, one simply observes that

p

n(n ’ 1) · · · (n ’ p + 1)

n

= ,

p p!

and the numerator of this fraction is an integer divisible by pk , but no higher

power of p, and the denominator is divisible by p, but no higher power of p.

That proves the claim.

From the claim, and the fact that a ∈ Z— , it follows that the coe¬cient of

n

n’p in (X + a)n is not zero, and hence the identity (22.1) does not hold. 2

X

Of course, Theorem 22.1 does not immediately give rise to an e¬cient

primality test, since just evaluating the left-hand side of the identity (22.1)

takes time „¦(n) in the worst case. The key observation of Agrawal, Kayal,

and Saxena is that if (22.1) holds modulo Xr ’ 1 for a suitably chosen value

of r, and for su¬ciently many a, then n must be prime. To make this idea

work, one must show that a suitable r exists that is bounded by a polynomial

in len(n), and that the number of di¬erent values of a that must be tested

is also bounded by a polynomial in len(n).

22.2 The algorithm and its analysis

The algorithm is shown in Fig. 22.1. It takes as input an integer n > 1.

A few remarks on implementation are in order:

• In step 1, we can use the algorithm for perfect-power testing discussed

in §10.5, which is a deterministic, polynomial-time algorithm.

• The search for r in step 2 can just be done by brute-force search;

likewise, the determination of the multiplicative order of [n]r ∈ Z— can

r

be done by brute force: after verifying that gcd(n, r) = 1, compute

successive powers of n modulo r until we get 1.

We want to prove that Algorithm AKS runs in polynomial time and is

correct. To prove that it runs in polynomial time, it clearly su¬ces to

prove that there exists an integer r satisfying the condition in step 2 that

is bounded by a polynomial in len(n), since all other computations can be

22.2 The algorithm and its analysis 491

if n is of the form ab for integers a > 1 and b > 1 then

1.

return false

2. ¬nd the smallest integer r > 1 such that either

gcd(n, r) > 1

or

gcd(n, r) = 1 and

[n]r ∈ Z— has multiplicative order > 4 len(n)2

r

3. if r = n then return true

4. if gcd(n, r) > 1 then return false

for j ← 1 to 2 len(n) r1/2 + 1 do

5.

if (X + j)n ≡ Xn + j (mod Xr ’ 1) in the ring Zn [X] then

return false

6. return true

Fig. 22.1. Algorithm AKS

carried out in time (r + len(n))O(1) . Correctness means that it outputs true

if and only if n is prime.

22.2.1 Running time analysis

The question of the running time of Algorithm AKS is settled by the fol-

lowing fact:

Theorem 22.2. For integers n > 1 and m ≥ 1, the least prime r such

that r n and the multiplicative order of [n]r ∈ Z— is greater than m is

r

2 len(n)).

O(m

Proof. Call a prime r “good” if r n and the multiplicative order of [n]r ∈ Z—

r

is greater than m, and otherwise call r “bad.” If r is bad, then either r | n

or r | (nd ’ 1) for some d = 1, . . . , m. Thus, any bad prime r satis¬es

m

(nd ’ 1).

r|n

d=1

If all primes r up to some given bound x ≥ 2 are bad, then the product of

all primes up to x divides n m (nd ’ 1), and so in particular,

d=1

m

(nd ’ 1),

r¤n

r¤x d=1

492 Deterministic primality testing

where the ¬rst product is over all primes r up to x. Taking logarithms, we

obtain

m m

d

log r ¤ log n (n ’ 1) ¤ (log n) 1 + d