Vorlesung
Effiziente Algorithmen für den
Primzahltest
Sommersemester 2008
| Veranstalterin: |
Beate Bollig
beate.bollig uni-dortmund.de |
|
| Termin: |
donnerstags 8:15-9:45 Uhr |
| Raum: |
SR 3.04 OH 14 |
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
- 10.4.2008: God may not play dice with the universe but something
strange is going on with the prime numbers. (Paul Erdös)
- 17.4.2008: Schnelle Exponentiation mod m, Test auf perfekte Potenz,
Grundlagen aus der Zahlentheorie
- 24.4.2008: Fortsetzung aus der Zahlentheorie, Chinesischer Restklassensatz,
Sieb des Eratosthenes mit Analyse, Dichte von Primzahlen: untere Schranke
- 8.5.2008: Dichte von Primzahlen: obere Schranke, Grundlagen aus der Algebra:
Struktur zyklischer Gruppen
- 15.5.2008: Fortsetzung Struktur zyklischer Gruppen
- 29.5.2008: in endlichen Körpern ist die multiplikative Gruppe zyklisch,
Fermat-Test mit Analyse, nichttriviale Quadratwurzeln von 1 modulo n
- 5.6.2008: Miller-Rabin-Test mit Analyse, Quadratische Reste
- 12.6.2008: Solovay-Strassen-Test mit Analyse
- 19.6.2008: Polynomringe
- 26.6.2008: Restklassenring von Polynomen
- 3.7.2008: Fortsetzung Restklassenring von Polynomen, AKS-Algorithmus mit Laufzeitanalyse
- 10.7.2008: Korrektheitsbeweis AKS-Algorithmus: Charakterisierung von Primzahlpotenzen
- 17.7.2008: Rückblick
Folien
Die Folien zur Vorlesung sind hier
erhältlich.
17.7.2008 - Beate
Bollig