However, rather than testing all m up to n − 1, it is only necessary to test m up to : if n is composite then it can be factored into two values, at least one of which must be less than or equal to .
The efficiency can also be improved by skipping all even m except 2, since if any even number divides n then 2 does. It can be improved further by observing that all primes are of the form 6k ± 1, with the only exceptions of 2 and 3. This is because all integers can be expressed as (6k + i) for some k and for i = −1, 0, 1, 2, 3, or 4; 2 divides (6k + 0), (6k + 2), (6k + 4); and 3 divides (6k + 3). So a more efficient method is to test if n is divisible by 2 or 3, then to check through all the numbers of form 6k ± 1 . This is 3 times as fast as the previous method.
Generalising further, it can be seen that all primes are of the form c#k + i for i < c# where i represents the numbers that are coprime to c#. In fact, as c → ∞ the number of values that c#k + i can take over a certain range decreases, and so the time to test n decreases. For this method, it is also necessary to check for divisibility by all primes that are less than c. Observations analogous to the preceding can be applied recursively, giving the sieve of Eratosthenes.
A good way to speed up these methods (and all the others mentioned below) is to pre-compute and store a list of all primes up to a certain bound, say all primes up to 200. (Such a list can be computed with the Sieve of Eratosthenes). Then, before testing n for primality with a serious method, n can first be checked for divisibility by any prime from the list. If it divides any of those numbers then it is composite, and any further tests can be skipped.
The basic structure of randomized primality tests is as follows:
The simplest probabilistic primality test is the Fermat primality test. It is only a heuristic test; some composite numbers (Carmichael numbers) will be declared "probably prime" no matter what witness is chosen. Nevertheless, it is sometimes used if a rapid screening of numbers is needed, for instance in the key generation phase of the RSA public key cryptographical algorithm.
The Miller-Rabin primality test and Solovay-Strassen primality test are more sophisticated variants which detect all composites (once again, this means: for every composite number n, at least 3/4 (Miller-Rabin) or 1/2 (Solovay-Strassen) of numbers a are witnesses of compositeness of n). They are often the methods of choice, as they are much faster than other general primality tests. For high confidence, the Frobenius pseudoprimality test detects at least 99.987% of composites, though its runtime is typically three times that of Solovay-Strassen or Miller-Rabin.
Leonard Adleman and Huang presented an errorless (but expected polynomial-time) variant of the elliptic curve primality test. Unlike the other probabilistic tests, this algorithm produces a certificate for primality, and thus can be used to prove that a number is prime. The algorithm is prohibitively slow in practice.
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. It is one of the most often used deterministic tests in practice.
The implementation of these two methods is rather difficult, creating a risk of programming errors; this is one reason they are not preferred.
If the generalized Riemann hypothesis is assumed, the Miller-Rabin test can be turned into a deterministic version 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.
In 2002, Manindra Agrawal, Nitin Saxena and Neeraj Kayal described a new deterministic primality test, the AKS primality test, which they proved runs in Õ((log n)12), later improved to Õ((log n)6) . In practice, this algorithm is slower than probabilistic methods.
In 1975, Vaughan Pratt showed that there existed a certificate for primality that was checkable in polynomial time, and thus that PRIMES was in NP, and therefore in NP ∩ coNP. See primality certificate for details.
The subsequent discovery of the Solovay-Strassen and Miller-Rabin algorithms put PRIMES in coRP. In 1992, the Adleman-Huang algorithm reduced the complexity to ZPP = RP ∩ coRP, which superseded Pratt's result.
Because of its tractability in practice, polynomial-time algorithms assuming the Riemann hypothesis, and other similar evidence, it was long suspected but not proven that primality could be solved in polynomial time. The existence of the AKS primality test finally settled this long-standing question and placed PRIMES in P. However, PRIMES is not known to be P-complete, and it is not known whether it lies in classes lying inside P such as L or NC.
The Lucas-Lehmer test relies on the fact that the multiplicative order of a number a modulo n is n − 1 for a prime n when a is a primitive root modulo n. If we can show a is primitive for n, we can show n is prime.