Aprimality test is analgorithm for determining whether an input number isprime. Among other fields ofmathematics, it is used forcryptography. Unlikeinteger factorization, primality tests do not generally giveprime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy (itsrunning time ispolynomial in the size of the input). Some primality tests prove that a number is prime, while others likeMiller–Rabin prove that a number iscomposite. Therefore, the latter might more accurately be calledcompositeness tests instead of primality tests.
The simplest primality test istrial division: given an input number,, check whether it isdivisible by anyprime number between 2 and (i.e., whether the division leaves noremainder). If so, then iscomposite. Otherwise, it is prime.[1] For any divisor, there must be another divisor, and a prime divisor of, and therefore looking for prime divisors at most is sufficient.
For example, consider the number 100, whose divisors are these numbers:
When all possible divisors up to are tested, some divisors will be discoveredtwice. To observe this, consider the list of divisor pairs of 100:
Products past are the reverse of products that appeared earlier. For example, and are the reverse of each other. Further, that of the two divisors, and. This observation generalizes to all: all divisor pairs of contain a divisor less than or equal to, so the algorithm need only search for divisors less than or equal to to guarantee detection of all divisor pairs.[1]
Also, 2 is a prime dividing 100, which immediately proves that 100 is not prime. Every positive integer except 1 is divisible by at least one prime number by theFundamental Theorem of Arithmetic. Therefore the algorithm need only search forprime divisors less than or equal to.
For another example, consider how this algorithm determines the primality of 17. One has, and the only primes are 2 and 3. Neither divides 17, proving that 17 is prime. For a last example, consider 221. One has, and the primes are 2, 3, 5, 7, 11, and 13. Upon checking each, one discovers that, proving that 221 is not prime.
In cases where it is not feasible to compute the list of primes, it is also possible to simply (and slowly) check all numbers between and for divisors. A simple improvement is to test divisibility by 2 and by just the odd numbers between 3 and, since divisibility by an even number implies divisibility by 2.
This method can be improved further. Observe that all primes greater than 5 are of the form for a nonnegative integer and. Indeed, every integer is of the form for a positive integer and. Since 2 divides, and, and 3 divides and, the only possible remainders mod 6 for a prime greater than 3 are 1 and 5. So, a more efficient primality test for is to test whether is divisible by 2 or 3, then to check through all numbers of the form and which are. This is almost three times as fast as testing all numbers up to.
Generalizing further, all primes greater than (c primorial) are of the form for positive integers,, andcoprime to. For example, consider. All integers are of the form for integers with. Now, 2 divides, 3 divides, and 5 divides. Thus all prime numbers greater than 30 are of the form for. Of course, not all numbers of the form with coprime to are prime. For example, is not prime, even though 17 is coprime to.
As grows, the fraction of coprime remainders to remainders decreases, and so the time to test decreases (though it still necessary to check for divisibility by all primes that are less than). Observations analogous to the preceding can be appliedrecursively, giving theSieve of Eratosthenes.
One 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, such as all primes up to 200. (Such a list can be computed with the Sieve of Eratosthenes or by an algorithm that tests each incremental against all known primes). Then, before testing for primality with a large-scale method, can first be checked for divisibility by any prime from the list. If it is divisible by any of those numbers then it is composite, and any further tests can be skipped.
A simple but inefficient primality test usesWilson's theorem, which states that is prime if and only if:
Although this method requires about modular multiplications,[2] rendering it impractical, theorems about primes and modular residues form the basis of many more practical methods.
 | This sectionneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources in this section. Unsourced material may be challenged and removed.(August 2025) (Learn how and when to remove this message) |
