2.3.6: AKS Primzahltest

2.3.6: Der AKS Primzahltest

AKS steht f�r Agrawal,Kayal und Saxena. Auf der Arbeit dieser drei Inder beruht der AKS-Test. Er ist vor allem in der Komplexit�tstheorie von Interesse.
Der Test zeigt, dass PRIM in der Komplexit�tsklasse P liegt. PRIM bezeichnet dabei, die Fragestellung, ob eine vorgegebene Zahl eine Primzahl ist, P fasst alle Entscheidungsprobleme, die mit einem deterministischen Algorithmus in polynomieller Zeit l�sbar sind in einer Klasse zusammen.

Der Algorithmus

Die Hauptidee

Der Algorithmus beruht auf einem Vergleich von Polynomen in dem Restklassenring R=((Z/Z_n)[X])/(X^r-1).

Die Binomische Formel f�r endliche Ringe der Charakteristk p besagt:

Satz: Sei p eine Primzahl und R ein kommutativer Ring der Charakteristik p.
Dann gilt: (c+d)^{p^k} = c^{p^k} + d ^{p^k} f�r alle c,d ∈ R und alle k ∈ Ν.

In R gilt also mit k=1 und einer beliebigen Primzahl p: ([X]+[b])^p = [X]^p + [b]^p.
Und in (Z/Z_n)[X] gilt: (X+b)^p ≡ (X^p + b^p) mod (X^r-1).

Sei nun b invertierbar in (Z/Z_n)[X], also b∈ (Z/Z_n)^*,
dann folgt zusammen mit dem Satz vom Fermat: (X+b)^p ≡ (X^p + b) mod (X^r-1).

Ist jetzt a∈Z ein Repr�sentant der Restklasse [b], also ggT(a,p)=1,
dann gilt in R: [X+a]^p = [X^p + a mod (X^r-1,n)].

F�r alle Primzahlen muss diese Bedingung also gelten. Um daraus einen Primzahltest zu machen interessiert aber die Umkehrung dieses Satzes.
Man kann nun zeigen : W�hlt man nun r so, dass es bestimmte Eigenschaften hat und ist f�r dieses eine r die Polynomkongruenz f�r gen�gend
viele bs erf�llt, dann ist p eine Primzahlpotenz. Also p=q^k f�r eine Primzahl q. Mit effizienten Algorithmen kann man k≥2 ausschlie�en,
sodass k=1 und p=q sein muss. Dieses gew�hlte r wird ein AKS Zeuge genannt.

Die Formulierung

Sei n ∈Ν eine Zahl mit n > 1.

1.Schritt: If n = a^b mit a, b ∈ Ν und b>1, n zusammengesetz

2.Schritt: Suche das kleinste r ∈Ν f�r das n^k≠1 mod r f�r alle k ≤ 4log²(n).

3.Schritt: If 1<ggT(i,n)<n f�r ein i≤r, dann ist n zusammengesetzt.

4.Schritt: If n≤r, dann ist n eine Primzahl.

5.Schritt: F�r alle b=1 bis ⌊2φ^0.5log(n)⌋do: if (X+b)ⁿ≠xⁿ+b (modX^r-1, n) , dann ist n zusammengesetzt

6.Schritt: n ist Primzahl.

Bemerkung:
In Schritt 1 wird gezeigt, dass n keine echte Potenz zweier Zahlen ist,d.h. Ausschluss von k≠1, falls p=q^k.
Schritt 3 zeigt die Invertierbarkeit von b in (Z/Z_n)[X].

Implementierung und Laufzeit

Bei der Implementierung habe ich eine API f�r die Polynomberechnung verwendet.Diese stellt Methoden f�r schnelles Potenzieren (Square and Multiply)
und effiziente Multiplikation von grossen Polynomen mittels Binary Segmentation bereit. Schritt 1 kann man mit einer Variation des Newton Verfahrens
effizient implementieren. Alle weiteren Schritte werden brute force implementiert .

Geschwindigkeitsbestimmender Schritt ist der Test der Polynomkongruenz (Schritt 5). Es ist klar, dass der AkS Test bislang rein komplexit�tstheoretisch interessant
ist, da er f�r Primzahlen in der �blicherweise verwendeten Gr�ssenordnung einfach zu langsam ist. Zum Erkennen der Primzahl 2¹³-1 braucht der Test beispielsweise
schon mit compilierten Sprachen ca. 30 Minuten.

Applet AKS Test

Quellcode:
AKSTest.java
UserInterface.java

2.4.1 Rho-Faktorisierung