AKS is an acronym for the names of the three Indian computer scientists who developed this primality test: Agrawal,Kayal and Saxena
It is a deterministic primality-proving algorithm which runs in polynomial time.
The algorithm is based on a polynomial congruence test in the quotient ring R=((Z/Zn)[X])/(Xr-1).
The binomial theorem for finite rings of characteristic p claims:
Theorem: Let p be prim and R a commutative ring of characteristic p.
Then (c+d)pk = cpk + d pk holds for all c,d ∈ R and all k ∈ Ν.
Therefor in R ([X]+[b])p = [X]p + [b]p holds for k=1 and any prime number p.
And (X+b)p ≡ (Xp + bp) mod (Xr-1) holds in (Z/Zn)[X].
Now let b be invertible in (Z/Zn)[X], i.e. b∈ (Z/Zn)*,
then together with Fermats Little Theorem, the following claim holds: (X+b)p ≡ (Xp + b) mod (Xr-1).
If a∈Z a member of the equivalence class [b], then ggT(a,p)=1, and it follows:
[X+a]p = [Xp + a mod (Xr-1,n)] holds in R.
This claim holds for all prime numbers. To develop a primality test, it is of interest if this claim also holds in the opposite direction.
It can be shown : If r is chosen properly and the polynomial congruence holds for a sufficient number of bs, it follows: p is a power
of a prime number,i.e. p=qk for some prime number q. k≥2 can be excluded efficiently, therefor k=1 and p=q. The chosen r is called
a AKS witness.
Let n ∈Ν a number with n > 1.
|1.: If n = ab with a, b ∈ Ν and b>1, output composite|
|2.: Find the smallest r ∈Ν such that nk≠1 mod r for all k ≤ 4log2(n).|
|3.: If 1<ggT(i,n)<n for some i≤r, output composite|
|4.: If n≤r, output prime|
|5.: For b=1 to ⌊2φ0.5log(n)⌋do: if (X+b)n≠xn+b (modXr-1, n) , output composite|
|6.: n is prime.|
Applet AKS Test