Algorithmische Zahlentheorie und Public Key Kryptographie

Sommer-Semester 2009,
Mi, Fr 14-16,   Raum A027

Übungen: Mi 16-18,   Raum A027
Zweite Übungsgruppe: Fr 16-18,   Raum B004

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:

1. Die Fibonacci-Zahlen
2. Der Euklidische Algorithmus
3. Der Restklassenring Z/n
4. Die multiplikative Gruppe (Z/n)*, Primitivwurzeln
5. Quadratische Reste, Reziprozitätsgesetz
6. Primzahl-Tests
7. Faktorisierungs-Algorithmen
8. Einführung in die Kryptographie
9. Block-Verschlüsselungs-Verfahren
10. Das RSA-Kryptosystem
11. Der Diskrete Logarithmus
12. Digitale Signaturen
13. Elliptische Kurven   (ps)   (pdf)  

Teil II der Vorlesung

ARIBAS-Code für einige zahlentheoretische Algorithmen

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

Otto Forster (), 2009-03-06