This site is supported by donations to The OEIS Foundation.


From OeisWiki
Jump to: navigation, search

This article page is a stub, please help by expanding it.

Primality is the quality of an integer being a prime number.

Primality testing

A primality test is a probabilistic primality test: if this test determines that a number is a probable prime, it must be highly probable to be so.

If such a test falsely determines that a number is prime, this number is called a pseudoprime for that test.

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

A primality proof is a deterministic primality test: if this test determines that a number is prime, it must be guaranteed to be so.

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."[1]

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".[2] The authors received many accolades, including the 2006 Gödel Prize and the 2006 Fulkerson Prize, for this work.

The algorithm determines whether a number is prime or composite within polynomial time.

Elliptic curve primality proving


See also