This site is supported by donations to The OEIS Foundation.

# Primality

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.)

(...)

(...)

## 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 $\left\lfloor {\sqrt {n}}\right\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.

(...)