Leseecke

Codierungstheorie
Algebraisch-geometrische Grundlagen und Algorithmen

W. Lütkebohmert
Vieweg Verlag, Braunschweig, Wiesbaden, 2002, 49,95 €

ISBN 3-528-03197-2

Vorliegendes Buch entstand aus einer einsemestrigen Vorlesung des Autors an der Universität Ulm. Sie war an Hörer mit Grundkenntnissen in Algebra gerichtet. Ziel der Vorlesung war es, den Studenten einen Rundblick über algebraisch konstruierte lineare Codes zu vermitteln. Das aus der Vorlesung mit demselben Ziel entstandene Buch wurde dann noch durch einige für die geometrischen Goppa-Codes notwendige Grundlagen aus der kommutativen Algebra und der Geometrie algebraischer Kurven angereichert.

Das Buch besteht aus drei Teilen. Der erste Teil mit den Kapiteln 1 bis 5 enthält die Elementare Codierungstheorie. Er umfasst allgemeine Standardresultate über lineare Codes inklusive der Behandlung einiger wichtiger Codeklassen wie Hamming- und Golaycodes, zyklische Codes mit BCH-Codes sowie Reed-Solomon-Codes, eingerahmt von Codekonstruktionen wie Spreizung und Verkettung sowie den klassischen Schrankensätzen: Singleton-Schranke, Plotkin-Schranke, Hamming- und Eliasschranke sowie als untere Schranke die Gilbert-Varshamov-Schranke. Wohl auf Grund fehlender Vorkenntnisse der Hörer auf dem Gebiet der Elementaren Zahlentheorie wurde auf die Behandlung der Quadratische-Reste-Codes verzichtet.

Der zweite Teil des Buches umfasst die für die Behandlung der geometrischen Goppa-Codes notwendigen geometrischen Grundlagen und besteht aus Kapitel 6.1, 8 und 7. Dabei enthält Abschnitt 6.1 eine kurze Zusammenfassung (ohne Beweise) der für die Einführung der Goppa-Codes notwendigen Sätze wie Satz von Riemann-Roch, Residuensatz und Hurwitzsche Relativgeschlechtsformel. Kapitel 8 enthält die dazugehörigen Beweise und die Konstruktion singularitätenfreier Modelle von Kurven. In Kapitel 7 werden speziell Kurven über endlichen Körpern studiert und die Riemannsche Vermutung für die zugehörigen Zetafunktionen bewiesen, was schließlich auf die für das Studium der Goppa-Codes unverzichtbaren Schrankensätze für die Anzahl der rationalen Punkte führt.

Der dritte Teil, bestehend aus den Kapiteln 6 und 9, enthält die angestrebten Resultate über geometrische Goppa-Codes. Nach der allgemeinen Einführung konzentriert sich der Autor auf die Konstruktion langer Codes, zuvor behandelt er aber noch zum Vergleich die klassischen Goppa-Codes, die auch schon im Rahmen der elementaren Theorie hätten vorgestellt werden können. Darauf folgt – und das ist sicher ein Höhepunkt dieses Buches – eine geometrische Konstruktion der 1996 von Garcia und Stichtenoth gefundenen Artin-Schreier-Türme, deren Punktanzahl die Drinfeld-Vladut-Schranke erreichen. Dies führt schließlich zu einem elementaren Beweis des Satzes von Tsfasman-Vladut-Zink, der besagt, dass man mit geometrischen Goppa-Codes die Gilbert-Varshamov- Schranke übertreffen kann. In meiner Vorlesung Galoistheorie im vergangenen Wintersemester habe ich diesen Teil noch durch einige allgemeine Strukturaussagen über selbstduale Codes und Automorphismen sowie durch die Untersuchung spezieller Codeklassen wie elliptische und hermitesche Codes ergänzt. (Entsprechende Resultate sind in den Büchern von Tsfasman-Vladut: Algebraic-Geometric Codes bzw. Stepanov Codes on Algebraic Curves: zu finden.) Schließlich enthält das letzte Kapitel 9 noch die Standardalgorithmen zur Codierung und Decodierung geometrischer Goppa-Codes mit praktischen Hinweisen zur Implementierung.

