Primality is the quality of an integer being a prime number.
- 1 Primality testing
- 2 Primality proving
- 3 See also
- 4 Notes
Primality testing algorithms
Fermat primality test
The Fermat primality test is done by applying Fermat's little theorem. If this test determines that an odd number is composite, it is guaranteed to be so, otherwise the number is either a prime or a Carmichael number (if all coprime bases from 2 to are considered, otherwise a Fermat pseudoprime to all coprime bases considered.)
Miller–Rabin primality test
Solovay–Strassen primality test
Primality proving algorithms
Trial division test
- Main article page: Trial division
This is the most basic deterministic primality test. This deterministic primality test determines successively whether an integer is coprime to all primes up to . One may also consider the GCD of with the product of a group of consecutive primes to somewhat speed up the process.
Lucas-Lehmer primality test
- Main article page: Lucas-Lehmer primality test
The Lucas-Lehmer test provides a very fast way to test the primality of numbers of the form , where is prime. "This test is ideal for binary computers because the division by (in binary) can be done using rotation and addition only."
AKS primality test
The AKS primality test (also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test) is a deterministic primality-proving algorithm created and published by three Indian Institute of Technology Kanpur computer scientists, Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, on August 6, 2002, in a paper titled "PRIMES is in P". The authors received many accolades, including the 2006 Gödel Prize and the 2006 Fulkerson Prize, for this work.
Elliptic curve primality proving