Primzahlen

Primalität liegt in P

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. ...

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.

http://www.heise.de/newsticker/data/as-07.08.02-000/