Primality testing is the evaluation of an integer to determine its primality, to see whether it is prime or composite without actually factoring it. Primality testing is often accomplished using congruences, such as from Fermat's little theorem, but there are also other methods.

With small numbers, it is practical to use integer factorization to determine primality; this is not the case for larger numbers with a large least prime factor. For larger numbers, such as most Mersenne numbers, there are special primality tests which in the case of a composite input return only False without giving any idea as to any of the factors. In the case of the Mersenne numbers, the Lucas-Lehmer primality test is quite effective. For numbers of no particular special form, sophisticated elliptic curve tests can be used.

For practical purposes, primality testing might further have to be limited to answering whether a given number is a probable prime which could turn out to be a pseudoprime to a given base with further testing. In Mathematica, the primality function is PrimeQ[n], which uses the strong Miller-Rabin primality test, which is thought to be infallible even for large numbers which Mathematica would not be able to factor.

In 2002, Agrawal, Kayal and Saxena published an algorithm they claim performs primality testing in polynomial time. Soon after mathematicians such as Carl Pomerance looked at the Agrawal, Kayal and Saxena paper and said it appears to be correct. By 2004, their paper was accepted as correct, confirming the long-held belief that primality testing is a P-problem.

Bibliography

1

Manindra Agrawal, Neeraj Kayal & Nitin Saxena, ``PRIMES is in P'', Annals of Math. 160 (2004): 781 – 793

2

Eric Weisstein, ``Primality Testing Is Easy'' MathWorld News, August 7, 2002