AKS-Primzahltest

Algorithmus, der testet ob eine Zahl eine Primzahl ist

Der AKS-Primzahltest (auch bekannt unter dem Namen Agrawal-Kayal-Saxena-Primzahltest) ist ein deterministischer Algorithmus, der für eine natürliche Zahl in polynomieller Laufzeit feststellt, ob sie prim ist oder nicht. Er wurde von den drei indischen Wissenschaftlern Manindra Agrawal, Neeraj Kayal und Nitin Saxena entwickelt und 2002 in einer Abhandlung mit dem Titel PRIMES is in P (deutsch sinngemäß: Das Primzahl-Problem gehört zur Komplexitätsklasse P) veröffentlicht. Für ihre Arbeit wurden die Forscher 2006 mit dem Gödel- und dem Fulkerson-Preis ausgezeichnet.

Der später von anderen verbesserte Algorithmus unterscheidet sich wesentlich von allen vorher bekannten polynomiellen Primalitätsbeweis-Algorithmen: Er baut für den Nachweis der – bezogen auf die Länge der Eingangswerte – polynomiellen Laufzeit auf keinen unbewiesenen Hypothesen (wie beispielsweise der verallgemeinerten Riemannschen Vermutung) auf. Die asymptotische Laufzeit des ursprünglichen Algorithmus ist , wobei die zu testende Zahl ist, für das Landau-Symbol und für eine beliebig kleine positive Zahl steht.

EntstehungsgeschichteBearbeiten

1999 arbeitete Manindra Agrawal mit seinem Doktorvater Somenath Biswas an einer probabilistischen Methode, um die Gleichheit von Polynomen zu zeigen. Die beiden erarbeiteten daraus eine Methode für einen probabilistischen Primzahltest. Die Idee, die dahintersteckt und die sich später als sinnvoll herausstellte, ist folgender Hilfssatz:

Sei   und  . Dann ist   eine Primzahl genau dann, wenn  .

Dabei ist   eine Unbestimmte, die den Polynomring   erzeugt. Die   Koeffizienten   der   der Polynome in   sind demnach alle auf   zu testen bzw. (verbessert) untereinander zu vergleichen:   ist genau dann keine Primzahl, wenn deren kleinster Teiler   die Ungleichung   erfüllt; dann ist aber   keine ganze Zahl und es gilt

 .

Für den so entstandenen Primzahltest galt, dass er nicht mit den aktuellen mithalten konnte. Im schlimmsten Falle musste man alle Koeffizienten berechnen, was ziemlich aufwendig sein konnte. Deshalb wurde die Idee zunächst nicht weiter verfolgt.

2001 nahmen die Studenten Rajat Bhattarcharjee und Prashant Pandey in ihrer Bachelorarbeit Primality Testing die Idee wieder auf. Sie erweiterten die Idee, die Polynome nicht nur modulo  , sondern auch modulo   (also  ) für ein   in der Größenordnung von   zu berechnen. Dies hat den Vorteil, dass man   in polynomieller Zeit berechnen kann. Nun gilt für eine Primzahl  , dass sie diese Kongruenz erfüllt, aber es erfüllen sie nun auch Zahlen, die keine Primzahlen sind.

Die beiden untersuchten diese Kongruenz für bestimmte   und  , um Bedingungen an   und   zu stellen, damit diese Kongruenz nur noch für Primzahlen gilt. Sie stellten nach einer Versuchsreihe die folgende Vermutung (s. a. Agrawal’s Conjecture) auf:

Ist   (  sei die Menge der Primzahlen) kein Teiler von   und  , dann ist   entweder prim oder  .

2002 arbeiteten die beiden Studenten Neeraj Kayal und Nitin Saxena an ihrer Bachelorarbeit. Sie führten die Überlegungen ihrer Vorreiter weiter. Unter der Annahme, dass die Riemannsche Vermutung korrekt ist, konnten sie den obigen Satz beweisen. In einer leichten Vorahnung nannten sie dann ihre Bachelorarbeit Towards a deterministic polynomial-time Primality Test.

Danach brachten sie den Algorithmus mit Manindra Agrawal in seine endgültige Form. Die dann veröffentlichte Schrift erfreute sich ziemlich schnell einer großen Beliebtheit. So wurde die Korrektheit innerhalb einer Woche bestätigt und die Webseite hatte über zwei Millionen Besucher in der ersten Woche.

Der AlgorithmusBearbeiten

Auf Primalität zu testen[1] sei die Zahl  . Ferner seien   natürliche Zahlen.