Am Ende des Buches hat der Autor in zwei Anhängen noch einige benötigte Resultate aus der Kommutativen Algebra und der Algebraischen Geometrie zusammengestellt, die zumeist in weiterführenden Algebra-Vorlesungen behandelt werden.

Insgesamt ist das Buch als Grundlage für Vorlesungen und auch zum Selbststudium geeignet, wünschenswerte Ergänzungen sind in der Besprechung der einzelnen Teile angemerkt. Es ist ein geometrisches Pendant zu dem inzwischen über 10 Jahre alten bewährten Buch von Stichtenoth: Algebraic Function Fields and Codes, das geometrische Goppa-Codes in der zahlentheoretischen Sprache algebraischer Funktionskörper behandelt (und ganz auf die Elementare Codierungstheorie verzichtet, wofür aber z.B. das Büchlein von Willems: Codierungstheorie herangezogen werden kann). Ein Pluspunkt der vorliegenden Ausgabe ist der auch für Studierende erschwingliche Preis. Bei den konkurrierenden Büchern von Tsfasman-Vladut und Stepanov vom Kluwer-Verlag stellt der Preis selbst für Fachbibliotheken gelegentlich ein Anschaffungshindernis dar.

Rezension: Bernd Heinrich Matzat (Heidelberg) aus Computeralgebra-Rundbrief, Nr. 34 - März 2004

A History of Algorithms
From the Pebble to the Microchip

Chabert, Jean-Luc (Ed.)
Springer, Berlin-Heidelberg-New York, 1999, 100 Abb., pp. 524, 78,92$
(französische Originalausgabe bei Éditions Belin, Paris, 1994)

ISBN 3-540-63369-3

Bei diesem Buch handelt es sich um die englische Übersetzung einer von einer Gruppe von französischen Mathematik-Historikern herausgegebenen und kommentierten Sammlung von über 200 Original-Texten zur Geschichte der Algorithmen. Der zeitliche Rahmen reicht dabei von der sumerischen und ägyptschen Zahldarstellung und Arithmetik bis zur formalen Präzisierung des Algorithmenbegriffes in den 30-er Jahren des 20. Jahrhunderts. Thematisch werden weit überwiegend numerische Algorithmen behandelt, algorithmische Problemstellungen etwa der Geometrie, der Logik, Algebra oder der diskreten Mathematik werden nicht betrachtet, wie auch Fragen der Komplexität allenfalls am Rande oder implizit angesprochen werden. Das Buch erhebt, auch unter den Beschränkungen, die sich die Autoren bewusst auferlegt haben, weder einen Anspruch auf enzyklopädische Vollständigkeit, noch ist es eine Art Lehrbuch. Vielmehr will es ein historisches "mathematisches Lesebuch'' sein, mit dem die Autoren die Absicht verbinden, die sie mit "...which offers a different perspective by giving pride of place to algorithms'' formulieren.

Das Buch gliedert sich in 15 thematisch abgeschlossene Kapitel, wobei in einer Einleitung und in einem Vorspann zu jedem der ausgewählten Texte jeweils deren historische Bedeutung und ihre Beziehungen untereinander (wie auch Querbezüge zu anderen Kapiteln) erläutert werden. Auch die Stellung im Werk des jeweiligen Autors und Anmerkungen zu dessen Werk und Wirkung insgesamt werden knapp, aber prägnant, kommentiert. Viele der (ins Englische übertragenen) Original-Texte werden zusätzlich noch in der heutigen Sprache der Mathematik nach-formuliert und interpretiert, wo dies für das Verständnis geboten erscheint.

