## You are here

Homeprimality testing

## Primary tabs

# primality testing

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.

# References

- 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

## Mathematics Subject Classification

11A41*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Comments

## Primes in P

I agree that an entry entitled "primality testing" is incomplete without some mention of "Primes in P". There is a "self contained" account of the algorithm and its complexity in the book _Primality Testing in Polynomial Time: From Randomized Algorithms to "PRIMES Is in P"_:

http://www.amazon.com/Primality-Testing-Polynomial-Time-Randomized/dp/35...

The Solovay-Strassen and Miller-Rabin tests are also discussed.

## (automatic) links

I think that linking "effective" to the "LeftAction" is nonsense ;

not only to avoid this, "effective" could be replaced by "efficient".

## Re: (automatic) links

Yes, there is an ordinarily recognized distinction between "effective" (= computable) and "efficient", and the word that is wanted here is "efficient".

Jon Awbrey