Hasso-Plattner-InstitutSDG am HPI
Hasso-Plattner-InstitutDSG am HPI
Login
 

Mathematische Grundlagen von modularem Rechnen (Wintersemester 2005/2006)

Dozent:

Allgemeine Information

  • Semesterwochenstunden: 2
  • ECTS: 3
  • Benotet: Ja
  • Einschreibefrist: 03.11.2005
  • Lehrform:
  • Belegungsart: Wahlpflichtmodul

Studiengänge

  • IT-Systems Engineering MA

Beschreibung

Auf Grund der Begrenztheit des Speichervermögens von Computern können grundsätzlich nur Algebren implementiert werden, deren Basismengen endlich oder wenigstens proendlich, d.h. inverse Limites von endlichen Mengen, sind. Daher ist das modulare Rechnen, d.h. das Rechnen mit Restklassen natürlicher Zahlen, oder allgemeiner das Rechnen in endlichen oder proendlichen Algebren die wichtigste Grundlage aller Anwendungen mathematischer Verfahren in der Informatik. Die Vorlesung "Mathematische Grundlagen modularen Rechnens" liefert eine Einführung in die elementare Zahlentheorie, in die Arithmetik endlicher und proendlicher Körper und Ringe, sowie ihrer Moduln und Systeme. Dabei werden die Erfordernisse der Kryptologie in besonderem Maße berücksichtigt. Definitionen und Verfahren werden durch Spezifikationen und Prototypen ergänzt. Die Vorlesung setzt eine gewisse Vertrautheit mit Begriffsbildungen und Methoden der Diskreten Mathematik und Theoretischen Informatik voraus. Um auch dem Novizen die Teilnahme an der Vorlesung zu ermöglichen, werden diese Grundkenntnisse, soweit erforderlich, noch einmal wiederholt.

 

Behandelte Stoffgebiete

 

  • Algebraische Grundlagen
    • Halbgruppen, Monoide, Gruppen
    • Homomorphismen
    • Transformationsgruppen und Permutationsgruppen; Metrik auf Permutationsgruppen
    • Kommutative Ringe und Körper, Polynomringe, Hauptidealringe

  • Zahlentheoretische Grundlagen
    • Elementare Teilbarkeitslehre
    • Primzahlen, Fundamentalsatz der elementaren Zahlentheorie
    • Teilbarkeit und Primteiler, Größter gemeinsamer Teiler, kleinstes gemeinschaftliches Vielfaches
    • Berechnung des größten gemeinsamen Teilers; Fibonacci Zahlen

  • Spezifikationen
    • Basisspezifikationen und Parametrisierte Spezifikationen
    • Spezifikationen mit formalen Parametern - Schablonen (Templates)
    • Konstruktion neuer Datentypen und Templates, interne und externe Konstruktionen
    • Die Spezifikationssprache Pi des Fraunhofer-Instituts für Softwaresystemtechnik; der Potsdamer Pi-Modul-Syntaxchecker und -Compiler, die Möglichkeit separater Compilation und der Compilation unvollständiger Komponenten
    • Konstruktionstechniken für Architekturen
    • Spezifikation algebraischer und zahlentheoretischer Grundoperationen

  • Modulares Rechnen
    • Kongruenzrelationen, Ideale und Restklassen
    • Der Restklassenring
    • Die prime Restklassengruppe und die Eulersche Funktion
    • Der kleine Fermatsche Satz
    • Die Summenformel für die Eulersche Funktion; Möbiussche Umkehrformeln
    • Simultane Kongruenzen, Chinesischer Restsatz
    • Die Struktur der primen Restklassengruppen

  • Quadratische Reste
    • Definition und Reduktion auf Primzahlpotenzmoduln
    • Eulersches Kriterium; Legendre-Symbol und Jacobi-Symbol
    • Das quadratische Reziprozitätsgesetz

  • Primzahltests und Faktorisierung
    • Das Sieb des Eratosthenes
    • Vorstellung verschiedener Primzahltests; Primzahltests und Riemannsche Hypothese
    • Probabilistische Primzahltests
    • Faktorisieren mit quadratischen Resten

  • Der diskrete Logarithmus
    • Die modulare Exponentialfunktion und ihre Berechnung: Square and multiply
    • Berechnung von Quadratwurzeln
    • Der diskrete Logarithmus und seine Berechnung: Baby step - giant step

  • Körpertheorie
    • Der Körperbegriff; endliche Körpererweiterungen
    • Zerfällungskörper und Normalerweiterungen; Separable Erweiterungen
    • Endliche Körper; der Satz von Wedderburn
    • Primkörper der Charakteristik p; Körper der p-adischen Zahlen
    • Der Satz vom primitiven Element

  • Proendliche Mengen
    • Der topologische Raum aller unendlichen Folgen
    • Lineare dynamische Systeme; Schieberegister; erzeugende Funktionen
    • Pseudozufallsfolgen und ihre Komplexität: Sequentielle Chiffren
    • Der Folgenraum einer Transformationsgruppe: Blockchiffren