Die ersten drei Kapitel beschäftigen sich mit den elementaren arithmetischen Operationen, (etwas aus dem Rahmen fallend, aber deshalb nicht weniger interessant) der Konstruktion von magischen Quadraten, sowie der berühmten regula falsi. Das vierte Kapitel behandelt Euklid's Algorithmus, Bezout's Identität, Kettenbrüche und Sturm'sche Ketten, und berührt damit auch die Ursprünge der Computeralgebra. Die drei folgenden Kapitel behandeln iterative, approximierende Verfahren zur Berechnung von π, Newton's Tangenten- und Polygonmethoden, sowie weitere Verfahren zur Wurzelberechnung. Dieser Weg in die Numerik wird, nach einem arithmetischen Kapitel (Primzahlen, Faktorisierung), weiter verfolgt mit den Themen: Lösen linearer Gleichungssysteme, Interpolation, Approximation von Integralen, approximierende Lösungen von gewöhnlichen Differentialgleichungen, Funktionsapproximation, sowie Konvergenzbeschleunigung. Das letzte Kapitel fällt etwas aus diesem Rahmen, indem es die Bemühungen von Gödel, Church, Kleene, Turing und Post um eine präzise Formulierung des Algorithmenbegriffes nachzeichet. So historisch wichtig dies ist, man muss wohl doch feststellen, dass der Anstoss zu dieser Entwicklung nicht aus der numerisch orientierten Mathematik kam.

Schließlich enthält dieses Buch, neben weiterführenden Bibliographien zu den einzelnen Kapiteln, ein Sammlung von über 200 Kurzbiographien der zitierten Mathematiker.

Was interessiert nun aus der Sicht der Computeralgebra an einem Buch, dessen Inhaltsverzeichnis, wie die Autoren selbst schreiben, "... might suggest that this is a standard work of numerical analysis'' ? Nun, die historische Perspektive der Algorithmik ist für sich genommen m.E. schon eine spannende Sache, wenn sie für den Nicht-Philologen so konzise und gut lesbar aufbereitet dargeboten wird. Außerdem: das kürzlich erschienene Buch Modern Computer Algebra von J. von zur Gathen und J. Gerhard das wohl gute Chancen hat, sich als ein Referenztext für die Algorithmik der Computeralgebra zu etablieren, betont historische Bezüge in erfreulicher Weise. Das kommt in den Überschriften "Euklid'', "Newton'', "Gauss'', "Fermat'', "Hilbert'' und den Einleitungstexten zu den einzelnen Abschnitten deutlich zum Ausdruck. Es ist alles andere als ein Zufall, dass diese "Riesen'', ebenso wie beispielsweise Cauchy, Euler und Lagrange, dort wie in dem hier besprochenen Werk herausragende Rollen spielen.

Rezension: Volker Strehl (Erlangen) aus Computeralgebra-Rundbrief, Nr. 26 - März 2000

A Singular Introduction to Commutative Algebra

G.-M. Greuel, G. Pfister
Springer Verlag, 2008 (2. Auflage), 689+XX Seiten, 53,45 €

ISBN 978-3-540-73541-0

Mit dem Computeralgebrasystem SINGULAR kann man Berechnungen in (kommutativen) Polynomringen mit Koeffizienten in gewissen Körpern sowie in deren Faktorringen und Lokalisierungen (in maximalen Idealen) ausführen. Das vorliegende Buch führt in die Kommutative Algebra und damit auch in die Algebraische Geometrie so weit ein, wie das zum Verständnis der in SINGULAR verwendeten Begriffe und Algorithmen nötig ist. Die Auswahl der Themen erfolgte mit Blick auf deren Bedeutung für die Algebraische Geometrie und die Singularitätentheorie. Die Autoren suchen nicht nach größter Allgemeinheit, sondern beschränken sich auf jene Bereiche, die in einem Computeralgebrasystem darstellbar sind. Alle Begriffe, Algorithmen und Konzepte werden im Buch durch mit SINGULAR gerechnete Beispiele verdeutlicht. Beim Lesen hat man das angenehme Gefühl, dass das Buch viel an Inhalt vermittelt, dabei aber immer im positiven Sinn ”am Boden bleibt“. Das Fehlen von Hinweisen auf Anwendungen der vorgestellten Algorithmen (zum Beispiel in der ganzzahligen Optimierung, der Systemtheorie oder der Statistik) beeinträchtigt den sehr guten Gesamteindruck nur wenig.

