Mathematikgebäude, Hörsaal M/E 28

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 Miller–Rabin 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 AKS–Test 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 AKS–Tests gegeben und es werden neue Hypothesen besprochen.

Tee: ab 16.30 Uhr im Raum M 614

Gastdozent Prof. Dr. Oleg Bogopolski