
As we mentioned before, many of the primality proving methods are conjectured
to be polynomialtime. For example, Miller's
test is polynomial if ERH is true (and Rabin gave a version of this test
that was unconditionally randomized polynomialtime [Rabin80]). Adleman and Hang [AH1992]
modified the GoldwasserKillian algorithm [GK86]
to produce a randomized polynomial time algorithm that always produced a certificate
of primality... So it is not surprising that there exists a polynomialtime
algorithm for proving primality. But what is surprising is that in 2002
Agrawal, Kayal and Saxena [AKS2002]
found a relatively simple deterministic algorithm which relies on no
unproved assumptions. We present this algorithm below then briefly
refer to a related algorithm of Bernstein.
The key to AKS' result is another simple version of Fermat's Little Theorem:
Theorem: Suppose that a and p are relatively prime integers with p > 1. p is prime if and only if
(xa)^{p} = (x^{p}a) (mod p)
Proof. If p is prime, then p divides the binomial coefficients _{p}C_{r} for r = 1, 2, ... p1. This shows that (xa)^{p} = (x^{p}a^{p}) (mod p), and the equation above follows via Fermat's Little Theorem. On the other hand, if p > 1 is composite, then it has a prime divisor q. Let q^{k} be the greatest power of q that divides p. Then q^{k} does not divide _{p}C_{q} and is relatively prime to a^{pq}, so the coefficient of the term x^{q} on the left of the equation in the theorem is not zero, but it is on the right.
(This result was used to create a randomized polynomialtime algorithm by Agrawal and Biswas [AB1999].)
Of course in this form it is too difficult to use because there are just far too many coefficients to check. Their idea was to look at the simpler condition:
This must hold if p is prime and it is conjectured (see [BP2001, KS2002]) that if r >1 does not divide p and the above congruence holds, then either p is prime or p^{2} is 1 modulo r.
Agrawal, Kayal and Saxena managed to reformulate this into the following algorithm which they proved would run in at most O((log n)^{12}f(log log n)) time where f is a polynomial. (This means the time it takes to run the algorithm is at most a constant times the number of digits to the twelfth power times a polynomial evaluated at the log of the number of digits.)
Input: Integer n > 1
if (n is has the form a^{b} with b > 1) then
output COMPOSITE
r := 2
while (r < n) {
if (gcd(n,r) is not 1) then output COMPOSITE
if (r is prime greater than 2) then {
let q be the largest factor of r1
if (q > 4sqrt(r)log n) and
(n^{(r1)/q} is not 1 (mod r)) then break
}
r := r+1
}
for a = 1 to 2sqrt(r)log n {
if ( (xa)^{n} is not (x^{n}a)
(mod x^{r}1,n) ) then output COMPOSITE
}
output PRIME;
The proof [AKS2002] is relatively
straightforward, and perhaps the most advanced result necessary is a sieve result
required to show the necessary q exists for each composite ([F1985],
[BH1996]). (Note that the first
step, determining if the number is a perfect power, can be done in essentially
linear time [Bernstein1998b].)
AKS also showed that if Sophie
Germain primes have the expected distribution [HL23]
(and they certainly should!), then the exponent 12 in the time estimate can
be reduced to 6, bringing it much closer to the the (probabilistic) ECPP
method. But of course when actually finding primes it is the unlisted
constants^{1} that make all of the difference!
We will have to wait for efficient implementations of this algorithm (and hopefully
clever restatements of the painful for loop
) to see how it compares
to the others for integers of a few thousand digits. Until then, at least
we have learned that there is a polynomialtime algorithm for all integers that
both is deterministic and relies on no unproved conjectures!
Note: D. J. Bernstein's exposition of the AgrawalKayalSaxena theorem (mentioned above) contains improvements by many diferent researchers which reduce the constants involved in the time analysis by at least a factor of 2,000,000. This is perhaps the best source for the present state of the algorithm.
Berrizbeitia [Berrizbeitia2003] found a way to save time in AKStype primality proofs for some primes n, reducing the exponent from 6+o(1) to 4+o(1). Cheng [Cheng2003] extended Berrizbeitia's idea to more primes n, and Bernstein [Bernstein2003] extended it to all primes n. The algorithm for finding these proofs relies on some randomness, unlike the original AKS algorithm.
It seems plausible that a variant of AKS may soon compete in practice with ECPP for 'general' primality proofs. This field is in great deal of flux at this time!
Other useful links:
