primality testing

Primality testingMathworldPlanetmath 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 congruencesMathworldPlanetmathPlanetmathPlanetmathPlanetmath, 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 factorMathworldPlanetmath. 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 primeMathworldPlanetmath which could turn out to be a pseudoprimeMathworldPlanetmathPlanetmath 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 algorithmMathworldPlanetmath they claim performs primality testing in polynomial timeMathworldPlanetmath. 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.


  • 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
Title primality testing
Canonical name PrimalityTesting
Date of creation 2013-03-22 17:45:37
Last modified on 2013-03-22 17:45:37
Owner PrimeFan (13766)
Last modified by PrimeFan (13766)
Numerical id 7
Author PrimeFan (13766)
Entry type Definition
Classification msc 11A41