1: if n = ab für ein b > 1 return ZUSAMMENGESETZT;
2: r = min{ r | ordr(n) > log(n)2 };
3: if 1 < ggT(a,n) < n für ein ar return ZUSAMMENGESETZT;
4: if nr return PRIM;
5: for a = 1 to sqrt(phi(r))*log(n) do
6:     if (X+a)nXn+a (mod (Xr−1), n) return ZUSAMMENGESETZT;
7: return PRIM;

ErläuterungenBearbeiten

  •   findet das kleinste Element in der (nach unten beschränkten) Menge  .
  •   ist die Ordnung von  ; das ist die kleinste Zahl  , für die   gilt.
  •   ist der Logarithmus von   zur Basis 2.
  •   ist der größte gemeinsame Teiler von   und  .
  •   berechnet die Quadratwurzel von  .
  •   ist die Anzahl der zu   teilerfremden Zahlen im Bereich von 1 bis  : die Eulersche Phi-Funktion.
  •   ist die Basis (Unbestimmte) des Polynomrings  .
  • Da das zweifach erzeugte Ideal   kein Hauptideal im Ring   ist, ist bei   die Teilbarkeit eines Polynoms sowohl durch   wie durch   zu untersuchen. Das heißt, die Inkongruenz       ist gleichbedeutend zur Implikation
     .
  • Eigentlich erschließt sich nach der Bejahung von
     
(durch die Anweisungsfolge 5, 6) in der Anweisung 7 nur, dass   eine Primzahlpotenz ist. Wegen der Anweisung 1 ist aber   eine Primzahl.

LaufzeitverhaltenBearbeiten

Der Algorithmus rechnet de facto im endlichen Ring   mit   Elementen.

Die Beachtung der Kongruenz   im Polynomring   reduziert die Menge der bei der Exponentiation   entstehenden Monome auf  . Die Beachtung der Kongruenz   beschränkt die Stellenzahl der dabei entstehenden Koeffizienten auf  

Somit kostet die Feststellung von

 

bei wiederholtem Quadrieren  .[2] Bei Schneller Fourier Multiplikation[3] ist der Aufwand in  .

Nach Agrawal, Kayal und SaxenaBearbeiten

In den folgenden Monaten nach der Entdeckung erschienen neue Varianten (Lenstra 2002, Pomerance 2002, Berrizbeitia 2003, Cheng 2003, Bernstein 2003a/b, Lenstra und Pomerance 2003), die die AKS-Geschwindigkeit um Größenordnungen verbesserten. Wegen der großen Anzahl an Varianten sprechen Crandall und Papadopoulos in ihrem Aufsatz On the implementation of AKS-class primality tests (dt.: Über die Implementation von Primzahltests der AKS-Klasse) von März 2003 von der Klasse der AKS-Algorithmen, statt vom AKS-Algorithmus.

Der Algorithmus von Lenstra und Pomerance terminiert in  . Die Laufzeit des AKS-Algorithmus bewegt sich in der Praxis jedoch in ähnlichen Größenordnungen, da der Parameter   meist wenig oberhalb von   gefunden werden kann.

Agrawal, Kayal und Saxena haben mit der obigen Vermutung einen ähnlichen Algorithmus aufgestellt:

Man suche zuerst ein   mit   (so ein   liegt im Intervall  ). Mit diesem Algorithmus erhält man eine Laufzeit von  . Lenstra und Pomerance haben zu dieser Vermutung in Remarks on Agrawal’s Conjecture eine Heuristik zum Finden von möglichen Gegenbeispielen angegeben. Ob es Zahlen wie die in deren Vermutung angenommenen gibt, ist jedoch bisher nicht bekannt.

LiteraturBearbeiten

  • Volker Diekert, Manfred Kufleitner, Gerhard Rosenberger: Diskrete algebraische Methoden: Arithmetik, Kryptographie, Automaten und Gruppen. De Gruyter, Berlin 2013, ISBN 978-3-11-031260-7.
  • Martin Dietzfelbinger: Primality testing in polynomial time. From randomized algorithms to “PRIMES is in P” (= Lecture Notes in Computer Science. Nr. 3000). Springer, Berlin 2004, ISBN 3-540-40344-2.

WeblinksBearbeiten

EinzelnachweiseBearbeiten

  1. Agrawal, Kayal, Saxena PRIMES is in P
  2. Manindra Agrawal, Neeraj Kayal and Nitin Saxena: PRIMES is in P
  3. D. E. Knuth. The Art of Computer Programming, Vol II, Seminumerical Algorithms. Addison Wesley, 1998.