WikiDer > AKS-Test

Das AKS-Test ist ein Primzahltest; eine Methode, um zu überprüfen, ob a Nummer ein zusammengesetzte Zahl oder ein Primzahl ist. Der AKS-Test ist nach seinen Schöpfern benannt: Manindra Agrawal, Neeraj Kayal und Nitin Saxena. Sie haben es veröffentlicht Algorithmus in ihrem Artikel Primzahlen ist in P.^[1]

Bald wurde ihr Ergebnis von anderen verbessert. Beschrieben im Jahr 2005 Carl Pomerance und H. W. Lenstra, Jr. eine Variante des AKS-Tests, der Ö(Log⁶nein) Betrieb muss eine nummer bekommen nein Zu testen. Dies war eindeutig eine Verbesserung gegenüber dem O(log¹²nein) im ursprünglichen Algorithmus.^[2]

Bedeutung des Tests

Das Wichtigste am AKS-Test ist, dass der Test vier Eigenschaften hat (Allgemeines, Polynom, deterministisch und ohne Annahmen) Bündel, die vorher nicht gebündelt wurden:

• Allgemein: Der Test funktioniert für alle Primzahlen. Andere Schnelltests wie der Lucas-Lehmer-Test (funktioniert nur für Mersenne-Primzahlen) oder der Pepintest (nur für Fermat-Zahlen) sind nicht für alle Primzahlen geeignet.
• Polynom: Wie wir oben gesehen haben, funktioniert der Test in Polynomzeit. Bisherige schlüssige Primzahlentests waren bekannt, dass exponentielle Zeit gearbeitet, aber nicht vorher in polynomieller Zeit.
• Deterministisch: Der Test bestimmt deterministisch, ob eine Zahl eine Primzahl ist oder nicht. Tests wie die Miller-Rabin-Primzahltest kann auch in polynomieller Zeit testen, ob eine Zahl eine Primzahl ist oder nicht, aber nur mit einer gewissen Sicherheit eine Antwort liefern (es besteht eine Wahrscheinlichkeit von 99,...%, dass nein ist eine Primzahl).
• Ohne Annahmen: Der Test basiert nicht auf noch unbewiesenem Verdächtigungen. Die deterministische Version des Miller-Rabin-Primzahltests basiert auf dem unbewiesenen Allgemeinen Riemann-Hypothese.

Theorie

Der Test basiert auf folgendem Prinzip:

${displaystyle (x-a)^{n}äquivalent (x^{n}-a){pmod {n}}qquad (1)}$

Dies ist eine Ableitung von Der kleine Satz von Fermat für Polynome und lässt sich aus dem kleinen Satz von Fermat in Kombination mit dem Newtons Binomial und die nächste Eigenschaft des Binomialkoeffizient:

${displaystyle {n wählen k}äquiv 0{pmod {n}}}$ für alle k, 0 < k < neindann und nur dann, wenn n ist eine Primzahl.

Obwohl dies selbst ein Primzahltest ist, funktioniert er in exponentieller Zeit. Deshalb wird für den AKS-Test Äquivalenz verwendet:

${displaystyle (x-a)^{n}äquivalent (x^{n}-a){pmod {n,x^{r}-1}}qquad (2)}$

was dasselbe ist wie:

${Anzeigestil (x-a)^{n}-(x^{n}-a)=nf (x^{r}-1)gqquad (3)}$

sicher Polynomef und G. Dies kann in polynomieller Zeit getestet werden. Beachten Sie, dass alle Primzahlen diese Gleichheit erfüllen (wenn wir r = 0 in (3) erhalten wir (1), was für alle Primzahlen gilt). Es gibt aber auch einige Zusammengesetzte Zahlen die dem entsprechen. Das Prinzip des AKS-Tests basiert nun auf dem r existiert, das klein genug ist mit einem assoziierten Sammlung Zahlen ein, so dass, wenn es gilt, dass die Vergleich gilt für diese kleinere Menge von Zahlen, dass die Zahl nein als eine Primzahl ist.

Der Algorithmus

Das Original^[1] Algorithmus funktioniert wie folgt:

Eingabe: eine ganze Zahl nein > 1.

1. wenn nein = ein^b, mit ganzen Zahlen ein > 0 und b > 1, Ausgang zusammengesetzt.
2. Finde die kleinste Zahl r so dass Ö_r(nein) > log²(nein).
3. Wenn 1 <gcd(ein,nein) < nein für eine gewisse ein ≤ r, Ausgabe zusammengesetzt.
4. wenn nein ≤ r, Ausgabe Ahle.
5. Vor dem ein = 1 to ${displaystyle scriptstyle lfloor scriptstyle {sqrt {varphi (r)}}log(n)scriptstyle floor }$, als

   wenn (Xein)^nein≠ X^neinein (mod X^r − 1,nein), Ausgabe zusammengesetzt.

6. Export Ahle.

Darin ist Ö_r(nein) ist die kleinste Zahl k so dass nein^k ≡ 1 (mod r) (d. h. die multiplikative Ordnung von nein modular r). Außerdem meinen wir mit log de Logarithmus mit Base 2 und ${displaystyle scriptstyle varphi(r)}$ ist der Euler-Phi-Funktion von r.

Wann nein eine Primzahl ist, wird die Ausgabe des Algorithmus immer Ahle sein: seit nein ist eine Primzahl, die Schritte 1. und 3. werden nie zusammengesetzt als Ausgabe geben. Schritt 5. wird nie zusammengesetzt Ausgabe, weil (2) für alle Primzahlen gilt nein. Daher ist die Ausgabe des Algorithmus Ahle befinden sich entweder in Schritt 4. oder in Schritt 6.

Umgekehrt, wenn nein zusammengesetzt ist, wird die Ausgabe des Algorithmus immer zusammengesetzt sind: Angenommen die Ausgabe Ahle dann erfolgt dies in Schritt 4. oder Schritt 6. Im ersten Fall, da nein ≤ r, hast nein ein Faktor ein ≤ r so dass 1 < gcd(ein,nein) < nein, was die Ausgabe in Schritt 3 verursacht. zusammengesetzt wäre gewesen. Die verbleibende Möglichkeit besteht darin, dass die Ausgabe in Schritt 6. Ahle ist. Im Originalartikel^[1] ist bewiesen, dass dies nicht passieren wird, da die in Schritt 5 getesteten Ähnlichkeiten ausreichen, um zu garantieren, dass die Ausgabe zusammengesetzt ist.

Um zu beweisen, dass der Algorithmus korrekt ist, müssen wir zwei Dinge beweisen. Zuerst, dass die r ab Schritt 2. kann immer gefunden werden^[1] und zweitens die oben beschriebenen Ansprüche. Außerdem ist der Artikel^[1] bewiesen, dass der Algorithmus funktioniert in Polynomzeit.

Externer Link

• (und) Hintergrundartikel

Verweise