Vorlesung
Effiziente Algorithmen für den
Primzahltest
Sommersemester 2006
| Veranstalterin: |
Beate Bollig
beate.bollig uni-dortmund.de |
|
| Termin: |
donnerstags 8:30-10:00 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:
Martin Dietzfelbinger (2004). Primality Testing in Polynomial
Time. Springer Verlag.
Juraj Hromkovic (2004). Randomisierte Algorithmen. Teubner Verlag.
Rajeev Motwani, Prabhakar Raghavan (1995). Randomized Algorithms.
Cambridge University Press.
Inhalt der Vorlesung
- 6.4.2006: God may not play dice with the universe but something
strange is going on with the prime numbers. (Paul Erdös)
- 13.4.2006: Komplexität von Algorithmen, Kosten
arithmetischer Op., repeated squaring/Schnelle Exponentiation mod m,
Test auf perfekte Potenz, Exkurs Zahlentheorie
- 20.4.2006: Fortsetzung Exkurs Zahlentheorie
(erweiterter Euklidischer Algorithmus, Chinesischer Restklassensatz ...)
- 27.4.2006: Fortsetzung Exkurs Zahlentheorie: Dichte von Primzahlen
- 4.5.2006: Fortsetzung Dichte von Primzahlen, Exkurs Abstrakte Algebra: Struktur zyklischer
Gruppen
- 11.5.2006: Fortsetzung Exkurs Abstrakte Algebra: kleiner Satz von Fermat,
Untergruppen zyklischer Gruppen, Ringe und Körper, Generatoren
- 18.5.2006: randomisierte Primzahltests: Fermat-Test, Miller-Rabin-Test
- 1.6.2006: randomisierte Primzahltests: Miller-Rabin-Test (Fortsetzung),
Solovay-Strassen-Test
- 8.6.2006: randomisierte Primzahltests: Solovay-Strassen-Test (Fortsetzung)
- 22.6.2006: Nachtrag Beweis Lemma 6.4.5,
Exkurs Abstrakte Algebra (Fortsetzung): Polynomringe
- 29.6.2006: Exkurs Abstrakte Algebra (Fortsetzung)
- 6.7.2006: AKS-Algorithmus, Laufzeitbetrachtung und Korrektheit
- 13.7.2006: Fortsetzung Korrektheit AKS-Algorithmus
- 18.7.2006, 14:15 Uhr: Rest Korrektheit AKS-Algorithmus (für alle Interessierten)
Folien
Die bisher benutzten Folien zur Vorlesung sind hier
erhältlich.
13.7.2006 - Beate
Bollig