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.
Read more about this topic: Primality Test
Famous quotes containing the words fast and/or tests:
“Man ... cannot learn to forget, but hangs on the past: however far or fast he runs, that chain runs with him.”
—Friedrich Nietzsche (1844–1900)
“It is not the literal past that rules us, save, possibly, in a biological sense. It is images of the past.... Each new historical era mirrors itself in the picture and active mythology of its past or of a past borrowed from other cultures. It tests its sense of identity, of regress or new achievement against that past.”
—George Steiner (b. 1929)