AKS-Primzahltest

Grundidee und Bedeutung

Der AKS-Primzahltest, auch Agrawal-Kayal-Saxena-Primzahltest genannt, ist ein deterministischer Algorithmus. Er entscheidet für eine natürliche Zahl n, ob sie prim oder zusammengesetzt ist. Deterministisch bedeutet: Bei derselben Eingabe liefert er stets ohne Zufallsschritte dasselbe Ergebnis.

Seine besondere Bedeutung liegt darin, dass er für die Länge der Eingabe nachweisbar polynomielle Laufzeit hat und dieser Nachweis keine unbewiesenen Annahmen wie die verallgemeinerte Riemannsche Vermutung benötigt. Die asymptotische Laufzeit des ursprünglichen Verfahrens beträgt O((log n)^(7,5+ε)). Dabei ist log(n)=log₂(n), O das Landau-Symbol und ε eine beliebig kleine positive Zahl.

Entwickelt wurde der Test von Manindra Agrawal, Neeraj Kayal und Nitin Saxena. Die Schrift PRIMES is in P erschien 2002; 2006 erhielten die drei Forscher dafür den Gödel- und den Fulkerson-Preis.

Entwicklung der zentralen Polynomidee

Ausgangspunkt war eine 1999 von Manindra Agrawal und seinem Doktorvater Somenath Biswas untersuchte probabilistische Methode zum Nachweis der Gleichheit von Polynomen. Daraus ergab sich ein Primzahltest auf Grundlage des Hilfssatzes: Für a∈ℤ, n∈ℕ, n>1 und ggT(a,n)=1 ist n genau dann prim, wenn

(X+a)^n ≡ X^n+a (mod n)

gilt. X ist dabei eine Unbestimmte des Polynomrings ℤ[X]. Für eine Primzahl sind die mittleren Koeffizienten aᵢ=(n über i)a^(n-i) für 0<i<n also alle kongruent zu 0 modulo n. Der direkte Test war jedoch aufwendig, weil im schlimmsten Fall alle Koeffizienten berechnet werden mussten.

2001 schlugen Rajat Bhattarcharjee und Prashant Pandey vor, zusätzlich modulo X^r−1 zu rechnen, also modulo (X^r−1,n), wobei r in der Größenordnung von log n liegt. Dadurch lässt sich (X+a)^n modulo (X^r−1,n) in polynomieller Zeit berechnen. Die Kongruenz gilt dann zwar für Primzahlen, aber auch für manche zusammengesetzten Zahlen. Die weitere Untersuchung passender Werte für a und r führte zu einer Vermutung: Ist r prim, teilt r nicht n und gilt (X+1)^n ≡ X^n+1 (mod (X^r−1,n)), so ist n entweder prim oder n²≡1 (mod r). Kayal und Saxena bewiesen dies unter der Annahme der Riemannschen Vermutung und entwickelten anschließend mit Agrawal die endgültige Form des Tests.

Ablauf des Tests

Der Test prüft n>1 in folgenden Schritten:

• Zuerst wird geprüft, ob n=a^b für ein b>1 ist. Dann ist n zusammengesetzt.
• Danach wird das kleinste r gesucht, für das ord_r(n)>log(n)² gilt. ord_r(n) ist die kleinste positive Zahl k mit n^k≡1 (mod r).
• Für jedes a≤r wird geprüft, ob 1<ggT(a,n)<n gilt. Falls ja, ist n zusammengesetzt, denn dann wurde ein nichttrivialer gemeinsamer Teiler gefunden.
• Gilt n≤r, wird n als prim ausgegeben.
• Sonst wird für alle a von 1 bis √φ(r)·log(n) die Polynomkongruenz (X+a)^n≡X^n+a (mod (X^r−1,n)) geprüft. Bei einer Verletzung ist n zusammengesetzt; bestehen alle Prüfungen, lautet das Ergebnis prim.

φ(r), die Eulersche Phi-Funktion, zählt die zu r teilerfremden Zahlen von 1 bis r. Die Kongruenz modulo X^r−1 reduziert Potenzen von X auf die Monome X^0,X^1,…,X^(r−1). Beim Rechnen modulo (X^r−1,n) müssen sowohl die Polynomrelation durch X^r−1 als auch die Koeffizienten modulo n berücksichtigt werden. Nach den Polynomprüfungen folgt zunächst nur, dass n eine Primzahlpotenz ist; zusammen mit dem ersten Schritt folgt daraus, dass n prim ist.

Laufzeit und spätere Varianten

Der Algorithmus arbeitet faktisch im endlichen Ring ((ℤ/(n))[X])/(X^r−1), der n·r Elemente besitzt. Wegen der Reduktion modulo n haben die dabei auftretenden Koeffizienten höchstens log n Stellen. Die Prüfung einer einzelnen Kongruenz (X+a)^n≡X^n+a (mod (X^r−1,n)) benötigt beim wiederholten Quadrieren O(r²log³n). Mit Schneller Fourier Multiplikation beträgt der Aufwand O(rlog²n).

In den Monaten nach 2002 erschienen zahlreiche verbesserte Varianten, unter anderem von Lenstra, Pomerance, Berrizbeitia, Cheng und Bernstein. Deshalb wird auch von einer Klasse von AKS-Algorithmen gesprochen. Der Algorithmus von Lenstra und Pomerance terminiert in O((log n)^(6+ε)). In der Praxis liegt die Laufzeit des AKS-Algorithmus in ähnlichen Größenordnungen, weil r meist nur wenig größer als log²n ist.

Agrawal, Kayal und Saxena beschrieben außerdem einen verwandten Algorithmus: Man sucht zunächst ein primzahliges r mit r∤(n²−1); ein solches r liegt im Intervall [2,4log n]. Daraus ergibt sich O((log n)^(3+ε)). Ob Zahlen existieren, wie sie in der zugrunde liegenden Vermutung angenommen werden, ist bisher nicht bekannt; Lenstra und Pomerance gaben eine Heuristik zum Finden möglicher Gegenbeispiele an.