Moin!
So wie es aussieht, haben ein paar Inder einen nicht-probabilistischen
Primzahltest in P gefunden.
Artikel bei Telepolis (eher naja):
http://www.telepolis.de/r4/artikel/20/20678/1.htmlArtikel "PRIMES is in P":
http://www.cse.iitk.ac.in/users/manindra/primality.psAktuelle Publikation wohl in Annals of Mathematics, Band 160 (2005),
S. 781.
Ganz so neu ist das alles nicht mehr:
Matthias Jantzen stellte im TGI-Oberseminar am 22. April 2003
dieses Ergebnis vor (aus der Ankündigung):
Im Vortrag werden die wesentlichen Schritte des Beweises vorgestellt
und auf das Umfeld eingegangen, in dem dieser epochale Beweis
von zwei nicht promovierten Studenten mit Bachelor–Abschluss und
Dr. Manindra Agrawal gemeinsam entwickelt wurde.
Man beachte: Saxena und Kayal, die beiden Studenten, haben ihren Bachelor-Abschluss erst
danach, im Frühjahr 2003 gemacht!
Grundlage des Vortrags war ein Artikel der Deutschen Mathematiker Vereinigung,
in Heft 4 (2002) 14-21, der als aktualisierte Kurzfassung im Computeralgebra Rundbrief der GI-Fachgruppe im März 2003 erschien.
Am 8. August 2002 erschien ein Artikel dazu in der Times (!)
und 25.01. 2003 erschein eine verbesserte Version, die in O(m^12) arbeitet,
wobei m = log n (Länge der Darstellunfg der zu testenden Zahl n).
Das ist immer noch viel schlechter als gute probabilistische Primzahltests!
Und auf das Problem der Faktorisierung, die ja für Krypthographie wichtig ist,
hat das leider nicht viel zu tun …
Das kurz dazu ….
Ganz so neu ist das alles nicht mehr:
Matthias Jantzen stellte im TGI-Oberseminar am 22. April 2003
dieses Ergebnis vor (aus der Ankündigung):
Oh, ich erinnere mich! Danke :-)
2003 erschein eine verbesserte Version, die in O(m^12) arbeitet,
wobei m = log n (Länge der Darstellunfg der zu testenden Zahl n).
Das ist immer noch viel schlechter als gute probabilistische Primzahltests!
In der Tat, aber da er deterministisch arbeitet, kann man ihn immernoch als "letzte Sicherheit" einsetzen - d.h. probabilistisch auf eine hohe Wahrscheinlichkeit einschränken und dann hiermit überprüfen -, was ja durchaus praktisch ist.
