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

(...)