Primtest nach Agrawal, Kayal und Saxena [ReWa09]
Mitte 2002 veröffentlichten die indischen Wissenschaftler Manindra Agrawal, Neery Kayal und Nitin Saxena einen deterministischen
Primzahltest (also effizient im Verhältnis zur Länge der Testzahl), während vorher die Primzahltests nur indeterministisch
gewesen sind (u.a. Miller-Rabin-Test, Lucas-Test), wobei man mit einer frei wählbaren Anzahl von Versuchen die Fehlerwahrscheinlichkeit
der Aussage "Zahl p ist prim" verschwindend klein machen konnte. Dieser beschriebene Test ist noch Forschungsgegenstand, wobei der
Algorithmus noch nicht mit den schnellen o.g. Tests mithalten kann.
Mathematische Grundlagen
Der Miller-Rabin-Test für eine Zahl n verwendet Ganzzahlen modulo n (0 ... n-1) sowie den kleinen (wichtigen !) Satz von Fermat.
Grundaussage: n ist prim.
Es werden für Basen a und n-1 = 2k * e, e also ungerade berechnet:
ae = y mod p. Ist y == +-1 mod n, nimm neue Basis a oder sage prim.
Ansonsten wird y (k-1) mal modulo n quadriert. Wird dabei y == -1 mod n erzeugt, nimm neue Basis a oder sage prim,
bei y == 1 ist n zusammengesetzt, Test Ende, ursprüngliche Annahme wiederlegt.
Fermat sagt hier aus für n prim; an-1 == y = +1 mod n. Liegt am Ende also y != 1 mod n vor, dann n zusammengesetzt.
Der AKS-Algorithmus berechnet auch Exponentiationen mod n, aber statt einer Zahl werden Polynome verwendet.
Hier gilt die Formel, wenn n prim ist (Variable X):
(X + a)n == Xn + a mod n.
In dieser Form ist ein Primzahltest jedoch nicht brauchbar, da der Grad der errechneten Polynome exponentiell mit der
Größe n anwächst. Die Erweiterung für AKS ist dabei, dass modulo n und modulo einen Polynoms Q gerechnet wird:
(X + a)n == Xn + a mod (n, Q).
Damit kann man die Größe der Zwischenergebnisse reduzieren, und gleichtzeitig verschiedene Polynome nutzen, welche den
größten Grad von X beschränken. Als besonders gut haben sich Kreisteilungspolynome Xr - 1 erwiesen.
Für eine deterministische Laufzeit muss also eine Aussage gemacht werden, wie viele a bzw. Q zu verwenden sein, bis
die Aussage "n ist prim" tatsächlich erwiesen ist.
Für r gilt hierbei ([ReWa09], Kap 6.2 Satz 6.1.1):
r ist teilerfremd zu n und ordr(n) > 4 * (log n)2 und Q := Xr - 1.
Ist n keine Potenz von p, so gibt es weniger als r Polynome der Form P = X + a mit 0 <= a < p, die bei zusammengesetztem
n die obige Gleichung erfüllen.
Java-Beispielprogramm
In Java gibt es seit Version 1.1 die Klasse BigInteger, welche auch die Methode isProbablePrime(anzahl Tests) anbietet.
Mir ist nicht bekannt, wie diese intern arbeitet, es geht jedoch schnell, jedoch werden (meiner Erfahrung nach) bei einem Test
oft Quadratzahlen wie 9 oder 25 als Primzahl erkannt, was sehr störend ist.
Hier ein Beispielprogramm für Zahlen maximal 63 Bit.
Hauptprogramm AKS
Hilfsklasse für Polynomrechnungen