Vorlesung
Effiziente Algorithmen für den
Primzahltest
Sommersemester 2007
| Veranstalterin: |
Beate Bollig
beate.bollig uni-dortmund.de |
|
| Termin: |
donnerstags 8:20-9:50 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
- 5.4.2007: God may not play dice with the universe but something
strange is going on with the prime numbers. (Paul Erdös)
- 12.4.2007: Komplexität von Algorithmen, Kosten arithmetischer Operationen,
Schnelle Exponentiation mod m, Test auf perfekte Potenz,
Grundlagen aus der Zahlentheorie
- 19.4.2007: Erweiterter Euklidischer Algorithmus, Chinesischer Restklassensatz,
Sieb des Eratosthenes
- 26.4.2007: Dichte von Primzahlen
- 3.5.2007: obere Schranke für Dichte von Primzahlen,
Grundlagen aus der Algebra: Struktur zyklischer Gruppen
- 10.5.2007: Fortsetzung Exkurs Abstrakte Algebra: kleiner Satz von Fermat,
Untergruppen zyklischer Gruppen, Generatoren, Ringe und Körper
- 24.5.2007: multiplikative Gruppen in endlichen Körpern sind zyklisch,
Fermat-Test, Vorbereitung Miller-Rabin-Test
- 31.5.2007: Miller-Rabin-Test und Analyse, Quadratische Reste
- 14.6.2007: Solovay-Strassen-Test
- 21.6.2007: Exkurs Algebra II: Polynomringe
- 28.6.2007: Fortsetzung Exkurs Algebra II: Faktorisierung von Polynomen
- 5.7.2007: AKS-Algorithmus (deterministischer Primzahltest) und Laufzeitanalyse
- 12.7.2007: Korrektheit AKS-Algorithmus
Folien
Die Folien zur Vorlesung sind hier
erhältlich.
Die Folien 134, 155, 158, 163, 166, 195-198, 200-202, 206, 249-253, 262-265, 275-276
sind in der Vorlesung nicht behandelt worden.
12.7.2007 - Beate
Bollig