These are tests that seem to work well in practice, but are unproven and therefore are not, technically speaking, algorithms at all.TheFermat primality test and the Fibonacci test are simple examples, and they are effective when combined.John Selfridge has conjectured that ifp is an odd number, andp ≡ ±2 (mod 5), thenp will be prime if both of the following hold:
wherefk is thek-thFibonacci number. The first condition is the Fermat primality test using base 2.
In general, ifp ≡ a (modx2+4), wherea is a quadratic non-residue (modx2+4) thenp should be prime if the following conditions hold:
f(x)k is thek-thFibonacci polynomial atx.
Selfridge,Pomerance andWagstaff together offered $620 for a counterexample or proof that there is none,[3] with the prize now due from theNumber Theory Foundation.[citation needed]
Probabilistic tests are more rigorous than heuristics in that they provide provable bounds on the probability of being fooled by a composite number.Multiple popular primality tests are probabilistic tests. These tests use, apart from the tested numbern, some other numbersa which are chosen at random from somesample space; the usual randomized primality tests never report a prime number as composite, but it is possible for a composite number to be reported as prime. The probability of error can be reduced by repeating the test with several independently chosen values ofa; for two commonly used tests, forany compositen at least half thea's detectn's compositeness, sok repetitions reduce the error probability to at most 2−k, which can be made arbitrarily small by increasingk.
The basic structure of randomized primality tests is as follows:
After one or more iterations, ifn is not found to be a composite number, then it can be declaredprobably prime.
The simplest probabilistic primality test is theFermat primality test (actually a compositeness test). It works as follows:
Ifan−1 (modulon) is 1 butn is not prime, thenn is called apseudoprime to basea. In practice, ifan−1 (modulon)is 1, thenn is usually prime. But here is a counterexample:ifn = 341 anda = 2, then
even though 341 = 11·31 is composite. In fact, 341 is the smallest pseudoprime base 2 (see Figure 1 of[4]).
There are only 21853 pseudoprimes base 2 that are less than 2.5×1010 (see page 1005 of[4]). This means that, forn up to 2.5×1010, if2n−1 (modulon) equals 1, thenn is prime, unlessn is one of these 21853 pseudoprimes.
Some composite numbers (Carmichael numbers) have the property thatan − 1 is 1 (modulon) for everya that is coprime ton. The smallest example isn = 561 = 3·11·17, for whicha560 is 1 (modulo 561) for alla coprime to 561. Nevertheless, the Fermat test is often used if a rapid screening of numbers is needed, for instance in the key generation phase of theRSA public key cryptographic algorithm.
TheMiller–Rabin primality test andSolovay–Strassen primality test are more sophisticated variants, which detect all composites (once again, this means: forevery composite numbern, at least 3/4 (Miller–Rabin) or 1/2 (Solovay–Strassen) of numbersa are witnesses of compositeness ofn). These are also compositeness tests.
The Miller–Rabin primality test works as follows:Given an integern, choose some positive integera < n. Let 2sd =n − 1, whered is odd. If
and
thenn is composite anda is a witness for the compositeness. Otherwise,n may or may not be prime.The Miller–Rabin test is astrong probable prime test (see PSW[4] page 1004).
The Solovay–Strassen primality test uses another equality: Given an odd numbern, choose some integera < n, if
thenn is composite anda is a witness for the compositeness. Otherwise,n may or may not be prime.The Solovay–Strassen test is anEuler probable prime test (see PSW[4] page 1003).
For each individual value ofa, the Solovay–Strassen test is weaker than the Miller–Rabin test. For example, ifn = 1905 anda = 2, then the Miller-Rabin test shows thatn is composite, but the Solovay–Strassen test does not. This is because 1905 is an Eulerpseudoprime base 2 but not a strong pseudoprime base 2 (this is illustrated in Figure 1 of PSW[4]).
The Miller–Rabin and the Solovay–Strassen primality tests are simple and are much faster than other general primality tests. One method of improving efficiency further in some cases is theFrobenius pseudoprimality test; a round of this test takes about three times as long as a round of Miller–Rabin, but achieves a probability bound comparable to seven rounds of Miller–Rabin.
The Frobenius test is a generalization of theLucas probable prime test.
TheBaillie–PSW primality test is a probabilistic primality test that combines a Fermat or Miller–Rabin test with aLucas probable prime test to get a primality test that has no known counterexamples. That is, there are no known compositen for which this test reports thatn is probably prime.[5][6] It has been shown that there are no counterexamples forn.
Leonard Adleman and Ming-Deh Huang presented an errorless (but expected polynomial-time) variant of theelliptic curve primality test. Unlike the other probabilistic tests, this algorithm produces aprimality certificate, and thus can be used to prove that a number is prime.[7] The algorithm is prohibitively slow in practice.
Ifquantum computers were available, primality could be testedasymptotically faster than by using classical computers. A combination ofShor's algorithm, an integer factorization method, with thePocklington primality test could solve the problem in.[8]
Near the beginning of the 20th century, it was shown that a corollary ofFermat's little theorem could be used to test for primality.[9] This resulted in thePocklington primality test.[10] However, as this test requires a partialfactorization ofn − 1 the running time was still quite slow in the worst case. The firstdeterministic primality test significantly faster than the naive methods was thecyclotomy test; its runtime can be proven to beO((log n)c log log log n), wheren is the number to test for primality andc is a constant independent ofn. A number of further improvements were made, but none could be proven to have polynomial running time. (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 numbern.) Theelliptic curve primality test can be proven to run in O((log n)6), if some conjectures onanalytic number theory are true.[which?] Similarly, under thegeneralized Riemann hypothesis (which Miller, confusingly, calls the "extended Riemann hypothesis"), the deterministicMiller's test, which forms the basis of the probabilistic Miller–Rabin test, can be proved to run inÕ((log n)4).[11] 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 two methods is rather difficult and creates a risk of programming errors, slower but simpler tests are often preferred.
In 2002, the first provably unconditional deterministic polynomial time test for primality was invented byManindra Agrawal,Neeraj Kayal, andNitin Saxena. TheAKS primality test runs in Õ((log n)12) (improved to Õ((log n)7.5)[12] in the published revision of their paper), which can be further reduced to Õ((log n)6) if theSophie Germain conjecture is true.[13] Subsequently, Lenstra and Pomerance presented a version of the test which runs in time Õ((log n)6) unconditionally.[14]
Agrawal, Kayal and Saxena suggest a variant of their algorithm which would run in Õ((log n)3) ifAgrawal's conjecture is true; however, a heuristic argument by Hendrik Lenstra and Carl Pomerance suggests that it is probably false.[12] A modified version of the Agrawal's conjecture, the Agrawal–Popovych conjecture,[15] may still be true.
Incomputational complexity theory, the formal language corresponding to the prime numbers is denoted as PRIMES. It is easy to show that PRIMES is inCo-NP: its complement COMPOSITES is inNP because one can decide compositeness by nondeterministically guessing a factor.
In 1975,Vaughan Pratt showed that there existed a certificate for primality that was checkable in polynomial time, and thus that PRIMES was inNP, and therefore in. Seeprimality certificate for details.
The subsequent discovery of the Solovay–Strassen and Miller–Rabin algorithms put PRIMES incoRP. In 1992, the Adleman–Huang algorithm[7] reduced the complexity to, which superseded Pratt's result.
TheAdleman–Pomerance–Rumely primality test from 1983 put PRIMES inQP (quasi-polynomial time), which is not known to be comparable with the classes mentioned above.
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 theAKS primality test finally settled this long-standing question and placed PRIMES inP. However, PRIMES is not known to beP-complete, and it is not known whether it lies in classes lying insideP such asNC orL. It is known that PRIMES is not inAC0.[16]
Certain number-theoretic methods exist for testing whether a number is prime, such as theLucas test andProth's test. These tests typically require factorization ofn + 1,n − 1, or a similar quantity, which means that they are not useful for general-purpose primality testing, but they are often quite powerful when the tested numbern is known to have a special form.
The Lucas test relies on the fact that themultiplicative order of a numbera modulon isn − 1 for a primen whena is aprimitive root modulo n. If we can showa is primitive forn, we can shown is prime.