Die ersten zwei Kapitel führen in die algorithmische Theorie der kommutativen Ringe und Moduln ein. Es werden die Theorie der Gröbnerbasen und der Standardbasen erläutert und deren grundlegende Anwendungen auf Berechnungen mit Idealen und Untermoduln besprochen (”Gröbner-basics“). In der vorliegenden zweiten Auflage wurde das erste Kapitel um einen Abschnitt ergänzt: Mit einem Beitrag von Viktor Levandovskyy über Gröbnerbasen in G-Algebren, einer Klasse von gewissen assoziativen Algebren, wird der Erweiterung von SINGULAR auf das Rechnen in nichtkommutativen Ringen Rechnung getragen. Wichtige Beispiele für G-Algebren sind Weyl-Algebren und universelle Einhüllende von endlichdimensionalen Lie-Algebren.

Im Kapitel 3 wird die Noethersche Normalisierung einer endlich erzeugten Algebra besprochen und ein auf einem Normalitätskriterium von Grauert und Remmert fußender Algorithmus zu ihrer Berechnung angegeben. Im Kapitel 4 geht es um die Berechnung der Primärzerlegung und des Radikals eines Ideals. Neu gegenüber der ersten Auflage sind Abschnitte über charakteristische Mengen (für die Berechnung der minimalen assoziierten Primideale) und über Dreiecksmengen (für ein Verfahren zur Lösung von nulldimensionalen Systemen polynomialer Gleichungen). Kapitel 5 ist dem Hilbert-Polynom bzw. dem Hilbert-Samuel-Polynom und deren Anwendung auf die Dimensionstheorie gewidmet. Kapitel 6 handelt von formalen Potenzreihen, dem Weierstraßschen Vorbereitungssatz und der Berechnung von Standardbasen von Idealen in Potenzreihenringen. Das abschließende Kapitel 7 ist eine Einführung in die (algorithmische) homologische Algebra.

Das letzte Drittel des Buches besteht aus drei Anhängen: Anhang A liefert den geometrischen Hintergrund für die im Hauptteil des Buches eingeführten Begriffe und Resultate der kommutativen Algebra. Dieser Abschnitt ist eine sehr konkrete und anschauliche Einführung in die algebraische Geometrie. Anhang B (neu in der zweiten Auflage) beschreibt Algorithmen zur Faktorisierung von Polynomen in einer und mehreren Variablen über endlichen Körpern, Q und algebraischen Erweiterungen davon. Anhang C führt in die Benutzung des Computeralgebrasystems SINGULAR ein, dieser Anhang wurde in der zweiten Auflage im Hinblick auf die Version 3-0-3 überarbeitet.

(Rezension: Franz Pauer, Innsbruck) aus Computeralgebra-Rundbrief, Nr. 43 - Oktober 2008

Algebraic Aspects of Cryptography

N. Koblitz
Band 3 der Reihe Algorithms and Computations in Mathematics, Springer-Verlag Berlin-Heidelberg-New York 1998, pp. 206, 149,79€.

ISBN 3-540-63446-0

Der Autor, der durch seine Bücher "Introduction to Elliptic Curves and Modular Forms'' (GTM 97, Springer 1984) und "A Course in Number Theory and Cryptography'' (GTM 114, Springer 1987) vielen Lesern dieses Rundbriefs gut bekannt sein wird, hat hier ein kleines Werk vorgelegt, das man wohl am Besten als "Lesebuch zu algebraischen Aspekten der Kryptographie mit öffentlichem Schlüssel'' charakterisieren kann.

Bis Mitte der 70er Jahre (der Autor setzt den Schnitt im Jahr 1976) spielten derartige Verfahren in der Kryptographie im Vergleich zu symmetrischen Verfahren bekanntlich eine untergeordnete Rolle. Dies änderte sich erst unter dem Druck verschiedener Computeranwendungsmöglichkeiten. Die generelle Aufgabenstellung für den Entwurf eines Kryptosystems mit öffentlichem Schlüssel kann man wie folgt formulieren: Es ist eine (injektive) Funktion f : X → Y von der Menge der Quelltexteinheiten X in die Menge Y der verschlüsselten Nachrichteneinheiten zu entwerfen, die für alle x ∈ X einfach zu berechnen ist, für die aber f^-1(y) für die meisten y ∈ im (f) ohne zusätzliche, öffentlich nicht zugängliche Information nicht mit zumutbarem Aufwand zu ermitteln ist. Allerdings soll es eine geheime Zusatzinformation, den privaten Schlüssel, geben, mit dessen Hilfe auch die Umkehraufgabe, das Dechiffrieren, einfach wird.

