Lehrstuhl Prof. Dr. E. Speckenmeyer

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.