AKS Primality Test - Concepts

Concepts

The AKS primality test is based upon the following theorem: An integer n (≥ 2) is prime if and only if the polynomial congruence relation

holds for all integers a coprime to n (or even just for some such integer a, in particular for a = 1). Note that x is a free variable. It is never substituted by a number; instead you have to expand and compare the coefficients of the x powers.

This theorem is a generalization to polynomials of Fermat's little theorem, and can easily be proven using the binomial theorem together with the following property of the binomial coefficient:

for all if and only if n is prime.

While the relation (1) constitutes a primality test in itself, verifying it takes exponential time. Therefore, to reduce the computational complexity, AKS makes use of the related congruence

which is the same as:

for some polynomials f and g. This congruence can be checked in polynomial time with respect to the number of digits in n, because it is provable that r need only be logarithmic with respect to n. Note that all primes satisfy this relation (choosing g = 0 in (3) gives (1), which holds for n prime). However, some composite numbers also satisfy the relation. The proof of correctness for AKS consists of showing that there exists a suitably small r and suitably small set of integers A such that, if the congruence holds for all such a in A, then n must be prime.