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**

**The Idea**

The algorithm is based on a polynomial congruence test in the quotient ring R=((Z/Z_{n})[X])/(X^{r}-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} = c^{pk} + 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} ≡ (X^{p} + b^{p}) mod (X^{r}-1) holds in (Z/Z_{n})[X].

Now let b be invertible in (Z/Z_{n})[X], i.e. b∈ (Z/Z_{n})^{*},

then together with Fermats Little Theorem, the following claim holds: (X+b)^{p} ≡ (X^{p} + b) mod (X^{r}-1).

If a∈Z a member of the equivalence class [b], then ggT(a,p)=1,
and it follows:

[X+a]^{p} = [X^{p} + a mod (X^{r}-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=q^{k} 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.

**The Algorithm**

Let n ∈Ν a number with n > 1.

1.: If n = a^{b} with a, b ∈ Ν and b>1, output composite |

2.: Find the smallest r ∈Ν such that n^{k}≠1 mod r for all k ≤ 4log^{2}(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.5}log(n)⌋do:
if (X+b)^{n}≠x^{n}+b (modX^{r}-1, n) , output composite |

6.: n is prime. |

In 1 it is shown, that n is not a power of two numbers,i.e. k≠1 can be excluded, if p=q

In 3 it is tested if b is invertible in (Z/Z

For the Implementation an API has been used for calculating the polynomials efficiently.

It contains for instance square-and-multiply and binary segmentation methods

1 can be implemented with a variation of the newton method. The rest is implemented brute force.

The test for polynomial congruence (5) is crucial for efficient performance. Therefor, the AkS test is only

of interest with respect to computational complexity theory. Testing 2

efficient implementation.

** Applet AKS Test**

Quellcode:

AKSTest.java

UserInterface.java

2.4.1 Rho-Faktoring |