Schon seit den 50-er Jahren versucht man, neben rein numerischen Rechnungen auch algebraische Umformungen mit Computern zu erledigen. Herausgekommen sind dabei kleine und große Computeralgebra-Systeme, in denen teilweise Hunderte von Mann-Jahren Entwicklung und eine ungeheure mathematische Expertise stecken. Deshalb bringt es nicht nur viel, wenn
man mit solch einem Programm arbeitet, sondern es lohnt sich auch hinter die Kulissen zu schauen.
Das vorliegende Buch stellt deshalb einige dieser Systeme vor und zeigt an Beispielen deren Leistungsf ̈higkeit. Grundlegende Techniken, wie etwa das Rechnen mit großen ganzen Zahlen oder Polynomen, werden untersucht. Dabei zeigt sich, dass man oft f ̈r ein Problem mehrere Algorithmen braucht, weil diese ganz verschiedene St ̈rken haben. Die Algorithmen werden begr ̈ndet, oft in einer Pseudoprogrammiersprache dargestellt, die sichnicht in technischen Details verliert, und analysiert. Dies wird begleitet von vielen durchgerechneten Beispielen.
Oftmals stellt es sich heraus, dass vermeintliche Umwege uber andere mathematische Strukturen der schnellste Weg sind, z.B. wenn f ̈r die Faktorisierung ganzzahliger Polynome in endlichen K ̈rpern gerechnet wird. Da dies algebraische Kenntnisse erfordert, werden die n ̈tigen Grundlagen ̈glichst kurz und ohne Beweise eingef ̈hrt, so dass Kenntnisse der linearen Algebra zum Verst ̈ndnis ausreichen sollten. Sicher n ̈tzlich sind außerdem Erfahrungen mit einer Programmiersprache.
Die ersten 4 Kapitel stellen die Grundlagen bereit. Die folgenden Kapitel sind weitestgehend unabh ̈ngig voneinander und k ̈nnen auch einzelnoder in anderer Reihenfolge gelesen werden. Bei den vielen enthaltenen Beispielen w ̈re es von Vorteil, wenn man diese selber (am besten mit einem Computeralgebra-System seiner Wahl) durchrechnet und variiert.
Der vorliegende Text basiert auf Vorlesungen und Seminaren, die ichzwischen den Jahren 1997 und 2004 am Zentrum Mathematik der TUM ̈nchen f ̈r Informatiker und Mathematiker (meist im Hauptstudium) angeboten habe. So sind auch die genannten Studenten die Hauptzielgruppe dieses Buches. Ansonsten sollen alle jene angesprochen werden, die sich fur algebraischen Algorithmen interessieren, etwa Ingenieure, die Anwendungen in der Codierungstheorie, Kryptographie oder benachbarten F ̈chern haben.a
Munchen, im Sommer 2004
M. Kaplan