AKS primality test

The AKS primality test is a deterministic algorithm that decides whether an integer is prime in polynomial time using polynomial congruences derived from the binomial theorem.

Fermat's little theorem: For prime p and integer a not divisible by p, a^(p−1) is congruent to 1 modulo p. AKS replaces this familiar prime test's limited converse with a stronger polynomial identity.
Agrawal–Kayal–Saxena paper: The 2002 research paper presenting the AKS deterministic polynomial-time primality test. This paper introduced the algorithm and proved its unconditional polynomial-time bound.
Miller–Rabin primality test: A randomized primality test that uses modular exponentiation to identify composite numbers with high confidence. Miller–Rabin is usually faster in practice, but its standard form is probabilistic.
P versus NP problem: The open question of whether every problem with efficiently verifiable solutions also has efficiently findable solutions. AKS gives primality a polynomial-time algorithm without resolving this broader complexity question.
Polynomial congruence: A congruence asserting that two polynomials have the same value modulo a specified polynomial or integer. AKS tests a binomial identity modulo both an integer and a polynomial.
Manindra Agrawal: An Indian mathematician and computer scientist whose work includes the AKS primality test. Agrawal coauthored the paper that established the test.
ECPP: A practical method for producing certificates that prove large integers prime using elliptic curves. ECPP often handles large inputs more efficiently, but AKS gives a direct deterministic decision.
Complexity class P: The class of decision problems solvable by deterministic algorithms in polynomial time. AKS placed primality testing in P unconditionally.
Multiplicative order: The least positive exponent that makes a group element equal to the identity. AKS searches for a small modulus whose multiplicative order is sufficiently large.
Neeraj Kayal: An Indian computer scientist who coauthored the AKS primality test. Kayal helped develop the polynomial-congruence approach with Agrawal and Saxena.

Linked from 6 pages