AKS-Primzahltest
Der AKS Primzahltest (auch bekannt unter dem Namen Agrawal-Kayal-Saxena Primzahltest oder EN:cyclotomic AKS Test) ist ein deterministischer Algorithmus, der für eine Zahl untersucht, ob sie prim ist oder nicht. Er wurde von den drei indischen Wissenschaftlern Namens Manindra Agrawal, Neeraj Kayal and Nitin Saxena entdeckt und am 6. August 2002 in einer Abhandlung mit dem Titel "PRIMES is in P" ("Primzahlen sind in P") veröffentlicht.
Der Algorithmus, der von anderen später verbessert wurde, entscheidet, ob eine Zahl eine Primzahl oder eine zusammengesetzte Zahl ist und benötigt nur eine polynome Laufzeit.
AKS hat einen wesentlichen Unterschied zu allen bisher bekannten primitäts Beweisalgorithmen. Er benötigt keine unbewiesenen Hypothesen (so wie die Riemann Hypothese) um korrekt zu sein, und eine beweisbar polynomiale Laufzeit unabhängig von den Eingangswerten zu haben.
Die asymptotische Laufzeit des ursprünglichen Algorithmus ist (-> Landau-Symbol ()).
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.
Externe Links (alle Englisch)
- MathWorld: AKS Primality Test
- PRIMES is in P: The original scientific paper describing AKS primality test (PDF)
- R. Crandall, Apple ACG, and J. Papadopoulos (March 18, 2003): On the implementation of AKS-class primality tests (PDF)
- Article by Borneman, containing photos and information about the three Indian scientists (PDF)