Viele schwierige mathematische Probleme gaben bisher Anlass für sichere oder vermeintlich sichere Verschlüsselungsverfahren. Die von einer Kryptanalyse zu beantwortenden Fragen sind dabei vor allem komplexitätstheoretischer Natur. Allerdings fortgeschrittener Art, denn die Existenz eines privaten Schlüssels legt die Frage nahe, ob man nicht durch geschickte Kombination öffentlich erzeugbarer Zusatzinformationen diesen Schlüssel doch irgendwie berechnen kann. Die "Code-Knacker'' setzen gerade hier an.

Da sich damit in der Kryptanalyse die gesamte Mathematik wie in einem Brennglas sammelt, wird man in einem Büchlein wie dem des Autors immer nur einen kleinen Ausschnitt dieses großen Gebiets einfangen können. Der Autor hat hierfür drei Themenkreise (Monomsysteme, polynomiale Gleichungssysteme und Verallgemeinerungen des Diffie-Hellman-Verfahrens auf elliptische und hyperelliptische Kurven) mit algebraischem Hintergrund gewählt, die bisher nicht in monographischer Form vorlagen.

Das Buch kann man grob in zwei (auch umfangmäßig etwa gleich große) Teile teilen. Im ersten Teil (Kap. 1 - 3) werden wichtige Begriffe und Zusammenhänge der im Weiteren benötigten mathematischen und kryptographischen Grundlagen erläutert und teilweise bewiesen. Der Umfang dieses Teils ist vor allem einer recht detaillierten Darlegung algorithmischer Aspekte geschuldet. Diese fände man zwar auch anderswo, jedoch gewinnt das Buch damit selbst für fortgeschrittene Studenten eine gewisse Abgeschlossenheit. Ein Teil des Materials wurde (für den fleißigen Leser) in eine Fülle von Übungsaufgaben ausgelagert, zu denen im Anhang Lösungen bzw. Lösungshinweise enthalten sind.

Der erste Teil umfasst im Einzelnen eine Tour durch kryptographische Fragen (Aufgabenstellung und Geschichte; das RSA-Kryptosystem; der Ansatz von Diffie-Hellman zur Verwendung von Logarithmus-Abbildungen; Anwendungen auf digitale Signaturen, Passwörter, Auswertung verdeckter Information), die Diskussion relevanter Komplexitätsklassen (polynomial vs. exponentiell; P, NP und NP-hart; Berechnungsaufgaben mit Zusatzinformationen; probabilistische Verfahren) an Beispielen aus Kombinatorik und Zahlentheorie sowie Fragen aus der Theorie endlicher Körper (Existenz- und Eindeutigkeitssatz; konstruktive Aspekte) und der Polynomringe (bis hin zu Hilberts Nullstellensatz, S-Polynomen und Gröbnerbasen).

Im zweiten Teil wird der Leser, begleitet von Alice, Bob und Catherine, durch die bereits oben genannten drei Themenkreise geführt. Der Autor legt großen Wert auf eine ausführliche und verständliche Darlegung des jeweils betrachteten kryptographischen Verfahrens, das in den zugehörigen Übungsaufgaben weiter vertieft werden kann. Die Kryptanalyse erfolgt in der Regel von einer einfach zu brechenden Variante aus, die sich verstärken, aber mit mehr Einsatz von Mathematik auch wieder brechen lässt. Der dabei gezeichnete Weg führt von einer guten Straße über unebenes Gelände bis hin zum Dickicht moderner Forschungen und (noch) ungelöster Fragen.

