2.3.6:AKS Primality Test

2.3.6: The AKS Primality Test

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)^{p^k} = c^{p^k} + d ^{p^k} 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²(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)ⁿ≠xⁿ+b (modX^r-1, n) , output composite

6.: n is prime.

Remark:
In 1 it is shown, that n is not a power of two numbers,i.e. k≠1 can be excluded, if p=q^k.
In 3 it is tested if b is invertible in (Z/Z_n)[X].

Implementation and Time Complexity of the Algorithm

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¹³-1 needs roughly 30 min with an
efficient implementation.

Applet AKS Test

Quellcode:
AKSTest.java
UserInterface.java

2.4.1 Rho-Faktoring