Vorlesung
Effiziente Algorithmen für den
Primzahltest
Sommersemester 2010
| Veranstalterin: |
Beate Bollig
beate.bollig uni-dortmund.de |
|
| Voraussetzung: |
Vordiplom |
| Termin: |
donnerstags 8:15-10:00 Uhr |
| Raum: |
OH 14, 304 |
Die Vorlesung beginnt am 15. Aril 2010.
Inhalt:
Der Primzahltest, d.h. der Test, ob eine natürliche Zahl eine
Primzahl ist,
ist eines der grundlegenden Probleme der Mathematik und Informatik.
Lange Zeit war nicht bekannt, ob es einen deterministischen
polynomiellen Algorithmus gibt, der den
Primzahltest entscheidet. Erst im Sommer 2002 schafften
Agrawal,
Kayal und Saxena den Durchbruch und konstruierten einen solchen
Algorithmus. Seine
Entwicklung hält man für eine der größten
Errungenschaften der Algorithmik, u.a. auch wegen der Methoden, die
seinem Entwurf zugrunde liegen.
In der Vorlesung werden zunächst die Grundlagen aus den
Gebieten Zahlentheorie und
Algebra, wie sie zum Verständnis des Algorithmus notwendig sind,
wiederholt und vertieft.
Erstaunlicherweise sind diese recht elementar. Anschließend
werden zwei bekannte effiziente randomisierte Primzahltests vorgestellt,
bevor das Hauptresultat, der
polynomielle deterministische Primzahltest, präsentiert und
analysiert wird.
Literatur:
Die Vorlesung richtet sich nach dem folgenden Lehrbuch:
Martin Dietzfelbinger (2004). Primality Testing in Polynomial
Time. Springer Verlag.
Weitere Literatur:
Für die randomisierten Primzahltests siehe auch:
Rajeev Motwani, Prabhakar Raghavan (1995). Randomized Algorithms.
Cambridge University Press.
Einen tieferen Einblick in die Zahlentheorie bietet:
Armin Leutbecher (1996). Zahlentheorie. Springer-Verlag.
Zwei unterhaltsam geschriebene Bücher zum Thema Primzahlen:
Marcus du Sautoy (2006). Die Musik der Primzahlen. dtv (Wissen)
John Derbyshire (2003). Prime obsession. Joseph Henry Press.
Prüfungsform
Fachprüfungen finden mündlich statt (2SWS, 3LP).
Die Veranstaltung gehört zum Schwerpunktgebiet 4
(Algorithmen, Komplexität und formale Modelle).
Der Erwerb eines Leistungsscheins ist durch ein mündliches Fachgespräch möglich,
die Voraussetzung ist der aktiver Besuch der Vorlesung.
Folien
Die Folien zur Vorlesung sind hier
erhältlich.
12.4.2010 - Beate
Bollig