Primality Test - Fast Deterministic Tests

Fast Deterministic Tests

Near the beginning of the 20th century, it was shown that a result of Fermat's little theorem could be used to test for primality. This resulted in the Pocklington primality test. However, as this test requires a partial factorization of n − 1 the running time was still quite slow in the worst case. The first deterministic primality test significantly faster than the naïve methods was the cyclotomy test; its runtime can be proven to be O((log n)c log log log n), where n is the number to test for primality and c is a constant independent of n. Many further improvements were made, but none could be proven to have polynomial running time. (Note that running time is measured in terms of the size of the input, which in this case is ~ log n, that being the number of bits needed to represent the number n.) The elliptic curve primality test can be proven to run in O((log n)6), but only if some still unproven (but widely assumed to be true) statements of analytic number theory are used. Similarly, under the generalized Riemann hypothesis, the Miller–Rabin test can be turned into a deterministic version (called Miller's test) with runtime Õ((log n)4). In practice, this algorithm is slower than the other two for sizes of numbers that can be dealt with at all. Because the implementation of these methods is rather difficult and creates a risk of programming errors, the slower but simpler tests are often preferred.

In 2002 the first provably polynomial time test for primality was invented by Manindra Agrawal, Neeraj Kayal and Nitin Saxena. The AKS primality test, runs in Õ((log n)12) (improved to Õ((log n)7.5) in the published revision of their paper), which can be further reduced to Õ((log n)6) if the Sophie Germain conjecture is true. Subsequently, Lenstra and Pomerance presented a version of the test which runs in time Õ((log n)6) unconditionally.