Vorlesung über "Algebraische Algorithmen"

Behandelte Inhalte

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 großer 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, 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. Anschließend wird auf einige Verfahren und Anwendungen der Numerischen Linearen Algebra eingegangen.

Falls die Zeitvorgabe es zulässt, kann noch auf die Thematiken Polynomfaktorisierung, Grobnerbasen und Buchberger-Algorithmus eingegangen werden. In loser Folge werden Übungsaufgaben ausgegeben, die im Rahmen der Vorlesung besprochen werden.

Folgeveranstaltung kommendes Semester

Falls seitens der Hörer der Veranstaltung Interesse besteht, wird im WS 05/06 ein Seminar über weiterführende Aspekte der algebraischen Strukturen, zugehöriger Algorithmen sowie Fragen zur Algebraischen Komplexitätstheorie auf der Grundlage von Originalarbeiten (als Blockveranstaltung) angeboten.

Termine

Vorlesungsbeginn ist Dienstag, der 19.04.2005. Die Vorlesung findet dienstags von 11.45-13.15 Uhr im Seminarraum 616 des Pohlighauses statt.

Literatur

• J. von zur Gathen, J. Gerhard, Modern Computer Algebra, Cambridge University Press, 2003.
• M. Kaplan, Computeralgebra, Springer-Verlag, 2005
• U. Schöning, Algorithmik, Spektrum Verlag, 2001.
• A. Salomaa, Public-Key Cryptography, Springer-Verlag, 1996.