Algorithms for numbers and prime numbers (Q2913092)

From the text: In der Vorlesung ``Einführung in das symbolische Rechnen'' ging es um prinzipielle Fragen und Probleme, deren Betrachtung für den qualifizierten Einsatz von Computer\-algebra-Werkzeugen im alltäglichen Gebrauch von Vorteil sind. Diese Vorlesung soll einen tieferen Einblick in die Algorithmen vermitteln, die für die grundlegenden Funktionalitäten des Rechnens mit exakten Zahlen sowie Primtests und Faktorisierung zum Einsatz kommen. Derartige AlgorithmenNEWLINEspielen nicht nur im Kern von CAS eine wichtige Rolle, sondern haben darüber hinaus auch eine zentrale Bedeutung etwa in kryptografischen Anwendungen. Daneben hat das Gebiet auch Bedeutung für die theoretische Informatik, etwa im Kontext des Problems (P = NP). Ich werde dazu in der Vorlesung ein wichtiges neueres theoretisches Ergebnis darstellen: den von drei indischen Mathematikern im August 2002 erbrachten Beweis, dass das Primtestproblem in Polynomialzeit entschieden werden kann.NEWLINENEWLINENeben den Algorithmen selbst wird auch deren Laufzeitverhalten untersucht, um auf diese Weise grundlegende Vorstellungen über Komplexitätsfragen im Zusammenhang mit Anwendungen des symbolischen Rechnens zu erarbeiten. Algorithmische Beispiele werde ich auf der Basis von Code oder Pseudocode besprechen, der sich an der Sprache des CAS Maxima orientiert und in vielen Fällen direkt lauffähig ist.NEWLINENEWLINEDieser Kurs stellt deutlich höhere Anforderungen an die mathematische Vorbildung der Teilnehmer als die Vorlesung ``Einführung in das symbolische Rechnen''. Insbesondere werden Grundkenntnisse der höheren Algebra, wie etwa über endliche Körper und das Rechnen in Restklassenringen, als bekannt vorausgesetzt. Zu diesen Fragen liegt ein Studienmaterial im Netz.NEWLINENEWLINENEWLINEDie Vorlesung orientiert sich stark am Buch von \textit{R. Crandall} and \textit{C. Pomerance} [Prime numbers. A computational perspective. Berlin: Springer (1999; Zbl 0995.11072)], wobei der Schwerpunkt auf praktikablen Verfahren für die verschiedenen grundlegenden algorithmischen Fragestellungen für Zahlen und Primzahlen liegt. Auch die wichtigsten Ideen für laufzeiteffiziente Verfahren werden dargestellt, ohne allerdings bis in die letzten Details einer getrimmten Implementierung oder eines vielleicht theoretisch interessanten, aber praktisch bedeutungslosen Verfahrens zu verzweigen.