AN EXPOSITION OF THE AGRAWAL-KAYAL-SAXENA PRIMALITY-PROVING THEOREM

DANIEL J. BERNSTEIN

Theorem 1 (Manindra Agrawal, Neeraj Kayal, Nitin Saxena). Let n be a positive integer. Let q and r be prime numbers. Let S be a finite set of integers. Assume that q divides r − 1; that n^{(r−1)/q} mod r ∉ {0, 1}; that gcd {n, b − b′} = 1 for all distinct b, b′ ∈ S; that \binom{q+#S−1}{#S} ≥ n^{2⌊\sqrt{r}⌋}; and that (x + b)^{n} = x^{n} + b in the ring (Z/n)[x]/(x^{r} − 1) for all b ∈ S. Then n is a power of a prime.

Proof. Find a prime divisor p of n such that p^{(r−1)/q} mod r ∉ {0, 1}. (If every prime divisor p of n has p^{(r−1)/q} mod r ∈ {0, 1} then n^{(r−1)/q} mod r ∈ {0, 1}.)

By hypothesis, (x + b)^{n} = x^{n} + b in F_{p}[x]/(x^{r} − 1) for all b ∈ S. Substitute x^{n^{i}} for x: (x^{n^{i}} + b)^{n} = x^{n^{i+1}} + b in F_{p}[x]/(x^{n^{i}r} − 1), hence in F_{p}[x]/(x^{r} − 1). By induction, (x + b)^{n^{i}} = x^{n^{i}} + b in F_{p}[x]/(x^{r} − 1) for all i ≥ 0. By Fermat’s little theorem, (x + b)^{n^{i}p^{j}} = (x^{n^{i}} + b)^{p^{j}} = x^{n^{i}p^{j}} + b in F_{p}[x]/(x^{r} − 1) for all j ≥ 0.

Consider the products n^{i}p^{j} with 0 ≤ i ≤ ⌊\sqrt{r}⌋ and 0 ≤ j ≤ ⌊\sqrt{r}⌋. Note for future reference that n^{i}p^{j} ≤ n^{2⌊\sqrt{r}⌋}. There are (⌊\sqrt{r}⌋ + 1)^{2} > r pairs (i, j) here, so there are distinct pairs (i, j), (k, ℓ) such that n^{i}p^{j} ≡ n^{k}p^{ℓ} (mod r). Write t = n^{i}p^{j} and u = n^{k}p^{ℓ}. Then x^{t} = x^{u} in F_{p}[x]/(x^{r} − 1), so (x + b)^{t} = x^{t} + b = x^{u} + b = (x + b)^{u} in F_{p}[x]/(x^{r} − 1) for all b ∈ S.

Find an irreducible polynomial h in F_{p}[x] dividing (x^{r} − 1)/(x − 1). A standard fact about cyclotomic polynomials is that deg h is the order of p modulo r; so deg h is a multiple of q; so deg h ≥ q.

Now (x + b)^{t} = (x + b)^{u} in the finite field F_{p}[x]/h for all b ∈ S. Note that x + b ∈ (F_{p}[x]/h)^{∗}, since deg h ≥ q ≥ 2. Define G as the subgroup of (F_{p}[x]/h)^{∗} generated by {x + b : b ∈ S}; then g^{t} = g^{u} for all g ∈ G.

G has at least \binom{q+#S−1}{#S} elements: specifically, all products ∏_{b∈S}(x + b)^{e_{b}} with ∑_{b} e_{b} ≤ q − 1. (The irreducibles x + b are distinct in F_{p}[x], because each difference (x+b)−(x+b′) = b−b′ is coprime to n by hypothesis; so these products ∏_{b}(x+b)^{e_{b}} are distinct in F_{p}[x]. These products have degree smaller than q, hence smaller than deg h, so they remain distinct modulo h.)

G is a finite multiplicative subgroup of a field, so it has an element g of order #G. But |t − u| ≤ n^{2⌊\sqrt{r}⌋} ≤ \binom{q+#S−1}{#S} ≤ #G, and g^{t} = g^{u}, so t = u. In other words, n^{i}p^{j} = n^{k}p^{ℓ}. If i = k then p^{j} = p^{ℓ} so (i, j) = (k, ℓ), contradiction. Consequently n is a power of p. □

Date: 20020820.

1991 Mathematics Subject Classification. Primary 11Y16.

Theorem 2 (Manindra Agrawal, Neeraj Kayal, Nitin Saxena, Hendrik W. Lenstra, Jr.). Let n and r be positive integers. Let S be a finite set of integers. Assume that n is a primitive root modulo r; that gcd {n, b − b′} = 1 for all distinct b, b′ ∈ S; that \binom{φ(r)+#S−1}{#S} ≥ n^{⌊^{\sqrt{r}}⌋}; and that (x + b)^{n} = x^{n} + b in the ring (Z/n)[x]/(x^{r} − 1) for all b ∈ S. Then n is a power of a prime.

Proof. If n = 1 then n is a power of a prime, so assume that n ≥ 2. Let p be a prime divisor of n. Note for future reference that φ(r) > 1. (Otherwise n ≤ n^{⌊^{\sqrt{r}}⌋} ≤ \binom{φ(r)+#S−1}{#S} = \binom{#S}{#S} = 1, contradiction.)

By hypothesis, (x + b)^{n} = x^{n} + b in F_{p}[x]/(x^{r} − 1) for all b ∈ S. Substitute x^{n^{i}} for x: (x^{n^{i}} + b)^{n} = x^{n^{i+1}} + b in F_{p}[x]/(x^{n^{i}r} − 1), hence in F_{p}[x]/(x^{r} − 1). By induction, (x + b)^{n^{i}} = x^{n^{i}} + b in F_{p}[x]/(x^{r} − 1) for all i ≥ 0. By Fermat’s little theorem, (x + b)^{n^{i}p^{j}} = (x^{n^{i}} + b)^{p^{j}} = x^{n^{i}p^{j}} + b in F_{p}[x]/(x^{r} − 1) for all j ≥ 0.

Consider the products n^{i}p^{j} with 0 ≤ i ≤ ⌊\sqrt{r}⌋ and ⌊\sqrt{r}⌋ ≤ i + j ≤ 2 ⌊\sqrt{r}⌋. Note for future reference that n^{i}p^{j}/p^{⌊^{\sqrt{r}}⌋} is an integer with n^{i}p^{j}/p^{⌊^{\sqrt{r}}⌋} ≤ n^{⌊^{\sqrt{r}}⌋}. There are (⌊\sqrt{r}⌋ + 1)^{2} > r pairs (i, j) here, so there are distinct pairs (i, j), (k, ℓ) such that n^{i}p^{j} ≡ n^{k}p^{ℓ} (mod r). Write t = n^{i}p^{j}/p^{⌊^{\sqrt{r}}⌋} and u = n^{k}p^{ℓ}/p^{⌊^{\sqrt{r}}⌋}. Then (x + b)^{tp^{^{⌊}^{\sqrt{r}}^{⌋}}} = x^{tp^{^{⌊}^{\sqrt{r}}^{⌋}}} + b = x^{up^{^{⌊}^{\sqrt{r}}^{⌋}}} + b = (x + b)^{up^{^{⌊}^{\sqrt{r}}^{⌋}}} in F_{p}[x]/(x^{r} − 1) for all b ∈ S.

Find an irreducible polynomial h in F_{p}[x] dividing the rth cyclotomic polynomial Φ_{r}. Observe that any polynomial g ∈ F_{p}[x] such that g(x^{n^{a}}) = 0 in F_{p}[x]/h for all a ≥ 0 must be divisible by Φ_{r}. (If c ∈ {0, 1, …, r − 1} and gcd {r, c} = 1 then, by hypothesis, c ≡ n^{a} (mod r) for some a, so g(y^{c}) = g(y^{n^{a}}) in F_{p}[y]/(y^{r} − 1), so g(y^{c}) = 0 in the field F_{p}[y]/h(y). The powers y^{c} are distinct in F_{p}[y]/h(y), so g is divisible by ∏_{c}(x − y^{c}) = Φ_{r} in (F_{p}[y]/h(y))[x], hence in F_{p}[x].)

Note that x+b ∈ (F_{p}[x]/h)^{∗}. (If x+b = 0 in F_{p}[x]/h then x^{n^{a}} +b = (x+b)^{n^{a}} = 0 in F_{p}[x]/h for all a, so Φ_{r} divides x + b; but deg Φ(r) = φ(r) > 1.)

Define G as the subgroup of (F_{p}[x]/h)^{∗} generated by {x + b : b ∈ S}. Then g^{tp^{^{⌊}^{\sqrt{r}}^{⌋}}} = g^{up^{^{⌊}^{\sqrt{r}}^{⌋}}} for all g ∈ G; pth powering is invertible in F_{p}[x]/h, so g^{t} = g^{u}.

G has at least \binom{φ(r)+#S−1}{#S} elements: specifically, all products ∏_{b∈S}(x + b)^{e_{b}} with ∑_{b} e_{b} ≤ φ(r) − 1. (The irreducibles x + b are distinct in F_{p}[x], because each difference (x + b) − (x + b′) = b − b′ is coprime to n by hypothesis; so these products ∏_{b}(x + b)^{e_{b}} are distinct in F_{p}[x]. Now assume that two products e = ∏_{b}(x + b)^{e_{b}} and f = ∏_{b}(x + b)^{f_{b}} are the same in F_{p}[x]/h. Then e^{n^{a}} = ∏_{b}(x + b)^{n^{a}e_{b}} = ∏_{b}(x^{n^{a}} + b)^{e_{b}} = e(x^{n^{a}}) in F_{p}[x]/h for all a ≥ 0; similarly f^{n^{a}} = f(x^{n^{a}}) in F_{p}[x]/h; so e(x^{n^{a}}) = f(x^{n^{a}}) in F_{p}[x]/h. Thus Φ_{r} divides e − f. Both e and f have degree smaller than φ(r) = deg Φ(r), so e = f in F_{p}[x].)

G is a finite multiplicative subgroup of a field, so it has an element g of order #G. But |t − u| ≤ n^{⌊^{\sqrt{r}}⌋} ≤ \binom{φ(r)+#S−1}{#S} ≤ #G, and g^{t} = g^{u}, so t = u. In other words, n^{i}p^{j} = n^{k}p^{ℓ}. If i = k then p^{j} = p^{ℓ} so (i, j) = (k, ℓ), contradiction. Consequently n is a power of p. □

Appendix: how the AKS algorithm works. Agrawal, Kayal, and Saxena use Theorem 1 to determine in polynomial time whether a given integer n > 1 is prime.

The idea is to find a small odd prime r such that n^{(r−1)/q} mod r ∉ {0, 1} and \binom{q+s−1}{s} ≥ n^{2⌊\sqrt{r}⌋}; here q is the largest prime divisor of r−1, and s is any moderately large integer. A theorem of Fouvry from analytic number theory implies that a suitable r exists on the scale of (log n)^{6}, with s on the scale of (log n)^{4}.

(For readers who care about ease of run-time analysis: Carl Pomerance points out that one can use a theorem of Goldfeld, older and simpler than the theorem of Fouvry, if 6 and 4 are replaced by substantially larger numbers. As an alternative, Lenstra has a generalization of Theorem 1 and Theorem 2, allowing many more r’s at some expense in speed; one can very easily prove that r and s suitable for Lenstra’s generalization exist on the scale of (log n)^{5}.)

Given such a (q, r, s), one can easily test that n has no prime divisors smaller than s, and test that (x + b)^{n} = x^{n} + b in the ring (Z/n)[x]/(x^{r} − 1) for all b ∈ S, where S = {0, 1, …, s − 1}. Any failure of the first test reveals a prime divisor of n. Any failure of the second test proves that n is composite. If both tests succeed, then n is a prime power by Theorem 1. One can easily check whether n is a square, cube, etc. to see whether n is prime.

(For readers who care about speed: A suitable r and s are conjectured to exist on the scale of (log n)^{2}, with q = (r − 1)/2. One can easily choose r and s to minimize the time spent checking the conditions (x + b)^{n} = x^{n} + b. The time is essentially linear in rs(lg n)^{2}. The minimum value of rs(lg n)^{2} is conjectured to be (0.017 … + o(1))(lg n)^{6} with Theorem 2, or (2.25 … + o(1))(lg n)^{6} with Theorem 1. In contrast, in the algorithm stated by Agrawal, Kayal, and Saxena, the value of rs(lg n)^{2} is conjectured to be (1024+o(1))(lg n)^{6}; the Agrawal-Kayal-Saxena paper imposes the unnecessarily strong conditions q ≥ 4\sqrt{r} lg n and s ≥ 2\sqrt{r} lg n.)

Department of Mathematics, Statistics, and Computer Science (M/C 249), The University of Illinois at Chicago, Chicago, IL 60607–7045

E-mail address: djb@cr.yp.to