Editing AKS primality test (section)

==Concepts==
The AKS primality test is based upon the following theorem: Given an integer <math>n\ge 2</math> and integer <math>a</math> [[coprime]] to <math>n</math>, <math>n</math> is prime if and only if the [[polynomial ring|polynomial]] [[Congruence relation#Modular arithmetic|congruence relation]]
{{NumBlk|:|<math>(X + a)^{n} \equiv X^{n} + a \pmod{n}</math>|{{EquationRef|1}}}}
holds within the polynomial ring <math>(\mathbb Z/n\mathbb Z)[X]</math>.<ref name="AKS"/> Note that <math>X</math> denotes the [[polynomial ring#Definition (univariate case)|indeterminate]] which generates this polynomial ring.

This theorem is a generalization to polynomials of [[Fermat's little theorem]].  In one direction it can easily be proven using the [[binomial theorem]] together with the following property of the [[binomial coefficient]]:
:<math>{n \choose k} \equiv 0 \pmod{n}</math> for all <math>0<k<n</math> if <math>n</math> is prime.

While the relation ({{EquationNote|1}}) constitutes a primality test in itself, verifying it takes [[exponential time]]: the [[brute force method|brute force]] approach would require the expansion of the <math> (X + a)^n</math> polynomial and a reduction <math>\pmod{n}</math> of the resulting <math>n + 1</math> coefficients.

The congruence is an equality in the [[polynomial ring]] <math>(\mathbb Z/n\mathbb Z)[X]</math>. Evaluating in a quotient ring of <math>(\mathbb Z/n\mathbb Z)[X]</math> creates an upper bound for the degree of the polynomials involved. The AKS evaluates the equality in <math>(\mathbb Z/n\mathbb Z)[X]/(X^r -1)</math>, making the [[Computational complexity theory|computational complexity]] dependent on the size of <math>r</math>. For clarity,<ref name="AKS"/> this is expressed as the congruence
{{NumBlk|:|<math>(X + a)^{n} \equiv (X^{n} + a) \pmod{X^{r}-1, n}</math>|{{EquationRef|2}}}}
which is the same as:
{{NumBlk|:|<math>(X + a)^n - (X^n + a) = (X^r - 1)g + nf</math>|{{EquationRef|3}}}}
for some polynomials <math>f</math> and <math>g</math>.

Note that all primes satisfy this relation (choosing <math>g=0</math> in ({{EquationNote|3}}) gives ({{EquationNote|1}}), which holds for <math>n</math> prime). This congruence can be checked in polynomial time when <math>r</math> is polynomial to the digits of <math>n</math>. The AKS algorithm evaluates this congruence for a large set of <math>a</math> values, whose size is polynomial to the digits of <math>n</math>. The proof of validity of the AKS algorithm shows that one can find an <math>r</math> and a set of <math>a</math> values with the above properties such that if the congruences hold then <math>n</math> is a power of a prime.<ref name="AKS"/>