The AKS primality test
------------------------
In August 2002, three Indian researchers, Manindra Agrawal, Neeraj Kayal and Nitin Saxena, published a paper describing a deterministic primality test with a running time comparable to that of the Miller–Rabin test (see below). Like the latter, it builds on Fermat's little theorem. More precisely, studying binomial coefficients shows that if a is coprime to p, then p is prime if and only if the two polynomials (X – a)*p and Xp – a, with coefficients in ? / p?, are equal—that is, if (X – a)p = Xp – a (mod p*).
A test based on this identity requires computing every coefficient of the polynomial (X – a)*p, which would take a prohibitive amount of time. To make the test practical, evaluate the identity modulo the polynomial Xr – 1; that is, test whether (X – a)p = Xp – a (mod Xr – 1, p*).
If p is prime, this identity holds for every pair (a, r); unfortunately, the converse is false. The three Indian researchers showed that, for suitable values of r, testing the identity above for a certain number of values of a was enough to determine whether or not p is prime.
-
The Miller primality test
------------------------------
Fermat's little theorem suggests one way to test whether a number p is prime: check whether *x p *–1 = 1 (mod p) with x chosen from 2, 3… p – 1. This test is easy to program and runs quickly. Unfortunately, it does not always give the correct result: if the result is "true," there is no guarantee that p is prime. For example, 341 passes the test, even though it is the product of 11 and 31. One way around this difficulty is to study the probability of obtaining the answer "true" when p is not prime. This probability is extremely low: for an integer chosen at random from the first twenty-five billion integers, the probability that the test returns "true" even though p is not prime is approximately 2 × 10–5.
A simple idea, then, is to run the test for several values of x. A priori, this reduces the probability of error. Michael Rabin (born 1931) and Gary Miller (born 1948) improved on this idea using the factorization of the polynomial X *p *–1 – 1. This yields a test of the same type, applied using an integer x. If it is repeated for k prime values of x, the test determines whether a number is prime with an error probability on the order of 1 / 4*k. This test is a priori* probabilistic, but for "small" numbers it can easily be turned into a deterministic test.
