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,   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


Otto Forster (email), 2009-03-06