Proseminar: Zahlentheorie und Kryptographie

  Zeitraum Sommersemester 2003

  Inhalt Die Zahlentheorie hat in den letzten Jahren wichtige Anwendungen in der Kryptographie gefunden, insbesondere bei dem im Internet gebräuchlichen RSA-Verfahren. Für die RSA-Verschlüsselung werden große Primzahlen benötigt, und die Sicherheit des Verfahrens beruht darauf, dass die Faktorisierung großer Zahlen sehr zeitaufwändig ist. Um das RSA-Verfahren, Primzahltests und Faktorisierungsverfahren zu behandeln, werden wir auch die benötigten Grundlagen aus der elementaren Zahlentheorie bereitstellen. Eine überraschende neue Entwicklung (über die sogar in der internationalen Presse berichtet wurde) gab es kürzlich mit einer Arbeit von Agrawal, Kayal und Saxena, in der ein deterministischer Primzahltest mit polynomialer Laufzeit vorgestellt wurde.

  Literatur-
auswahl
  • M. Agrawal, N. Kayal und N. Saxena: Primes is in P, Preprint 2002
  • M. Aigner, G.M. Ziegler: Proofs from THE BOOK, Springer 1998
  • D. J. Bernstein, Proving primality after Agrawal-Kayal-Saxena, Preprint-draft 2003
  • A. Beutelspacher, J. Schwenk, K.-D. Wolfenstetter: Moderne Verfahren der Kryptographie, Vieweg 1995
  • N. Koblitz: A Course in Number Theory and Cryptography, Springer 1994
  • R. Remmert, P. Ullrich: Elementare Zahlentheorie, Birkhäuser 1987
  • P. Ribenboim: The little book of big primes, Springer 1991
  • P. Ribenboim: The new book of prime number records, Springer 1996
  • H. Scheid: Zahlentheorie, BI 1991

  •   Links
  • Primzahlgeheimnisse
  • Die Jagd nach grossen Primzahlen
  • The prime pages - prime number research, records, and resources
  • Einige Vorlesungsskripten zur Zahlentheorie und Kryptographie von W. Ruppert
  • Lecture Notes von A. Klappenecker zum Hintergrund des AKS-Tests
  • Kryptographie FAQ

  •   Vorträge
    10.04.03 Kerstin Fröhling
    Teilbarkeit und Primzahlen
    17.04.03 Katharina Werner
    Der Euklidische Algorithmus
    24.04.03 Robert Baier
    Modulare Arithmetik
    30.04.03 Stephan Kip
    Die Struktur der primen Restklassengruppe
    08.05.03 Tatiana Kolova
    Laufzeitfragen, schnelles Potenzieren
    15.05.03 Felix Pape
    Carmichael-Zahlen, Miller-Rabin-Test
      Skript
    22.05.03 Liza Saikisyan
    Klassische Kryptographie und RSA
    28.05.03 Oksana Schestakov
    Endliche Körper und diskrete Logarithmen
      Skript
    05.06.03
    Quadratische Reste
    19.06.03 Christian Gutschwager
    Starke Pseudoprimzahlen, Solovay-Strassen-Test
    25.06.03 Pavel Berkovitch
    Mersenne- und Fermatzahlen, Teil 1
    26.06.03 Jonit Fischmann
    Mersenne- und Fermatzahlen, Teil 2
    03.07.03 Sebastian Peters
    Primzahlverteilung
    10.07.03 Heike Weber
    PRIMES is in P, Teil 1
    17.07.03 Jesus Diaz Diaz
    PRIMES is in P, Teil 2

      Material Skript Konstruktion endlicher Körper von Dr. Marcos Soriano