Das Ergebnis. In [1] geben M. Agrawal,
N. Kayal und N. Saxena einen Algorithmus an, der in
polynomieller Zeit entscheidet, ob eine eingegebene Zahl eine Primzahl ist oder nicht.
“Polynomielle Zeit” bedeutet, dass die Anzahl der Schritte, die der angegebene
Algorithmus ausführt, durch ein Polynom in Abhängigkeit von der Länge
(Stellenzahl) der zu untersuchenden Zahl beschränkt ist. Die Primzahlprüfung
gehört damit aus komplexitätstheoretischer Sicht zu den
“leichten“ Entscheidungsproblemen.
Der Algorithmus. Wir verwenden die Abkürzungen
Pot = {ab: a, b ∈ N, a, b > 1},
P(n) = größter Primteiler von n, n ∈ N,
ggT(m, n) = größter gemeinsamer Teiler von m und n
und die Schreibweise f(x) ≡ g(x) mod
(h(x), p) dafür, dass zwei Polynome
f und g aus dem Körper Fp
(Körper der Restklassen modulo p) äquivalent modulo
einem dritten solchen Polynom h sind. Der Algorithmus bekommt als Eingabe eine
natürliche Zahl n > 1 und lässt sich wie folgt wiedergeben:
wenn n ∈ Pot, dann Ausgabe NEIN;
r := 1;
wiederhole
r := r + 1;
wenn r < n und ggT(r, n) ≠ 1,
dann Ausgabe NEIN;
bis r = n oder ( r prim und P( r - 1) > 4 sqrt( r) log n und
n(r-1) / P(r-1) ¬≡ 1 mod r);
*)
für a = 1 bis 2 sqrt( r)log n wiederhole
wenn (x-a)n
¬≡ xn − a mod (xr-1, n),
dann Ausgabe NEIN;
Ausgabe JA;
*) ¬≡ soll hier für 'ist nicht equivalent' stehen, da
Internet Explorer (in Version 5.5) das korrekte Zeichen ≢ leider nicht anzeigt.
Korrektheit. Mit umfassenden zahlentheoretischen Betrachtungen, die hier
nicht im Einzelnen wiedergegeben werden können, zeigen die Autoren, dass ihr Algorithmus
jede zulässige Eingabe korrekt entscheidet.
Die komplexitätstheoretischen Überlegungen, die die
polynomielle Laufzeit begründen, sind dagegen weniger anspruchsvoll, zumindest für
Leser mit Grundkenntnissen auf diesem Gebiet. Dabei waren die Autoren nach eigenen Angaben
nicht bemüht, den Grad des als Zeitschranke dienenden Polynoms möglichst niedrig
abzuschätzen. Für die Laufzeit geben sie als asymptotische obere Schranke
(log n)7,5 (ein Polynom
in der Länge der eingegebenen Zahl) an.
Sie vermuten aber, dass durch Verbesserungen am Algorithmus sowie weiteren zahlentheoretischen
Betrachtungen die obere Schranke für die Rechenzeit wesentlich gesenkt werden kann,
etwa auf kubische Zeit.
Ergänzung. Mittlerweile gibt es eine verbesserte Version der
Arbeit, in der auch der Algorithmus verändert wurde. Diese und auch die
ursprüngliche Arbeit sind auf der unter [1] angegebenen
Internetseite zu finden.
Literatur
[1]
M. Agrawal, N. Kayal, N. Saxena:
PRIMES is in P.
Indian Institute of Technology, Kanpur. Preprint vom 06. 08. 2002.
http://www.cse.iitk.ac.in/news/primality.html
Thomas Schneider, Wurzel
|
Die Wurzel
Kontakt zur Wurzel
Feedback zur Website
Datenschutz