www.wikidata.de-de.nina.az

AKS Primzahltest Der auch bekannt unter dem Namen Agrawal Kayal Saxena Primzahltest ist ein deterministischer Algorithmu

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 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.

Entstehungsgeschichte Bearbeiten

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:

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 Algorithmus Bearbeiten

Auf Primalität zu testen 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 a ≤ r return ZUSAMMENGESETZT; 4: if n ≤ r return PRIM; 5: for a = 1 to sqrt(phi(r))*log(n) do 6: if (X+a)n ≢ Xn+a (mod (Xr−1), n) return ZUSAMMENGESETZT; 7: return PRIM;

Erläuterungen Bearbeiten

  • 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

Laufzeitverhalten Bearbeiten

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 . Bei Schneller Fourier Multiplikation ist der Aufwand in .

Nach Agrawal, Kayal und Saxena Bearbeiten

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.

Literatur Bearbeiten

  • 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.

Weblinks Bearbeiten

Einzelnachweise Bearbeiten

  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.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Der AKS Primzahltest auch bekannt unter dem Namen Agrawal Kayal Saxena Primzahltest ist ein deterministischer Algorithmus der fur eine naturliche 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 sinngemass Das Primzahl Problem gehort zur Komplexitatsklasse P veroffentlicht Fur ihre Arbeit wurden die Forscher 2006 mit dem Godel und dem Fulkerson Preis ausgezeichnet Der spater von anderen verbesserte Algorithmus unterscheidet sich wesentlich von allen vorher bekannten polynomiellen Primalitatsbeweis Algorithmen Er baut fur den Nachweis der bezogen auf die Lange der Eingangswerte polynomiellen Laufzeit auf keinen unbewiesenen Hypothesen wie beispielsweise der verallgemeinerten Riemannschen Vermutung auf Die asymptotische Laufzeit des ursprunglichen Algorithmus ist O log n 7 5 e displaystyle mathcal O left log n 7 5 varepsilon right wobei n displaystyle n die zu testende Zahl ist O displaystyle mathcal O fur das Landau Symbol und e displaystyle varepsilon fur eine beliebig kleine positive Zahl steht Inhaltsverzeichnis 1 Entstehungsgeschichte 2 Der Algorithmus 2 1 Erlauterungen 2 2 Laufzeitverhalten 3 Nach Agrawal Kayal und Saxena 4 Literatur 5 Weblinks 6 EinzelnachweiseEntstehungsgeschichte Bearbeiten1999 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 fur einen probabilistischen Primzahltest Die Idee die dahintersteckt und die sich spater als sinnvoll herausstellte ist folgender Hilfssatz Sei a Z n N n gt 1 displaystyle a in mathbb Z n in mathbb N n gt 1 nbsp und g g T a n 1 displaystyle mathrm ggT a n 1 nbsp Dann ist n displaystyle n nbsp eine Primzahl genau dann wenn X a n X n a mod n displaystyle X a n equiv X n a text mod n nbsp Dabei ist X displaystyle X nbsp eine Unbestimmte die den Polynomring Z X displaystyle mathbb Z X nbsp erzeugt Die n displaystyle n nbsp Koeffizienten a i n i a n i 0 lt i lt n displaystyle a i binom n i a n i 0 lt i lt n nbsp der X i displaystyle X i nbsp der Polynome in X displaystyle X nbsp sind demnach alle auf 0 mod n displaystyle equiv 0 text mod n nbsp zu testen bzw verbessert untereinander zu vergleichen n displaystyle n nbsp ist genau dann keine Primzahl wenn deren kleinster Teiler k displaystyle k nbsp die Ungleichung 1 lt k lt n displaystyle 1 lt k lt n nbsp erfullt dann ist aber n 1 k 1 k displaystyle textstyle binom n 1 k 1 k nbsp keine ganze Zahl und es gilt n k n 1 k 1 n k mod n displaystyle binom n k equiv binom n 1 k 1 frac n k quad text mod n nbsp Fur 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 zunachst 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 displaystyle n nbsp sondern auch modulo X r 1 displaystyle X r 1 nbsp also mod X r 1 n displaystyle text mod X r 1 n nbsp fur ein r displaystyle r nbsp in der Grossenordnung von log n displaystyle log n nbsp zu berechnen Dies hat den Vorteil dass man X a n mod X r 1 n displaystyle X a n text mod X r 1 n nbsp in polynomieller Zeit berechnen kann Nun gilt fur eine Primzahl n displaystyle n nbsp dass sie diese Kongruenz erfullt aber es erfullen sie nun auch Zahlen die keine Primzahlen sind Die beiden untersuchten diese Kongruenz fur bestimmte a displaystyle a nbsp und r displaystyle r nbsp um Bedingungen an a displaystyle a nbsp und r displaystyle r nbsp zu stellen damit diese Kongruenz nur noch fur Primzahlen gilt Sie stellten nach einer Versuchsreihe die folgende Vermutung s a Agrawal s Conjecture auf Ist r P displaystyle r in mathbb P nbsp P displaystyle mathbb P nbsp sei die Menge der Primzahlen kein Teiler von n displaystyle n nbsp und X 1 n X n 1 mod X r 1 n displaystyle X 1 n equiv X n 1 bigl text mod X r 1 n bigr nbsp dann ist n displaystyle n nbsp entweder prim oder n 2 1 mod r displaystyle n 2 equiv 1 text mod r nbsp 2002 arbeiteten die beiden Studenten Neeraj Kayal und Nitin Saxena an ihrer Bachelorarbeit Sie fuhrten die Uberlegungen 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 endgultige Form Die dann veroffentlichte Schrift erfreute sich ziemlich schnell einer grossen Beliebtheit So wurde die Korrektheit innerhalb einer Woche bestatigt und die Webseite hatte uber zwei Millionen Besucher in der ersten Woche Der Algorithmus BearbeitenAuf Primalitat zu testen 1 sei die Zahl n gt 1 displaystyle n gt 1 nbsp Ferner seien a b r displaystyle a b r nbsp naturliche Zahlen 1 if n ab fur ein b gt 1 return ZUSAMMENGESETZT 2 r min r ordr n gt log n 2 3 if 1 lt ggT a n lt n fur ein a r return ZUSAMMENGESETZT 4 if n r return PRIM 5 for a 1 to sqrt phi r log n do 6 if X a n Xn a mod Xr 1 n return ZUSAMMENGESETZT 7 return PRIM Erlauterungen Bearbeiten min M displaystyle operatorname min M nbsp findet das kleinste Element in der nach unten beschrankten Menge M displaystyle M nbsp ord r n displaystyle operatorname ord r n nbsp ist die Ordnung von n mod r displaystyle n text mod r nbsp das ist die kleinste Zahl k gt 0 displaystyle k gt 0 nbsp fur die n k 1 mod r displaystyle n k equiv 1 text mod r nbsp gilt log n log 2 n displaystyle log n log 2 n nbsp ist der Logarithmus von n displaystyle n nbsp zur Basis 2 ggT a n displaystyle operatorname ggT a n nbsp ist der grosste gemeinsame Teiler von a displaystyle a nbsp und n displaystyle n nbsp sqrt X displaystyle operatorname sqrt X nbsp berechnet die Quadratwurzel von X displaystyle X nbsp phi r f r displaystyle operatorname phi r varphi r nbsp ist die Anzahl der zu r displaystyle r nbsp teilerfremden Zahlen im Bereich von 1 bis r displaystyle r nbsp die Eulersche Phi Funktion X displaystyle X nbsp ist die Basis Unbestimmte des Polynomrings Z X displaystyle mathbb Z X nbsp Da das zweifach erzeugte Ideal X r 1 n displaystyle bigl X r 1 n bigr nbsp kein Hauptideal im Ring Z X displaystyle mathbb Z X nbsp ist ist bei mod X r 1 n displaystyle not equiv bigl text mod X r 1 n bigr nbsp die Teilbarkeit eines Polynoms sowohl durch X r 1 displaystyle X r 1 nbsp wie durch n displaystyle n nbsp zu untersuchen Das heisst die Inkongruenz u v mod X r 1 n displaystyle u not equiv v bigl text mod X r 1 n bigr nbsp ist gleichbedeutend zur Implikation u v mod X r 1 u v mod n displaystyle u equiv v bigl text mod X r 1 bigr quad implies quad u not equiv v text mod n nbsp Eigentlich erschliesst sich nach der Bejahung von r a X a n X n a mod X r 1 n displaystyle forall r forall a colon X a n equiv X n a quad bigl text mod X r 1 n bigr nbsp durch die Anweisungsfolge 5 6 in der Anweisung 7 nur dass n displaystyle n nbsp eine Primzahlpotenz ist Wegen der Anweisung 1 ist aber n displaystyle n nbsp eine Primzahl Laufzeitverhalten Bearbeiten Der Algorithmus rechnet de facto im endlichen Ring Z n X X r 1 displaystyle Bigl bigl mathbb Z n bigr X Bigr X r 1 nbsp mit n r displaystyle n cdot r nbsp Elementen Die Beachtung der Kongruenz mod X r 1 displaystyle equiv bigl text mod X r 1 bigr nbsp im Polynomring Z X displaystyle mathbb Z X nbsp reduziert die Menge der bei der Exponentiation X a n displaystyle X a n nbsp entstehenden Monome auf X 0 X 1 X r 1 displaystyle X 0 X 1 ldots X r 1 nbsp Die Beachtung der Kongruenz mod n displaystyle equiv text mod n nbsp beschrankt die Stellenzahl der dabei entstehenden Koeffizienten auf log n displaystyle log n nbsp Somit kostet die Feststellung von X a n X n a mod X r 1 n displaystyle X a n equiv X n a quad text mod X r 1 n nbsp bei wiederholtem Quadrieren O r 2 log 3 n displaystyle mathcal O r 2 log 3 n nbsp 2 Bei Schneller Fourier Multiplikation 3 ist der Aufwand in O r log 2 n displaystyle mathcal O r log 2 n nbsp Nach Agrawal Kayal und Saxena BearbeitenIn 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 Grossenordnungen verbesserten Wegen der grossen Anzahl an Varianten sprechen Crandall und Papadopoulos in ihrem Aufsatz On the implementation of AKS class primality tests dt Uber die Implementation von Primzahltests der AKS Klasse von Marz 2003 von der Klasse der AKS Algorithmen statt vom AKS Algorithmus Der Algorithmus von Lenstra und Pomerance terminiert in O log n 6 e displaystyle mathcal O left log n 6 varepsilon right nbsp Die Laufzeit des AKS Algorithmus bewegt sich in der Praxis jedoch in ahnlichen Grossenordnungen da der Parameter r displaystyle r nbsp meist wenig oberhalb von log 2 n displaystyle log 2 n nbsp gefunden werden kann Agrawal Kayal und Saxena haben mit der obigen Vermutung einen ahnlichen Algorithmus aufgestellt Man suche zuerst ein r P displaystyle r in mathbb P nbsp mit r n 2 1 displaystyle r nmid n 2 1 nbsp so ein r displaystyle r nbsp liegt im Intervall 2 4 log n displaystyle 2 4 log n nbsp Mit diesem Algorithmus erhalt man eine Laufzeit von O log n 3 e displaystyle mathcal O left log n 3 varepsilon right nbsp Lenstra und Pomerance haben zu dieser Vermutung in Remarks on Agrawal s Conjecture eine Heuristik zum Finden von moglichen Gegenbeispielen angegeben Ob es Zahlen wie die in deren Vermutung angenommenen gibt ist jedoch bisher nicht bekannt Literatur BearbeitenVolker 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 Weblinks BearbeitenM Agrawal N Kayal N Saxena PRIMES is in P PDF 195 kB Eric W Weisstein AKS Primality Test In MathWorld englisch R Crandall J Papadopoulos On the implementation of AKS class primality tests Memento vom 3 April 2003 im Internet Archive PDF 104 kB 18 Marz 2003 O Braun S Schonnenbeck Der AKS Primzahltest Vortrag 2009 Folkmar Bornemann Ein Durchbruch fur Jedermann PDF 487 kB Artikel uber den AKS Primzahltest mit Fotos der drei indischen Forscher H Lenstra C Pomerance Remarks on Agrawal s Conjecture ANDREW GRANVILLE 1 IT IS EASY TO DETERMINE WHETHER A GIVEN INTEGER IS PRIME in BULLETIN New Series OF THE AMERICAN MATHEMATICAL SOCIETY Vol 42 2004 englisch Einzelnachweise Bearbeiten Agrawal Kayal Saxena PRIMES is in P Manindra Agrawal Neeraj Kayal and Nitin Saxena PRIMES is in P D E Knuth The Art of Computer Programming Vol II Seminumerical Algorithms Addison Wesley 1998 Abgerufen von https de wikipedia org w index php title AKS Primzahltest amp oldid 209506559