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.
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 [1] dafĂŒr vorgelegt, dass man diese Frage mit polynomischem Aufwand (in Bezug auf die ZahlengröĂe) beantworten kann. Bislang galt diese PolynomitĂ€t [2] "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 [3] 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 [4])
URL dieses Artikels:
https://www.heise.de/-67889
Links in diesem Artikel:
[1] http://www.cse.iitk.ac.in/primality.pdf
[2] http://web.informatik.uni-bonn.de/I/Lehre/Vorlesungen/InfoIV-01-PDF/kapitel3.pdf
[3] https://www.heise.de/news/39-Mersenne-Primzahl-entdeckt-49299.html
[4] mailto:as@ct.de
Copyright © 2002 Heise Medien