Literatur

- Eine sehr persönliche Auswahl -

 

Algebraische Grundlagen

  • B.L. van der Waerden, Moderne Algebra (Springer Berlin 1940)
  • S. Lang, Algebra (Addison-Wesley 1965)
  • S. Mac Lane, G. Birkhoff, Algebra (MacMillan New York, London 1967)
  • R. Kochendörfer, Einführung in die Algebra (VEB Deutscher Verlag der Wissenschaften 1955)
  • R. Lidl, H. Niederreiter, Finite Fields (Addison-Weley 1983)
  • Grundlagen aus der Informatik
  • A. V. Aho, J.D. Ullman, Informatik, Datenstrukturen und Konzepte der Abstraktion (Intern. Thomson Publ. 1996).
  • A. V. Aho, J.E.Hopcroft, J.D. Ullman, Data Structures and Algorithms (Addison-Wesley 1983).
  • H. Ehrig, B. Mahr, Fundamentals of Algebraic Specification I (Springer 1985)

 

Berechnungstheorie und Komplexität

  • J. E. Hopcroft, R. Motvani, J. D. Ullman, Introduction to automata theory, languages and computation (Addison-Wesley Boston, San Francisco, New York, London, Toronto, Sydney, Tokyo, Singapore, Madrid, Mexico City, Munich, Paris, Cape Town, Hong Kong, Montreal, 2001).
  • M.R. Garey, D.S. Johnson, Computers and Intractability (Freeman San Francisco 1979)
  • K. Erk, L. Priese, Theoretische Informatik: Eine umfassende Einführung (Springer-Verlag, Berlin, Heidelberg, New York, Barcelona, Hongkong, London, Mailand, Paris, Singapur, Tokyo 2000).
  • K. W. Wagner, Einführung in die Theoretische Informatik (Springer-Verlag, Berlin, Heidelberg, New York, London, Paris, Tokyo 1991).

 

Zahlentheoretische Grundlagen

  • H. Hasse, Vorlesungen über Zahlentheorie (Springer 1950)
  • F. Neiß, Einführung in die Zahlentheorie (Hirzel Leipzig 1952)
  • W.W. Adams, L.J. Goldstein, Introduction to Number Theory (Prentice-Hall 1976)
  • H. Koch, H. Pieper, Zahlentheorie (VEB Deutscher Verlag der Wissenschaften 1976)

 

Kryptologie

  • J. L. Massey, Coding and Cryptography (Advanced Technology Seminars 1985)
  • E. Kranakis, Primality and Cryptography (Teubner, Wiley 1986)
  • Th. Beth, Kryptographie (Univ. Karlsruhe 1987)
  • F.L. Bauer, Entzifferte Geheimnisse (Springer 1991)
  • A. Salomaa, Public-Key Cryptography (Springer 1996)

Leistungserfassung

Für die Belegung der Vorlesung sind 3 Belegungspunkte zu entrichten. Ein erfolgreicher Abschluss wird mit 3 benoteten Leistungspunkten bestätigt. Die Belegungsfrist endet am 3. November 2005.

Die Bewertung der Leistung der Teilnehmer der Vorlesung erfolgt in einer mündlichen Prüfung.

Termine

Vorlesung: Donnerstag 13.30-15.00 Uhr, HPI A-2.1

Zurück