AKS-Primzahltest

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Der AKS-Primzahltest (auch bekannt unter dem Namen Agrawal-Kayal-Saxena-Primzahltest) ist ein deterministischer Algorithmus, der für eine Zahl untersucht, ob sie prim ist oder nicht. Er wurde von den drei indischen Wissenschaftlern Manindra Agrawal, Neeraj Kayal und Nitin Saxena entdeckt und am 6. August 2002 in einer Abhandlung mit dem Titel PRIMES is in P (Das Primzahl-Problem ist in P) veröffentlicht.

Der später von Anderen verbesserte Algorithmus entscheidet, ob eine Zahl eine Primzahl oder eine zusammengesetzte Zahl ist. Er benötigt dazu nur eine polynomielle Laufzeit. AKS unterscheidet sich jedoch wesentlich von allen bisher bekannten polynomiellen Primalitäts-Beweisalgorithmen: 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 $\hbox{O}\left((\log n)^{10+\varepsilon}\right)$ (Landau-Symbol $O$ ).

[Bearbeiten] Entstehungsgeschichte

1999 arbeitete Manindra Agrawal mit seinem Doktorvater Somenath Biswas an einer probalistischen Methode, um die Gleichheit von Polynomen zu zeigen. Die Beiden erarbeiteten daraus eine Methode für einen probabilistischen Primzahltest. Die Idee die dahinter steckt, die sich später als sinnvoll herausstellt, ist folgendes Lemma:

Sei $a\in \mathbb Z, N\in \mathbb N, N>1$ und ggT(a,N)=1. Dann ist $N\in \mathbb P$ genau dann, wenn $(x+a)^N\equiv x^N+a \mod N$

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. Dadurch wurde die Idee wieder fürs erste in die Schublade zurück gesperrt.

2001 haben zwei Studenten, Rajat Bhattarcharjee und Prashant Pandey, in Ihrer Bachelorarbeit mit dem Titel Primality Testing die Idee wieder aufgenommen. Sie erweiterten die Idee, die Polynome nicht nur modulo $N$ sondern auch modulo $x r - 1$ für ein r in der Größenordnung von log N zu berechnen. Dies hat den Vorteil, dass man $(x+a)^N \ (\text{mod }x^r-1,N)$ in polynomieller Zeit berechnen kann. Nun gilt natürlich noch für eine Primzahl N, dass sie diese Kongruenz erfüllt, aber erfüllen sie nun auch Zahlen, die keine Primzahlen sind.

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

Ist $r\in \mathbb P$ kein Teiler von N und $(x+1)^N \equiv x^n+1\ (\text{mod }x^r-1,N)$ , dann ist N entweder Prim oder $N^2\equiv 1\ (\text{mod } r)$ .

2002 arbeiteten die beiden Studenten Neeraj Kayal und Nitin Saxena an Ihrer Bachelorarbeit. Sie führten die Überlegungen ihrer Vorreiter weiter. Mithilfe der Riemannschen Vermutung konnten sie den obigen Satz beweisen. In einer leichten Vorahnung nannten sie dann Ihre Bachelorarbeit: Towards a deterministic polynomial-time Primality Test.

Danach schafften sie es mit Manindra Agrawal, den Algorithmus in seine endgültige Form zu bringen. Das dann veröffentlichte Paper erfreute sich ziemlich schnell einer großen Beliebtheit. So wurde die Korrektheit innerhalb einer Woche bestätigt und die Webseite erfreute sich an über zwei Millionen Besuchern in der ersten Woche.

Die Beliebtheit dieses Papers kann man daran erklären, dass dieses Problem eines der großen der aktuellen Mathematik ist, aber so einfach nachzuvollziehen ist.

[Bearbeiten] Der Algorithmus

Im folgenden sind $N,a,b,r\in \mathbb N$ . Die Eingabe ist die Zahl N>1.

1. if  $N = a b$  for b>1 return ZUSAMMENGESETZT
2. finde das kleinste r mit  $o r (N) > 4(log N) 2$

3. if 1<ggT(a,N)<N für ein  return ZUSAMMENGESETZT
4. if  return PRIM
5. for a=1 to  do
      if 
          return ZUSAMMENGESETZT
6. return PRIM

Man sollte noch bemerken, dass $o r (N)$ die Ordnung von N modulo r und $\varphi(x)$ die Eulersche Phi-Funktion bezeichnet. Die Ordnung von N modulo r bezeichnet die kleinste Zahl k, für die $N^k \equiv 1 (\text{mod}\ r)$ gilt.

[Bearbeiten] Nach Agrawal, Kayal und Saxena

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 ihrer wissenschaftlichen Schrift On the implementation of AKS-class primality tests (Über die Implementation von Primzahltests der AKS-Klasse), die im März 2003 veröffentlicht wurde, statt vom AKS-Algorithmus von der Klasse der AKS-Algorithmen.

Der Algorithmus von Lenstra und Pomerance terminiert in $\hbox{O}\left((\log n)^{6+\varepsilon}\right)$ .

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

Man suche zuerst ein $r\in\mathbb P$ mit $r\not|(N^2-1)$ (so ein r liegt im Intervall $2,4log N$ ). Mit diesem Algorithmus erhält man eine Laufzeit von $\hbox{O}\left((\log n)^{3+\varepsilon}\right)$