Die Wurzel (Zur Übersicht)



www.wurzel.org



Zeitschrift   Werkstatt   Service   Verein   Hilfe  

Zeitschrift für Mathematik

Übersicht Inhalt Kontakt 


Neuigkeit: Primzahlprüfung in Polynomialzeit

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 ¬≡ xna 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 > Zeitschrift

Anfang
Bücher von amazon.de

Übersicht  Zeitschrift  Werkstatt  Service  Verein  Hilfe
eMail  Kontakt zur Wurzel   Feedback zur Website


© 1996-2017 Wurzel e.V. Alle Rechte vorbehalten.