Department Mathematik
print


Navigationspfad


Inhaltsbereich

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:

  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

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