Primality

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 $n$ 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 $\frac{n-1}{2}$ 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 $n$ is coprime to all primes up to $\lfloor \sqrt{n}\rfloor$. One may also consider the GCD of $n$ 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 $2^p-1$, where $p$ is prime. "This test is ideal for binary computers because the division by $2^p-1$ (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.

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

Elliptic curve primality proving

(...)

See also

• Fermat pseudoprimes
• Carmichael numbers

• Compositeness (the quality of an integer being a composite number)