Algorithmische Zahlentheorie und Public Key Kryptographie
Vorlesung (4std.) mit Übungen (2std.)von Otto Forster
am Mathematischen Institut, LMU München
Theresienstr. 39
Sommer-Semester 2009,
Mi, Fr 14-16, Raum A027
Übungen: Mi 16-18
Beschreibung:
In diesem Kurs betrachten wir die elementare Zahlentheorie bis zum
quadratischen Reziprozitätsgesetz vom algorithmischen Standpunkt aus.
Wichtige Probleme sind dabei die Faktorzerlegung von ganzen Zahlen,
Primzahltests und die Berechnung des diskreten Logarithmus. Diese
Probleme haben Anwendungen in der modernen Public Key Kryptographie,
welche sich dadurch auszeichnet, dass zur Verschlüsselung
geheimer Nachrichten ein öffentlicher Schlüssel verwendet wird,
was für den elektronischen Datenverkehr, der leicht
abgehört werden kann, besonders wichtig ist. Nur zum
Entschlüsseln wird vom Empfänger der Nachricht ein
geheim zu haltender Schlüssel benutzt.
Die algorithmische Zahlentheorie hat eine lange Geschichte
(Euklidischer Algorithmus, Sieb des Eratosthenes). Seit
dem Aufkommen schneller Computer sind neue, effiziente
Algorithmen entwickelt worden. Einige davon benutzen interessante
algebraische und geometrische Methoden, wie die Theorie der
Elliptischen Kurven.
Vorkenntnisse:
Anfänger-Vorlesungen Lineare Algebra, Analysis.
Nützlich ist auch eine Vorlesung Zahlentheorie oder Algebra,
sowie Spass am Programmieren.
Schein: Gilt für Diplomhaupt- und Int. Masterprüfung (AM).
Für: Studierende der Mathematik oder Informatik im Hauptstudium, sowie Lehramts-Studenten.
Inhalt:
- Die Fibonacci-Zahlen
- Der Euklidische Algorithmus
- Der Restklassenring Z/n
- Die multiplikative Gruppe (Z/n)*, Primitivwurzeln
- Quadratische Reste, Reziprozitätsgesetz
- Primzahl-Tests
- Faktorisierungs-Algorithmen
- Einführung in die Kryptographie
- Block-Verschlüsselungs-Verfahren
- Das RSA-Kryptosystem
- Der Diskrete Logarithmus
- Digitale Signaturen
- Elliptische Kurven
Literatur
- Bach/Shallit: Algorithmic Number Theory. MIT Press
- J. Buchmann: Einführung in die Kryptographie. Springer
- H. Cohen: A Course in Computational Algebraic Number Theory. Springer
- O. Forster: Algorithmische Zahlentheorie, Vieweg-Verlag
- J. von zur Gathen / J. Gerhard: Modern Computer Algebra. Cambridge U.P
- S. Wagstaff: Cryptanalysis of Number Theoretic Ciphers. Chapman and Hall
Vorlesungen vergangener Semester
|
Bücher/Books | Eprints | Software |
Otto Forster 2011-07-27