AKS-Methode

Der AKS-Primzahltest (auch bekannt unter dem Namen Agrawal-Kayal-Saxena-Primzahltest) ist ein deterministischer Algorithmus, der für eine 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 entdeckt 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.

Der später von anderen verbesserte Algorithmus unterscheidet sich wesentlich von allen vorher 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 \mathcal{O}\left((\log n)^{10+\varepsilon}\right) (Landau-Symbol \mathcal{O}), wobei n die zu testende Zahl ist.

Inhaltsverzeichnis

Entstehungsgeschichte

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 dahinter steckt und die sich später als sinnvoll herausstellte, 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. 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 N sondern auch modulo xr − 1 für ein r in der Größenordnung von logN zu berechnen. Dies hat den Vorteil, dass man (x+a)^N \ (\text{mod }x^r-1,N) in polynomieller Zeit berechnen kann. Nun gilt für eine Primzahl N, 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 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. 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 schafften sie es mit Manindra Agrawal, den Algorithmus in seine endgültige Form zu bringen. 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 Besuchern in der ersten Woche.

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

Der Algorithmus

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

1. if N = ab for b>1 return ZUSAMMENGESETZT
2. finde das kleinste r mit or(N) > 4(logN)2
3. if 1<ggT(a,N)<N für ein a\leq r return ZUSAMMENGESETZT
4. if N\leq r return PRIM
5. for a=1 to \lfloor 2\sqrt{\varphi(r)}\log N\rfloor do
      if ((x+a)^N)\neq x^N+a\ (\text{mod}\ (x^r-1,N))
          return ZUSAMMENGESETZT
6. return PRIM

Man sollte noch bemerken, dass or(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.

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 ihrem Aufsatz On the implementation of AKS-class primality tests (Ü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 \mathcal{O}\left((\log N)^{6+\varepsilon}\right).

Agrawal, Kayal und Saxena haben 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,4logN). Mit diesem Algorithmus erhält man eine Laufzeit von \mathcal{O}\left((\log n)^{3+\varepsilon}\right)

Weblinks


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • AKS-Primzahltest — 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… …   Deutsch Wikipedia

  • PRIMES — Als Primzahltest bezeichnet man ein mathematisches Verfahren, mit dem ermittelt wird, ob eine gegebene Zahl eine Primzahl ist oder nicht. Inhaltsverzeichnis 1 Praktische Anwendung 2 Bekannte Primzahltest Verfahren 2.1 Probedivision 2.2 Sieb des… …   Deutsch Wikipedia

  • Primzahlentest — Als Primzahltest bezeichnet man ein mathematisches Verfahren, mit dem ermittelt wird, ob eine gegebene Zahl eine Primzahl ist oder nicht. Inhaltsverzeichnis 1 Praktische Anwendung 2 Bekannte Primzahltest Verfahren 2.1 Probedivision 2.2 Sieb des… …   Deutsch Wikipedia

  • Primzahltest — Ein Primzahltest ist ein mathematisches Verfahren, um festzustellen, ob eine gegebene Zahl eine Primzahl ist oder nicht. Inhaltsverzeichnis 1 Praktische Anwendung 2 Bekannte Primzahltest Verfahren 2.1 Probedivision …   Deutsch Wikipedia

  • Agrawal-Kayal-Saxena-Primzahltest — Der AKS Primzahltest (auch bekannt unter dem Namen Agrawal Kayal Saxena Primzahltest) ist ein deterministischer Algorithmus, der für eine Zahl in polynomieller Laufzeit feststellt, ob sie prim ist oder nicht. Er wurde von den drei indischen… …   Deutsch Wikipedia

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • accès — [ aksɛ ] n. m. • fin XIIIe donner accès; lat. accessus, p. p. de accedere → accéder I ♦ 1 ♦ Possibilité d aller, de pénétrer dans (un lieu), d entrer. ⇒ abord, approche, entrée, ouverture. L accès de ce parc est interdit; une grille en interdit l …   Encyclopédie Universelle

  • Fremdsprachenunterricht — bezeichnet das Lehren und das Erlernen einer Sprache, die nicht zu der/den Muttersprache(n) gehört, in Bildungsinstitutionen oder im Privatunterricht. Inhaltsverzeichnis 1 Fremdsprachenunterricht im europaweiten Vergleich …   Deutsch Wikipedia

  • MiG-19 — Mikojan Gurewitsch MiG 19 …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”