Veranstaltungen
Veranstaltungen der Fakultät für Mathematik
A short proof of Agrawal-Kayal-Saxena theorem: ``PRIMES is in P``, als mathkol
Termin
13.11.2006, 17:00 -
Veranstaltungsort
Mathematikgebäude, Hörsaal M/E 28
Abstract
In seinem ersten Buch Disquisitiones Arithmeticae (1801), hat C.F. Gauß
geschrieben: Das Problem des Unterscheidens von Primzahlen und zusammengesetzten
Zahlen, und das Zerlegen von großen Zahlen in ihre Primfaktoren,
ist eine der wichtigsten und interessantesten Aufgaben der Arithmetik.
Jetzt k¨onnen wir dazu sagen, dass die zwei Probleme eine zentrale Stelle nicht
nur in der algorithmischen Zahlentheorie, sondern auch in der Kryptographie
einnehmen. In dem Vortrag wird das erste Problem besprochen:
Wie kann man schnell erkennen, ob eine gegebene nat¨urliche Zahl eine Primzahl
ist?
Es gibt einen sehr schnellen MillerRabin Primzahlentest, der es ermöglicht
die Zahlen mit 10 000 Ziffern zu untersuchen. Dieser Test ist probabilistisch,
deshalb gibt er nicht immer richtige Antworten. 2002 haben die drei indischen
Mathematiker Manindra Agrawal, Neeraj Kayal und Nitin Saxena einen Artikel
PRIMES is in P veröffentlicht. Der AKSTest ist deterministisch und
polynomial. Das heißt, dass er immer richtige Antworten gibt und in einer
polynomialen Zeit läuft.
In dem Vortrag wird eine einfache Erklärung des AKSTests gegeben und es
werden neue Hypothesen besprochen.
Hinweis
Tee: ab 16.30 Uhr im Raum M 614
Vortragende(r)
Gastdozent Prof. Dr. Oleg Bogopolski