Kap. 4 befasst sich mit dem Imai-Matsumoto-System. Die Idee des Systems besteht darin, die Abbildung u → u^h zum Verschlüsseln zu verwenden, wobei u aus einer endlichen Erweiterung von F_q stammt. Zusätzlich werden affine Transformationen vor- und nachgeschaltet, um "die Spuren zu verwischen''. Für geeignete Exponenten h (Summen von wenigen q-Potenzen) lässt sich daraus ein polynomiales Kodierungssystem herleiten. Die Kryptanalyse zeigt, dass in einigen Fällen aus diesen Gleichungen die Existenz bilinearer Gleichungen folgt, die man zum Kodebrechen mit linearer Algebra verwenden kann.

Kap. 5 befasst sich mit dem "Polly Cracker''. Hierbei ist X = F ein Körper und Y = F[T₁,...,T_n] ein Polynomring. Eine Nachricht x ∈ X wird durch ein zufälliges Polynom p ∈ I(B) bzgl. eines (öffentlich bekannten) Polynomsystems B ⊂ Y zu c = x + p verfälscht. Die Dechiffrierung erfolgt mit Kenntnis einer (geheimen) Nullstelle y ∈ Fⁿ von B. Die Kryptanalyse muss also feststellen, wie schwierig es ist, eine solche Nullstelle allein aus den Gleichungen B zu bestimmen. Hierzu werden Gleichungssysteme betrachtet, die sich aus verschiedenen NP-harten kombinatorischen Problemen ableiten lassen, womit das Erstellen eines solchen Systems in P, sein Knacken aber (wahrscheinlich) in NP liegt. Abschließend wird eine Verallgemeinerung des Polly Crackers betrachtet, wo X eine Teilmenge der Standardmonome bzgl. I(B) ist. Der Autor folgt den Argumenten von T. Mora (1993), der vermutet, dass es mit Blick auf intelligente Attacken mit linearer Algebra einen solchen "Krypto-Gröbner'' nicht geben kann.

