Vorlesung über "Algebraische Algorithmen"

Algebraische Algorithmen stellen neben den zugehörigen algebraischen Strukturen die Grundlage für sogenannte Computeralgebrasysteme dar. Hierunter versteht man die Umsetzung algorithmischer Verfahren, die Probleme algebraischer Natur effizient lösen.

In der Vorlesung werden zunächst strukturelle Aspekte und algorithmische Verfahren zu gruppen- und zahlentheoretischen Problemen, wie modulare Arithmetik, (Erweiterter) Euklidischer Algorithmus, Chinesischer Restsatz, Faktorisierung/Multiplikation grosser Zahlen, Primzahltest etc., behandelt. Dabei geht es sowohl um die (Problematik der) komplexitätstheoretische(n) Einordnung solcher Probleme, sowie um praktisch nutzbare, effiziente Verfahren die, wie im Falle des Primzahltests, auch randomisierter Natur sein können. In diesem Kontext soll auch die Hauptanwendung nämlich das Gebiet der Kryptologie kurz umrissen werden.

Sodann werden effiziente Verfahren zur Polynommultiplikation, und die damit eng verwandte Schnelle Diskrete Fouriertransformation samt Anwendungen behandelt. Hier werden auch Implementationsmöglichkeiten auf Rechnernetzen vorgestellt.

Anschliessend wird auf einige Verfahren und Anwendungen der Numerischen Linearen Algebra eingegangen. Falls die Zeitvorgabe es zulässt, kann noch auf die Thematiken Polynomfaktorisierung, Gröbnerbasen und Buchberger-Algorithmus eingegangen werden.

Termine

Dienstags 12.00 Uhr - 13.30 Uhr, Pohligstr. 1, Seminarraum 616

Einordnung und Scheinvergabe

Einordnung: B/D.

Literatur

• J. von zur Gathen, J. Gerhard, Modern Computer Algebra, Cambridge University Press, 2003.
• M. Kaplan, Computeralgebra, Springer-Verlag, 2005.
• P. Bürgisser, Completeness and Reduction in Algebraic complexity theory, Springer-Verlag, 2000.
• P. Bürgisser, M. Clausen, M.A. Shokrollahi, Algebraic complexity theory, Springer-Verlag, 1997.
• J. Köbler, U. Schöning, J. Toran, The graph isomorphism problem: its structural complexity, Birkhäuser, 1993.
• A. Salomaa, Public-Key Cryptography, Springer-Verlag, 1996.

Weitere spezielle Literatur wird in Verbindung mit der Themenvergabe angegeben werden.