Vorlesung
Effiziente Algorithmen für den
Primzahltest
Sommersemester 2009
| Veranstalterin: |
Beate Bollig
beate.bollig uni-dortmund.de |
|
| Voraussetzung: |
Vordiplom |
| Termin: |
donnerstags 8:15-9:45 Uhr |
| Raum: |
OH 14, 304 |
Inhalt:
Der Primzahltest, d.h. der Test, ob eine natürliche Zahl eine
Primzahl ist,
ist eines der grundlegenden Probleme der Mathematik und Informatik.
Darüber hinaus gehört er zu den wichtigen algorithmischen
Aufgaben mit großer praktischer Bedeutung.
Das bekannteste Public-Key Kryptosystem, das RSA-System, verwendet
große zufällige Primzahlen, um die Kryptanalyse zu
erschweren. Hierfür generiert man eine zufällige ungerade
Zahl aus einem vorgegebenen Bereich und führt den Primzahltest
durch.
Lange Zeit war nicht bekannt, ob es einen polynomiellen Algorithmus
gibt, der den
Primzahltest deterministisch 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,
erarbeitet.
Diese sind erstaunlicherweise recht elementar. Anschließend
werden zwei (praktisch)
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.
Für die randomisierten Primzahltests siehe auch:
Juraj Hromkovic (2004). Randomisierte Algorithmen. Teubner Verlag.
Rajeev Motwani, Prabhakar Raghavan (1995). Randomized Algorithms.
Cambridge University Press.
Einen tieferen Einblick in die Zahlentheorie bietet:
Armin Leutbecher (1996). Zahlentheorie. Springer-Verlag.
Inhalt der Vorlesung
- 16.4.2009: God may not play dice with the universe but something
strange is going on with the prime numbers. (Paul Erdös)
- 23.4.2009: Test auf perfekte Potenz,
Grundlagen aus der Zahlentheorie
- 30.4.2009: Chinesischer Restklassensatz, Analyse Sieb des Eratosthenes,
Dichte von Primzahlen
- 7.5.2009: Grundlagen aus der Algebra: Eigenschaften zyklischer Gruppen
- 14.5.2009: Fortsetzung Eigenschaften zyklischer Gruppen,
Fermat-Test mit Analyse, (nicht)triviale Quadratwurzeln von 1 modulo n
- 28.5.2009: Miller-Rabin-Test mit Analyse, Quadratische Reste
- 4.6.2009: Berechnung des Jacobi Symbols, Solovy-Strassen-Test mit Analyse
- 18.6.2009: Polynomringe
- 25.6.2009: Ausblick AKS-Algorithmus, Restklassenpolynome
- 2.7.2009: AKS-Algorithmus mit Laufzeitanalyse
- 9.7.2009: Korrektheit AKS-Algorithmus
Folien
Die Folien zur Vorlesung sind hier
erhältlich.
9.7.2009 - Beate
Bollig