Kap. 6 ist schließlich Kryptosystemen auf der Basis elliptischer und hyperelliptischer Kurven gewidmet. Diese basieren auf der Idee von Diffie-Hellman, die auf die additive Gruppe der Kurve (im elliptischen Fall) bzw. deren Jacobischer (im hyperelliptischen Fall) angewendet wird. Damit vergrößert sich der Fundus von Gruppen, wo man die Anwendung der genannten Idee studiert hat, beträchtlich. Die Ausführungen beginnen mit einer Zusammenstellung der wichtigsten Fakten aus der Theorie elliptischer Kurven, die im weiteren benötigt werden. Es schließt sich eine ausführliche Erörterung verschiedener Aspekte von Kryptosystemen an, die elliptische Kurven verwenden (subexponentielles Verhalten des Originalverfahrens von Diffie und Hellman für G = F_q^*; Diskreter Logarithmus und "schlechte'' Gruppenordnungen; ECDSA-Verfahren zur digitalen Signatur; Auswahl "guter'' Kurven und Probleme der klassischen Zahlentheorie). Im abschließenden Teil werden die Fragen auf hyperelliptische Kurven übertragen. Wichtigstes neues Problem ist dabei die effiziente Ausführung der Addition auf der Jacobischen, das in einem Anhang ("An Elementary Introduction to Hyperelliptic Curves'' von A. J. Menezes, Yi-Hong Wu und R. J. Zuccherato) abgehandelt wird.

Mit zunehmender Schwierigkeit des Materials werden die Ausführungen dabei skizzenhafter und beschränken sich immer stärker auf den Hinweis auf entsprechende Quellen, was den Charakter eines guten "Lesebuchs'', wie ich es oben bezeichnet habe, ausmachen sollte. Das Buch eignet sich damit selbst für "advanced undergraduates'', wie es im Klappentext heißt, als Einstieg und erster Überblick über ein Gebiet, in dem sich in den letzten Jahren auf überraschende Weise praktische Anwendungsmöglichkeiten für tief innermathematische Themen ergeben haben.

Rezension: Hans-Gert Gräbe (Leipzig) aus Computeralgebra-Rundbrief, Nr. 25 - Oktober 1999

Algorithmische Geometrie

M. Joswig, T. Theobald
Vieweg Verlag, 2008, 266 Seiten, 37,99 €

ISBN 978-3-8348-0281-1

Algorithmische Fragen in der Geometrie erhielten in den letzten Jahrzehnten vor allem durch Anwendungen in der Computergraphik oder bei Optimierungsprobleme eine große Aufmerksamkeit. Das vorliegende Lehrbuch von Joswig und Theobald möchte auf einem auch für Bachelor-Studiengänge geeigneten Niveau in dieses Gebiet einführen.

Das Buch gliedert sich in drei Teile. Der erste behandelt die lineare algorithmische Geometrie. Er beinhaltet zunächst eine kurze Einführung in die projektive Geometrie (die an vielen Stellen im Buch benutzt wird) und studiert dann ausführlicher Polytope und Polyeder. An algorithmischen Fragestellungen werden die lineare Optimierung mit dem Simplex-Algorithmus sowie die Berechnung von konvexen Hüllen, Voronoi-Diagrammen und Delone-Zerlegungen diskutiert.

Der zweite Teil beschäftigt sich mit der nichtlinearen algorithmischen Geometrie, was hier vor allem das Lösen polynomialer Gleichungssysteme mit Gröbnerbasen bedeutet. Dazu werden zunächst die benötigten Grundbegriffe aus kommutativer Algebra und algebraischer Geometrie eingeführt. Dann werden Gröbnerbasen und deren Berechnung mit dem Buchberger-Algorithmus diskutiert. Das Lösen erfolgt schließlich mit Hilfe von Eliminationsidealen (und vereinzelt auch Resultantenmethoden).

Im dritten Teil werden weiterführende Anwendungen angeschnitten. Hier wird als erstes das Problem der Kurvenrekonstruktion studiert. Dann werden einige Fragen zu Geradenkonfigurationen mit Hilfe von Plücker-Koordinaten behandelt. Den Abschluss bilden einige Anwendungen der nichtlinearen Geometrie, wie das direkte kinematische Problem bei Stewart-Plattformen oder das Global Positioning System (GPS).

Laut Klappentext ist das Buch für Studierende ab dem 4. Semester gedacht. Zumindest der erste Teil kann aber sicherlich auch schon im 3. Semester benutzt werden. Der zweite Teil setzt jedoch eine Einführungsvorlesung in Algebra voraus, wie sie typischerweise erst im 3. Semester gehört wird. Die Autoren geben sich große Mühe, alle Beweise auf einem dieser Studienphase angemessenen Niveau zu führen sowie alle Konstruktionen durch nachvollziehbare Anwendungen zu motivieren. Wie es sich für ein ordentliches Lehrbuch gehört, werden alle Kapitel durch Übungsaufgaben ergänzt sowie kurzen ”Anmerkungen“, in denen u. A. auf weiterführende Literatur oder verfügbare Software verwiesen wird. An vielen Stellen werden konkrete Berechnungen in Systemen wie POLYMAKE, SINGULAR oder MAPLE vorgeführt.

Kritisch lässt sich nur wenig anmerken. Wünschenswert wäre ein weiterer Anhang, in dem die verwendeten Konzepte aus der Topologie kurz eingeführt werden, da gerade bei Bachelor-Studierenden nicht unbedingt vorausgesetzt werden kann, dass sie eine Topologie-Vorlesung besucht haben. Da die Autoren verschiedentlich auf Komplexitätsfragen eingehen, verwundert es, dass nicht einmal in den Anmerkungen zum Buchberger-Algorithmus etwas über die praktische Komplexität des Algorithmus zu finden ist. An einigen wenigen Stellen haben sich auch kleine Fehler eingeschlichen, die sich aber leicht korrigieren lassen. Aufgrund eines Fehlers des Verlags ist übrigens der größte Teil der Auflage ohne Inhaltsverzeichnis erschienen; die Autoren stellen auf der Webseite www.mathematik.tu-darmstadt.de/˜joswig/algo/index.html einen Ersatz in Form einer PDF-Datei zur Verfügung.

Insgesamt handelt es sich aber um ein sehr gelungenes und gut lesbares Lehrbuch, das sich in Bachelor- Studiengängen vielfältig einsetzen lässt.

Rezension: Werner M. Seiler, Kassel aus Computeralgebra-Rundbrief, Nr. 45 - Oktober 2009