Seminar im Wintersemester 1998/1999:

Seminar über Computeralgebra

H. Kredel, M. Schlichenmaier, W.K. Seiler:

Beginn: 23. Oktober 1998

INHALT: Thema dieses Semesters ist die Algorithmische Zahlentheorie mit ihren Anwendungen, wobei hier besonders die Kryptographie eine große Rolle spielen wird. Themen sind dementsprechend das Rechnen mit großen Zahlen (mehrere hundert Stellen), die Faktorisierung solcher Zahlen, das Rechnen modulo einer großen Zahl, wie man es beispielsweise für das RSA-Verfahren braucht, der chinesische Restesatz, mit dessen Hilfe man ein Geheimnis unter mehreren Personen aufteilen kann, und so weiter.

Das Seminar wendet sich an Mathematiker und Lehramtskandidaten (bei entsprechendem Interesse auch Informatiker) mit Interesse an Anwendungen der Zahlentheorie in Kryptographie, Kommunikation und so weiter.

Voraussetzungen: Alle benötigten zahlentheoretischen Grundlagen werden im Laufe des Seminars bereitgestellt werden; die Teilnehmer sollten allerdings wissen, was ein Vektorraum über einem endlichen Körper ist.

Vorläufige Themenliste

• Block I: Ganze Zahlen
  1. Einführung
     (erweiterter) Euklidischer Algorithmus, chinesischer Restesatz (mit kryptographischen Anwendungen), multiplikative Struktur der Zahlen modulo n, kleiner Satz von Fermat, Anwendung auf RSA, kurze Diskussion des Rechnens mit großen Zahlen
  2. Primzahlen
     Siebverfahren, Anwendung des kleinen Satzes von Fermat, Carmichaelzahlen, Konstruktion kryptographisch brauchbarer Primzahlen
  3. Primzahlen und Charaktersummen
     Bei großem zahlentheoretischem Interesse der Teilnehmer kann ein solcher Vortrag über deterministische Primzahltests eingefügt werden
  4. Quadratische Reste
     Primzahltest von Miller-Rabin, quadratisches Reziprozitätsgesetz, Anwendungen quadratischer Reste in kryptographischen Protokollen
  5. Elementare Faktorisierungsverfahren
     Abdividieren, Monte-Carlo-Methode, Fermat, (p-1)-Methode, (p+1)-Methode
  6. Siebverfahren zur Faktorisierung
     Lineares und quadratisches Sieb, multipolynomiale Version des quadratischen Siebs, Grundidee von Zahlkörper- und Funktionenkörpersieb
  7. Die elliptische Kurvenmethode
     Gruppentheoretische Reinterpretation von (p-1)- und (p+1)-Methode, elliptische Kurven, ECM
• Block II: Endliche Körper
  1. Einführung
     Klassifikation der endlichen Körper, Struktur der multiplikativen Gruppe, primitive Elemente, Darstellung der Elemente von F_q
  2. Rechnerische Aspekte
     Rechenoperationen mod p, Beschleunigung der Division nach Montgomery, Rechnen in F_q, der Spezialfall q = 2ⁿ
  3. Diskrete Logarithmen
     Definition, kryptographische Relevanz, Berechnungsmethoden
  4. Schieberegisterfolgen
     Lineare Schieberegister mit feedback, Anwendungen
• Block III: Polynome
  1. Einführung
     Division, Euklidischer Algorithmus, Problem der Zwischenergebnisse, modulare Verfahren, elementare Schranken
  2. Faktorisierung I
     Berlekamp-Algorithmus, Henselsches Lemma
  3. Faktorisieren II
     LLL-Algorithmus
  4. Weitere Anwendungen des LLL-Algorithmus
     Ganzzahlige Optimierung, Kryptoanalyse

Literatur
Literatur zu den einzelnen Vortägen wird im Seminar angegeben; eine Auswahl allgemein interessanter Bücher ist

• O. Forster: Algorithmische Zahlentheorie, Vieweg 1996
• F. Schwarz: Einfühung in die elementare Zahlentheorie (mit MuPAD und CD), Teubner 1998
• H. Riesel: Prime numbers and computer methods for factorization, Birkäuser 1985
• N. Koblitz: A course in number theory and cryptography, Springer 1987, 1994, 1997