Modern Computer Algebra
J. von zur Gathen, J. Gerhard
Cambridge University Press, Cambridge, 1999, XIV + 754 Seiten, 109 $
ISBN 0-521-641764
Das Buch Modern Computer Algebra von J. von zur Gathen und J. Gerhard wird sich sicher zu einem Standardwerk über Computeralgebra entwickeln. Es ist sehr liebevoll aufbereitet mit historischen Einleitungen und Anmerkungen, vielen Beispielen, Bildern und Anwendungen sowie einer Vielzahl von Übungsaufgaben. Das Buch beginnt mit einer Sammlung motivierender Anwendungen, u.a. Modellierung von Cyclohexan-Molekülen und RSA-Verschlüsselung, die später nach der Entwicklung der nötigen Theorie wieder aufgegriffen werden.
Die Kapitel sind nach Wegbereitern der Computeralgebra benannt: Euklid, Newton, Gauß, Fermat und Hilbert. Das erste startet mit den grundlegenden Algorithmen zur Multiplikation und Division (mit Rest). Hauptthema aber ist der Euklidische Algorithmus in verschiedenen Spielarten und Anwendungen wie Kettenbrüche, Partialbruchzerlegung, Resultanten und Subresultanten etc. Alle diese Algorithmen wie auch die späteren sind durch sorgfältige Aufwandsanalysen begleitet. Flankiert wird dieses Kapitel durch Ausflüge in die Kalenderkorrektur, Tonsysteme und die Codierung mit BCH-Codes.
Hauptthema des zweiten Kapitels Newton ist die schnelle Arithmetik. Es beginnt mit einer Darstellung des Karatsuba-Algorithmus, der diskreten und schnellen Fouriertransformation bis zum Algorithmus von Schönhage und Strassen. Danach folgt eine Einführung des Newtonverfahrens mit Konvergenzverhalten (Julia-Mengen), Polynomwertberechnung und Interpolation. Anschließend wird mit dem schnellen Euklidischen Algorithmus das Hauptthema des ersten Kapitels weitergeführt. Es folgt ein Kapitel über schnelle Matrixmultiplikation mit dem (ersten) Algorithmus von Strassen sowie Verfahren für spezielle Matrizen, z. B. dünn besetzte (Wiedemann). Für die fortgeschritteneren und für die Komplexitätstheorie interessanten Algorithmen von Strassen und von Winograd wird auf die Literatur verwiesen. Beschlossen wird das Kapitel mit der stetigen Fouriertransformation mit Anwendung auf Bildkompression.
Das Kapitel Gauß ist der Faktorisierung von Polynomen gewidmet. Es enthält zunächst Algorithmen zur Faktorisierung von Polynomen über endlichen Körpern, z. B. die Algorithmen von Berlekamp und Cantor-Zassenhaus. Weiter die Henselsche Liftungsmethode in Polynomringen über p-adischen Zahlen, die zum Zassenhaus-Algorithmus zur Zerlegung ganzzahliger Polynome führt. Schließlich wird die Gitterbasisreduktion nach Lenstra-Lenstra-Lovasz beschrieben und mit deren Hilfe die Polynomialität der Primzerlegung ganzzahliger Polynome gezeigt. Als weitere Anwendungen werden u. a. simultane diophantische Approximationen behandelt und Angriffsmöglichkeiten auf Cryptosysteme vorgeführt.
Im Kapitel Fermat werden Primzahltest und Primzerlegungsalgorithmus für ganze Zahlen behandelt. Der erste Paragraph führt über das Studium von Carmichael-Zahlen zum Primzahltest von Solovay und Strassen. Der folgende enthält elementare Faktorisierungsalgorithmen wie Pollards 
- und (p-1)-Methode, Dixon's random square Methode (leider ohne Verfeinerung zum quadratischen Sieb) sowie eine Beschreibung der elliptischen Kurven-Methode von Lenstra. Beschlossen wird dieses Kapitel mit der Vorstellung von diversen Verschlüsselungssystemen, insbesondere dem auf obigen Resultaten aufbauenden RSA-Schema.
Das letzte Kapitel ist nichtlinearen algebraischen Gleichungssystemen gewidmet. Nach Einführung von Gröbnerbasen wird der Buchbergersche Algorithmus behandelt, und es werden geometrische Anwendungen gezeigt. Bei der Komplexitätsuntersuchung wird festgestellt, daß dieser grundlegende Algorithmus der Klasse der doppelt-exponentiellen Algorithmen angehört, wodurch seine Reichweite im allgemeinen sehr eingeschränkt ist. Es folgen Abschnitte über symbolische Integration, u. a. mit dem Algorithmus von Rothstein und Trager, und symbolische Summation mit dem Gosper-Algorithmus. Unter den Anwendungen sind u. a. Petri-Netze und automatisches Beweisen (von Formeln) zu finden. Schließlich wird zum Abschluß das Cyclohexan-Beispiel aus der Einführung ausführlich behandelt.
Das Buch deckt den Standardstoff einer ein- bis zweisemestrigen Vorlesung über Computeralgebra ab. Unter anderem wegen der vielen Beispiele, historischen Anmerkungen und Verweise ist es als Begleitlektüre sehr zu empfehlen. Da insbesondere die Themen der ersten beiden Kapitel sehr ausführlich behandelt und illustriert werden, ist dieses Buch auch zum Selbststudium geeignet. Es kann weiter Impulse für Vorlesungen an Fachhochschulen sowie für Arbeitsgemeinschaften an Schulen geben. Ich wünsche diesem Buch einen breiten Leserkreis.
Rezension: B. H. Matzat (Heidelberg) aus Computeralgebra-Rundbrief, Nr. 27 - Oktober 2000