Primalität liegt in P

Zur Frage, ob Zahlen prim sind oder nicht, haben indische Mathematiker einen elementaren Beweis dafür vorgelegt, dass man diese Frage mit polynomischen Aufwand beantworten kann.

In Pocket speichern vorlesen Druckansicht 302 Kommentare lesen
Lesezeit: 2 Min.
Von
  • Andreas Stiller

Die Frage, ob Zahlen prim sind oder nicht, treibt Mathematiker, Mönche und Mystiker schon seit Jahrtausenden um -- nun haben indische Mathematiker einen elementaren Beweis dafür vorgelegt, dass man diese Frage mit polynomischem Aufwand (in Bezug auf die Zahlengröße) beantworten kann. Bislang galt diese Polynomität "liegt in P" bei bestimmten Zahlenklassen (Lukas-Lehmer-Test für Mersenne-Zahlen oder Brillhart-Selfridge-Test, falls n-1 faktorisiert ist) oder unter bestimmten Annahmen (ERH Extended Riemann Hypothesis) und vor allem für Monte-Carlo-Verfahren (Miller-Rabin-Test). Letztere ermitteln die Primalität einer Zahl mit sehr hoher Wahrscheinlichkeit. Der verbleibende Unsicherheitsfaktor liegt schnell unter der Fehlerquote normaler Rechnersysteme, sodass solche Wahrscheinlichkeits-Checks eigentlich nicht schlechter dastehen als stringente, exakte Verfahren.

Die indischen Mathematiker Agrawal, Kayal und Saxena vom Indian Institute of Technology Kanpur weisen in ihrem Paper nach, dass sich der Aufwand maximal in den Grenzen von O( log(n)12) hält, praktisch kommt sogar der Algorithmus meist schon in O(log(n)6) zum Ziel. Zum Suchen nach neuen größeren Primzahlen ist das allerdings immer noch viel zu viel, hier ist der Lukas-Lehmer-Test für die Mersenne-Zahlen weitaus effizienter, mit dem eine riesige Internet-Gemeinde im GIMPS-Projekt schon seit Jahren erfolgreich nach immer größeren Mersenneschen Primzahlen sucht. Aktueller Rekord: 213466917-1.

Nebenbei bemerkt, etwas, was Einstein wohl entgangen ist: Während man sich intensiv mit Primzahlen und Zahlentheorie beschäftigt, bleibt nach primologischen Erkenntnissen die Zeit stehen. Und so wurden viele Primzahlforscher uralt, jedenfalls wenn sie sich nicht in jungen Jahren mit Duellen oder anderen Hobbys die Zeit und ihr Leben vertrieben haben. Hadamard und de la Vallée-Pousse beispielsweise, die den lange gesuchten Primzahlsatz (Zahl der Primzahlen <=n) im Jahre 1896 unabhängig voneinander bewiesen, wurden beide fast 100 Jahre alt. Bertrand Russell, einer der wohl faszinierendsten Wissenschaftler (und Philosoph und Krimi-Autor und Moralist und ...) des letzten Jahrhunderts hat die 100 ebenfalls beinahe erreicht. Euler und Gauß, die sich lange mit dem Primzahlsatz vergeblich beschäftigt hatten, kamen immerhin hoch in die Siebziger, nur Riemann, dessen Vermutung bis heute wohl die größte Herausforderung der Zahlentheorie darstellt, ist vor Verzweiflung darüber, dass er den Primzahlsatz und seine eigene Vermutung nicht beweisen konnte, leider schon vierzigjährig gestorben. (as)