Leseecke

Numerical Polynomial Algebra

H. Stetter
SIAM, Philadelphia 2004, xv + 472 Seiten, 109,55 €

ISBN 0-898-71557-1

Die Bezeichnung Numerical Polynomial Algebra steht für ein noch recht junges und sich schnell entwickelndes Teilgebiet der Mathematik an der Schnittstelle zwischen der Computeralgebra und der numerischen Mathematik. Wie kann man nichtlineare algebraische Probleme mit Hilfe approximativer Methoden lösen? Kann man klassische Probleme der numerischen Mathematik mit Verfahren der modernen symbolischen Berechnung behandeln?

Das vorliegende Buch von Hans Stetter erscheint zu einem idealen Zeitpunkt in dieser Entwicklung. Es ist geradezu prädestiniert, das Standardreferenzwerk auf diesem neuen Gebiet zu werden. Auf über 450 Seiten legt Stetter die Grundlagen für die Teile der Mathematik, die den kommenden numerisch-symbolisch rechnenden Computeralgebrasystemen zu Grunde liegen. Ausgehend von Polynomen und Polynomidealen in P = K[x₁, . . . , x_n] mit K = R/C betrachtet er zunächst das klassische Problem des Lösens algebraischer Gleichungssysteme und erklärt, wie man es mit Gröbner-Basen und Randbasen angehen kann. Dabei nimmt er von vornherein den Standpunkt ein, dass man ein Polynomideal I am besten über den Restklassenring P/I beschreibt. Das Central Theorem ist dabei nichts anderes als die Beschreibung der Methode, die anderswo auch als das Verfahren von Auzinger und Stetter bezeichnet wird. Weitere wichtige Themen im grundlegenden ersten Kapitel Polynomials and Numerical Analysis sind eine sorgfältige Definition empirischer Polynome (also von Polynomen mit Koeffizienten, die Rundungswerte sind) sowie eine Diskussion verschiedener Methoden, um mit solchen empirischen Polynomen zu rechnen und die numerische Stabilität dieser Berechnungen zu beurteilen.

Danach behandelt Kapitel II den univariaten Fall. Hier gibt es bereits eine Menge klassischer Ergebnisse der numerischen Analysis, wie die univariate Polynominterpolation oder die Sensibilitätsanalyse der Polynomdivision. Ein in den letzten 15 Jahren aktives Forschungsthema ist die Berechnung des größten gemeinsamen Teilers zweier univariater empirischer Polynome. Auch das Problem der Isolation der Nullstellen kommt zur Sprache. Diese Themen kann der Leser über die Historical and Bibliographical Notes und die kapitelweisen References leicht selbst weiter vertiefen.

Den Kern des Buchs bildet Kapitel III, wo Stetter die Grundlagen einer Theorie der multivariaten empirischen Polynome und Polynomideale entwickelt. Nach einem kurzen Ausflug in die Problematik der numerischen Behandlung einzelner multivariater Polynome (z. B. die numerische Faktorisierung) geht er ausführlich auf die von ihm mitbegründete und entwickelte Theorie der Randbasen 0-dimensionaler Polynomideale ein. Hierbei bedeutet ”0-dimensional“, dass das Ideal nur endlich viele komplexe Nullstellen besitzt. Solche Polynomideale I werden mit Hilfe des Restklassenrings P/I und mit Hilfe von Randbasen studiert; das Kapitel gibt u. A. Auskunft über die Berechnung der Anzahl und der Vielfachheit der Nullstellen, die numerische Berechnung einer Randbasis oder Gröbner-Basis von I sowie einer Basis von P/I, über die ”duale Darstellung“ mit Hilfe von Linearformen und über die Bestimmung der Syzygien einer Randbasis. Viele dieser Resultate sind hier erstmals in Buchform aufgeschrieben.

Das abschließende Kapitel behandelt positivdimensionale polynomiale Systeme. Dabei schlägt Stetter verschiedene Ansätze vor, die Methoden aus Kapitel III auf nicht 0-dimensionale Situationen zu übertragen. Die Entwicklung solcher Theorien ist noch nicht abgeschlossen, so dass seine Ausführungen als Vorschläge und Anregungen zu interpretieren sind, die mit geeigneten Beispielen untermauert werden.

Das gesamte Buch ist sehr lebendig und direkt geschrieben. Überall finden sich Zahlenbeispiele, Übungsaufgaben, geschichtliche Bemerkungen und Literaturhinweise. Der Text liest sich flüssig und die Notationen sind angenehm einheitlich. Somit kann das Buch jedem Mathematiker empfohlen werden, der in dieses aktuelle Gebiet eindringen möchte. Es ist auch als Grundlage für Vorlesungen im Haupt- bzw. Master-Studium geeignet. Der Preis für SIAM-Mitglieder beträgt $ 64,75 und ist daher recht moderat.

Rezension: Martin Kreuzer (Dortmund) aus Computeralgebra-Rundbrief, Nr. 40 - März 2007

Hypergeometric Summation
An Algorithmic Approach to Summation and Special Function Identities

Wolfram Koepf
Springer, 300 Seiten, 2014, 2. Aufl., 53,49 €

ISBN: 1-447-16463-6

Aufgaben wie die explizite oder rekursive Auswertung von Summen von Binomialkoeffizienten (allgemeiner: hypergeometrischen Termen) oder der Nachweis der Gleichheit von solchen Summen (Binomialidentitäten) treten in vielen Bereichen der Mathematik auf und haben in der Vergangenheit auch erfahrenen "Rechnern'' notorische Probleme bereitet. Seit etwas weniger als zehn Jahren hat die Behandlung dieses Problems der definiten hypergeometrischen Summation, beginnend mit den Arbeiten von Doron Zeilberger, eine neue, algorithmische Qualität gewonnen. Vieles, wofür man früher Erfahrung, Intelligenz, Hartnäckigkeit, Tafeln von bekannten Auswertungen und Transformationen und auch Glück benötigte, kann nun "automatisch'', also algorithmisch, erledigt werden. Protagonisten dieser raschen Entwicklung waren neben Zeilberger u.a. Herbert Wilf und Marko Petkovsek, und diese drei Autoren haben in dem 1996 erschienenen Buch mit dem vielsagenden (?) Titel "A=B'' (A.K. Peters, Wellesley) eine erste zusammenfassende Darstellung gegeben, die neben anderen Qualitäten auch den authentischen Charme der Pionierarbeit hat.

Das vorliegende Buch von W. Koepf, der vor allem auch durch seine Implementierungen zur Verbreitung dieses Fortschritts beigetragen hat, deckt in der mathematisch-algorithmischen Substanz in etwa den gleichen Themenkreis wie "A=B'' ab. Die Basisalgorithmen (also die Technik von Sister Celine, Gospers Methode der indefiniten hypergeometrischen Summation, der WZ-Ansatz, Zeilbergers kreatives Teleskopieren, die Bestimmung der hypergeometrischen Lösungen von linearen Differenzengleichungen mit polynomialen Koeffizienten nach Petkovsek) werden ausführlich behandelt. Viele Varianten und Erweiterungen (Mehrfachsummen, q-Analoga, Faktorisierungen von Operatoren, analoge Techniken für Integrationsprobleme etc.) werden in unterschiedlichem Detaillierungsgrad angesprochen, so wie das für einen Text mit dieser Ausrichtung sinnvoll und angemessen ist.

Was dieses Buch auszeichnet, ist einerseits die jederzeit greifbare Nähe zur konkreten (Maple-)Implementierung, andererseits die Fülle von Beispielen, Anwendungen und Aufgaben, wobei der Verfasser, mehr noch als die Autoren von "A=B'', auf den riesigen Fundus von Anwendungsmöglichkeiten im Bereich der "speziellen Funktionen'' (im Sinne von Sektion 33 der Mathematical Reviews) zurückgreift.

Es war die ausgesprochene Absicht des Verfassers, einen Text vorzulegen, der als Basis von Seminaren oder Vorlesungen den Einstieg in diesen faszinierenden Bereich der Computeralgebra motiviert und unterstützt. Das ist ihm, so meine ich, rundum gelungen.

Bem.: Revidierte Versionen der Maple packages "hsum.mpl'' und "qsum.mpl'' mit Implementierungen der in diesem Buch behandelten Algorithmen sind auf der Webseite http://www.mathematik.uni-kassel.de/~koepf/Publikationen zu finden.

Rezension: Volker Strehl (Erlangen) aus Computeralgebra-Rundbrief, Nr. 23 - Oktober 1998

Mathematics Unlimited
2001 and Beyond

Björn Engquist, Wilfried Schmid (Herausgeber)
Springer Verlag, Berlin, Heidelberg, New York, 2001, 1236 Seiten, 59,95 $

ISBN 3-540-66913-2

Dieses Buch wurde speziell zum Millenniumswechsel aufgelegt und soll den Stand der mathematischen Forschung zu Beginn des dritten Jahrtausends festhalten. Gleich vorneweg möchte ich sagen, dass das Buch diesen Zweck m. E. ohne Einschränkung erfüllt.

Auf Grund des Umfangs des vorliegenden Buchs möchte ich mich in diesem Referat allerdings auf eine kurze Beschreibung derjenigen Artikel beschränken, die sich mit Themen der Computeralgebra beschäftigen. Das ist angesichts des Leserkreises des Rundbriefs naturgemäß angemessen.

Man sollte annehmen, dass Computeralgebra als eine moderne computerorientierte Wissenschaft in diesem Buch eine wichtige Rolle spielen wird. Und in der Tat werden wir nicht enttäuscht. Eine beträchtliche Anzahl der Artikel des Bandes beschäftigt sich mit Themen, die sich hier einordnen lassen. Es handelt sich hierbei um mindestens 10 von insgesamt 63 Artikeln, die ich nun kurz beschreiben will.

David H. Bailey, Jonathan M. Borwein: Experimental Mathematics: Recent Developments and Future Outlook.
Computeralgebrasysteme ermöglichen mathematische Experimente. In diesem Artikel werden insbesondere Algorithmen behandelt, mit denen sich ganzzahlige Beziehungen zwischen gegebenen reellen oder komplexen Zahlen auffinden lassen. Hierbei spielt insbesondere der berühmte LLL-Gitterreduktions-Algorithmus eine Rolle. Ein Resultat derartiger Berechnungen ist die Darstellung

mit welcher jede hexadezimale (und damit auch jede binäre) Ziffer von π einzeln - ohne Kenntnis der Vorgängerziffern - berechnet werden kann. Diese Identität wurde mit den erwähnten Methoden erst in den 1990ern entdeckt. Natürlich wurde Formel (1) dazu verwendet, Rekordbinärziffern von π zu berechnen.

Die Autoren liefern weitere Beispiele von Ergebnissen, welche mit dieser Methode gefunden wurden. Schließlich geben sie ein warnendes Beispiel, dass nicht jede experimentelle Vermutung auch stimmen muss: Während für k = 0,...,5

ist, ist für k = 6

Dies weicht nur um 10^-11 von π/2 ab!

Achtung: Dieser Artikel wurde offenbar per e-mail übermittelt und enthält einige Schreibfehler, die vom e-mail-Transport herrühren.

Arjeh M. Cohen: Communicating Mathematics Across the Web.
In diesem Artikel kommt das Wort Computeralgebra bereits in der Einleitung vor. Der Autor entwickelt an der Fragestellung der mathematischen Kommunikation mit verschiedenen Computeralgebrasystemen das Bedürfnis nach einer Metasprache. Beispielsweise gibt er konkrete Beispiele von teilweise falschen Ergebnissen bestimmter Computeralgebrasysteme, welche es wünschenswert erscheinen lassen, Probleme interaktiv von mehreren Systemen gleichzeitig lösen zu lassen. Dies führt zum OpenMath-Projekt.

Der Autor führt aus, wie eine Kombination von Computeralgebra und Fehlerkontrolle am besten über das World Wide Web realisiert werden kann, und gibt schließlich einen Überblick über das OpenMath-Projekt.

Henri Cohen: Computational Aspects of Number Theory.
Zahlentheorie hat sich seit der Entdeckung asymmetrischer Verschlüsselungsverfahren von einer Disziplin der reinen Mathematik zu einem anwendungsorientierten Fachgebiet hin entwickelt. Diese Entwicklung geht einher mit der größeren Leistungsfähigkeit heutiger Computer, welche algorithmische Rechnungen begünstigen.

Die Sicherheit von Verschlüsselungsverfahren wie dem RSA-Verfahren hängt essentiell mit der Schwierigkeit zusammen, große natürliche Zahlen zu faktorisieren. Gute Faktorisierungsalgorithmen können das RSA-Verfahren brechen. Daher gibt es einen Forschungsboom auf diesem Gebiet mit z. T. durchaus erstaunlichen Ergebnissen. Über derartige Methoden wird ein historischer Überblick gegeben.

Es werden zunächst Primzahltests behandelt. Nach dem Fermattest wird die Benutzung zyklotomischer Körper und elliptischer Kurven betrachtet. Es folgen Faktorisierungsmethoden: der Pollardsche -Test, Shanks Babystep-Giantstep-Methode, Lenstras Elliptische-Kurven-Methode, Pollards p-1-Methode, Faktorbasen sowie Zahlkörpermethoden.

Nach Einführung quadratischer Körper werden weitere moderne zahlentheoretische Algorithmen betrachtet. Der LLL-Algorithmus eignet sich - wie im Beitrag von Bailey und Borwein gesehen - zur Bestimmung Q-linearer Abhängigkeiten, läßt sich auch zur Idealreduktion einsetzen und ist für die Faktorisierung von Polynomen von Bedeutung. Algorithmen zur Bestimmung der Anzahl der Punkte elliptischer Kurven über endlichen Körpern folgen. Die Arbeit schließt mit einer Liste Some Challenges for the Twenty-First Century.

Oded Goldreich: Computational Complexity.
Die Möglichkeit, mathematische Algorithmen in Computerprogramme umzusetzen, hat zum Entstehen des Gebiets der Komplexitätstheorie geführt. Der Autor spricht über den Begriff der Berechenbarkeit, über Turingmaschinen und über Effizienz. Es wird genau erklärt, was ein polynomialer Algorithmus ist. Die Komplexitätsklassen P und NP werden eingeführt und die Frage P ≠ NP wird diskutiert. NP-vollständige Probleme werden erörtert. Der Autor macht klar, dass es genau dann Einwegfunktionen gibt - welche Kryptosysteme wie RSA erst sicher machen -, falls die zentrale Vermutung P ≠ NP richtig ist. Diese Zusammenhänge zwischen der Komplexitätstheorie und der Kryptographie werden eingehend untersucht.

Neal Koblitz: Cryptography.
Die Kryptographie wurde 1976 durch die Einführung des Konzepts eines asymmetrischen Verschlüsselungsverfahrens durch Diffie und Hellman revolutioniert. Rivest, Shamir und Adleman entwickelten 1978 als erste ein solches Verfahren, das RSA-Verfahren. Dieses Verfahren wird ausführlich behandelt, Hashfunktionen sowie digitale Signaturen werden eingeführt. Diskrete Logarithmen, das Diffie-Hellmansche Schlüsselaustauschverfahren und der digitale Signatur-Algorithmus (DSA) werden behandelt. Das Rechnen in elliptischen Kurven macht asymmetrische Verschlüsselungsverfahren häufig sicherer.

Schließlich wird die Kryptoanalyse, also das Brechen kryptographischer Verfahren, betrachtet, welche im Falle des RSA-Algorithmus auf die Faktorisierung großer ganzer Zahlen hinausläuft. Das Zahlkörpersieb wird vorgestellt und der Xedni-Algorithmus wird betrachtet. Abschließende Bemerkungen über die Forschungskultur in der Kryptographie beruhen auf Erfahrungen des Autors, welche durchaus zu denken geben.

Maxim Kontsevich, Don Zagier: Periods.
Die algebraischen Zahlen A bilden üblicherweise die höchste Stufe in der Hierarchie endlich darstellbarer komplexer Zahlen:

In dieser Arbeit wird zwischen A und C noch eine weitere Hierarchie eingefügt, die also auch transzendente Zahlen enthält, welche sich aber dennoch geeignet endlich darstellen lassen, die sogenannten Perioden. Eine Zahl heißt eine Periode, falls sich ihr Real- und ihr Imaginärteil jeweils durch absolut konvergente bestimmte Integrale rationaler Funktionen mit rationalen Koeffizienten darstellen lassen, mit Integrationsgebieten in Rⁿ, welche durch polynomiale Ungleichungen mit rationalen Koeffizienten beschrieben werden. Es zeigt sich sofort, dass algebraische Zahlen Perioden sind.

Aber auch die transzendente Zahl

ist eine Periode, während vermutet wird, dass die Eulersche Zahl e keine Periode ist. Es gibt aber viele weitere Perioden: Logarithmen algebraischer Zahlen, elliptische Integrale oder auch

Man kann zeigen, dass die Menge der Perioden eine Algebra bildet, Summe und Produkt von Perioden sind also wieder Perioden.

Der sehr interessante Artikel untersucht Identitäten zwischen Perioden und stellt Perioden mit Differentialgleichungen und L-Funktionen in Zusammenhang.

Hans Petter Langtangen, Aslad Tveito: How Should We Prepare the Students of Science and Technology for a Life in the Computer Age?
Heutige mathematische Software macht die Nutzung numerischer Tafeln obsolet und ermöglicht Unterricht auf höherem Niveau als früher. Dies wird aber leider noch weitgehend ignoriert. Der Autor fordert eine völlige Umorientierung des Lehrbetriebs. Im Gegensatz zum Status Quo dürfen die Studenten erwarten, vom ersten Studientag an mit modernster Computertechnologie unter Berücksichtigung realistischer Fragestellungen aus den Anwendungen vertraut gemacht zu werden. Die Analysisausbildung profitiert aus numerischen Experimenten zu den Begriffen Differentiation, Integration, gewöhnliche Differentialgleichungen, Grenzwerte, Newtonverfahren. Graphische Darstellungen runden das Bild ab. Einige dieser Beispiele werden ausgeführt und die zentrale Rolle, die mathematische Software bei der Ausbildung spielen kann, wird erarbeitet.

Leider beschäftigt sich dieser Artikel - trotz des allgemein gehaltenen Titels - praktisch ausschließlich mit numerischen Fragestellungen, obwohl die Systeme Mathematica und Maple neben Matlab durchaus genannt werden.

Yiannis N. Moschovakis: What Is an Algorithm?
Algorithmen werden in einem allgemeinen informatischen Framework meist im Zusammenhang mit Rechenmaschinen, beispielsweise Turingmaschinen, erklärt. Dies ist nicht sonderlich intuitiv. Unsere intuitive Vorstellung eines Algorithmus ist eher die einer rekursiven Definition, während das Maschinenmodell auf Implementierungen, welche spezielle Algorithmen darstellen, abzielt.

Während heute kaum jemand an der Gültigkeit der Church-Turingschen These ,,Eine Funktion f : N → N ist berechenbar genau dann, wenn sie von einer Turingmaschine berechnet werden kann'' zweifelt, so stellt der Autor jedoch heraus, dass beispielsweise wichtige Aspekte der Komplexitätstheorie von der Theorie der Turingmaschinen nicht erfasst werden.

In dem vorliegenden Artikel wird eine möglichst weitgehende Definition einer Rechenmaschine gegeben. Am Beispiel des Sortierens wird gezeigt, dass Maschinenmodelle Komplexitätsfragen unzureichend beantworten können. Dann werden stetige rekursive Definitionen und Algorithmen behandelt. Unstetige Algorithmen runden das Bild ab. Der Artikel schließt mit einer Liste von Problemen im Zusammenhang mit der Definition eines Algorithmus.

Gerard van der Geer: Error-Correcting Codes and Curves over Finite Fields.
Der Artikel beginnt mit den endlichen Körpern F_q, es werden algebraische Kurven erklärt und Kurven über endlichen Körpern betrachtet. Die Frage nach der Anzahl der Punkte einer Kurve über einem endlichen Körper schließt sich an.

Fehlerkorrigierende Codes und Hamming-Abstand werden eingeführt, und es folgen einige Beispielklassen solcher Codes mit ihren Eigenschaften.

Jan van Leeuwen, Jiri Wiedermann: The Turing Machine Paradigm in Contemporary Computing.
In diesem Artikel wird beschrieben, warum die Nutzung heutiger Computer nicht mehr vollständig durch Turingmaschinen beschrieben werden kann. Hierzu wird zunächst ausführlich erklärt, was eine Turingmaschine ist, und es wird gezeigt, dass die folgenden Eigenschaften moderner Computertechnologie diesem Paradigma nicht entsprechen:

• non-uniformity of programs (Softwareupgrades etc. lassen sich nicht durch endliche Programme beschreiben)
• interaction of machines (z. B. über das Internet vernetzte Computer)
• infinity of operation (Input- und Outputdaten strömen permanent)

und zwar treten diese Effekte alle gleichzeitig auf. In diesem Sinne ist auch die Church-Turingsche These heute nicht mehr gültig. Man beachte, dass dies hauptsächlich den zugrundeliegenden Begriff der Berechenbarkeit berührt.

Der Autor gibt zwei Modelle einer erweiterten Turingmaschine, welche auch den Begriff des Orakels erweitert, nämlich die site machine bzw. die interactive Turing machine with advice. Diese Konzepte sind im wesentlichen gleichwertig und lassen eine Beschreibung der obigen Effekte zu. Aus diesem neuen Paradigma ergibt sich eine Neuformulierung der Church-Turingschen These.

Man möge mir nachsehen, wenn ich diese Auswahl nach persönlichen Gesichtspunkten getroffen habe und Ihr Lieblingsbeitrag fehlen sollte.

Zusammenfassend lässt sich sagen, dass das referierte Buch für mich kaum einen Wunsch offenlässt. Nur eines möchte ich bemängeln: Das Buch ist so dick - dicker als jedes andere Buch, das ich kenne - dass ich dieses Referat nur schreiben konnte, weil ich die mich interessierenden Artikel kopierte (das Buch lässt sich wegen seiner Dicke auch noch extrem schlecht kopieren!). Das Gesamtwerk ist nämlich praktisch überhaupt nicht transportabel. Da tröstet auch der wirklich extrem günstige Preis nicht darüber weg.

Rezension: Wolfram Koepf (Kassel) aus Computeralgebra-Rundbrief, Nr. 29 - Oktober 2001

Handbook of elliptic and hyperelliptic curve cryptography

H. Cohen, G. Frey et al.
Chapman & Hall Verlag, 2006, 848 Seiten, 86,90 €

ISBN 1-584-88518-1

Das vorliegende Buch ist mit über 800 Seiten ein sehr umfangreiches Werk, welches sich mit (fast) allen Aspekten der auf elliptischen und hyperelliptischen Kurven basierenden Kryptographie beschäftigt. Die Hauptautoren sind Roberto M. Avanzi, Henri Cohen, Christophe Doche, Gerhard Frey, Tanja Lange, Kim Nguyen und Frederik Vercauteren. Weitere acht Personen sind mit Beiträgen in geringerem Umfang vertreten.

Das Buch richtet sich sowohl an Studierende als auch an professionelle Mathematiker, Informatiker und Elektrotechniker, die sich mit dem Thema zu Forschungs- und Entwicklungszwecken auseinandersetzen möchten. Es untergliedert sich im Wesentlichen in vier Teile: 1. Mathematische Grundlagen (140 Seiten). 2. Arithmetik in den ganzen Zahlen, endlichen Körpern und p-adischen Körpern, Arithmetik für elliptische und hyperelliptische Kurven, Paarungen, Methoden zum Punktezählen, Angriffe auf das diskrete Logarithmusproblem (400 Seiten). 3. Anwendungen, darunter Zusammenfassung und Einordnung der Aspekte des zweiten Teils, Parameterwahl, paarungsbasierte Kryptographie, Primzahltests und Faktorisierung ganzer Zahlen (70 Seiten). 4. Praxisaspekte, speziell Einsatz und Angriffe bei Chipkarten, Zufallszahlenerzeugung (120 Seiten). Themen, die nicht oder nur am Rande behandelt werden, sind beispielsweise Quantenalgorithmen, kryptographische Protokolle und Standards, Patente, gesetzliche Regelungen.

Das Hauptaugenmerk ist damit auf die gegenwärtig relevanten mathematischen und algorithmischen Grundlagen gerichtet. Ein Großteil der Forschung der letzten 15 Jahre in diesem Gebiet wird in der Tat im vorliegenden Buch zusammengefasst. Da sich der Forschungsstand, vornehmlich hyperelliptische Kurven und Paarungen beziehungsweise paarungsbasierte Kryptographie betreffend, noch zügig weiterentwickelt, werden die entsprechenden Teile des Buchs relativ schnell veralten (oder sind bereits etwas veraltet).

Die Darstellung ist im Allgemeinen knapp, aber detailliert gehalten. Die Autoren haben Wert darauf gelegt, die relevanten Definitionen und Sätze möglichst vollständig aufzunehmen, so dass das Buch in sich vergleichsweise abgeschlossen ist. Für Beweise wird jedoch auf die entsprechende Literatur verwiesen. Ein zentraler Bestandteil sind die zahlreichen Algorithmen, die in relativ implementationsnaher Form beschrieben werden. Auf Übungsaufgaben wurde verzichtet, allerdings befinden sich viele Beispiele im Text. Darüber hinaus sind die einzelnen Kapitel so verfasst worden, dass die aus vorhergehenden Abschnitten benötigten Ergebnisse und die Notation eingangs kurz wiederholt werden und so Quereinstiege in den Text erleichtert werden. Trotz der großen Anzahl an Autoren ist der Text einheitlich gehalten.

Der Hauptnutzen des Buchs ist zusammenfassend darin zu sehen, dass es dem Leser die Möglichkeit bietet, sich effizient über die für die oben genannten Teilgebiete relevanten Aspekte, Zusammenhänge und Literaturreferenzen zu informieren. Als reines Lehrbuch dürfte es sich dagegen weniger eignen.

Die Webseite des Buchs ist http://www.hyperelliptic.org/HEHCC/. Hier können neben Inhaltsverzeichnis und Bibliographie ein monatlich wechselndes Kapitel heruntergeladen werden.

Rezension: Florian Heß (Berlin) aus Computeralgebra-Rundbrief, Nr. 40 - März 2007

Kryptografie in Theorie und Praxis
Mathematische Grundlagen für Internetsicherheit, Mobilfunk und Elektronisches Geld

Albrecht Beutelspacher, Heike B. Neumann, Thomas Schwarzpaul
Vieweg+Teubner Verlag, 2010, 324 Seiten, 26,95 €

ISBN 978-3-8348-0977-3

Der Untertitel des Buches lautet „Mathematische Grundlagen für Internetsicherheit, Mobilfunk und elektronisches Geld“. Ein Blick ins Inhaltsverzeichnis, das sich in die Teile Symmetrische Verschlüsselungen, Asymmetrische Verschlüsselungen und Anwendungen gliedert, bestätigt, dass das Buch eine enorme Breite an Themen abdecken und dabei keinen Verzicht üben will. So findet man hier auch Stromchiffren, Pseudo- Zufallsgeneratoren mit Schieberegistern, Kryptographische Zufallsgeneratoren von Blum-Micali und Blum- Blum-Shub, Statistische Tests, Blockchiffren DES und AES, Elliptische Kurven sowie Kryptosysteme, die auf Codes oder kombinatorischen Problemen beruhen. Damit ist aber nur etwas mehr als die Hälfte des Buches gefüllt, denn der weitaus größte Teil ist den Anwendungen vorbehalten. In diesem Abschnitt geht es um Authentizität von Nachrichten, Zero-Knowledge- Protokolle, Schlüsselinfrastrukturen und Authentifizierung von Teilnehmern, Secret-Sharing, Anonymität, bis hin zur Sicherheit von Internet-Standards, Mobilfunk und zur Quantenkryptografie.

Diese Themen werden auch tatsächlich angesprochen, allerdings bleibt das Buch dabei verständlicherweise an der Oberfläche. Mathematische Grundlagen findet man nur zu einem gewissen Teil, und wenn sie vorhanden sind, ist der Grad der Vertiefung eher inkonsistent. So startet das Buch z. B. mit hohem Anspruch an mathematische Präzision, wenn etwa das Sicherheitskonzept der Ununterscheidbarkeit mit Hilfe von Komplexitätstheorie, Erfolgswahrscheinlichkeiten von Angreifern und (asymptotisch) vernachlässigbaren Funktionen eingeführt wird, wie man es aus Goldreichs Foundations of Cryptography erwarten würde. Wenige Seiten später wird auf einen dreizeiligen Beweis der Bayes-Formel verzichtet und stattdessen ein Lehrbuch der Stochastik zitiert.

Dass verschiedene Grundlagen nicht bewiesen werden, zieht sich durch das ganze Buch. Wenn statt eines trivialen Beweises ein Lehrbuch zitiert wird, ist das nicht schön, aber verkraftbar. Wenn gar keine Referenzen gegeben werden (und das kommt vor), hat ein unbedarfter Leser allerdings keine Chance einzuschätzen, ob hier nur eine Kleinigkeit fehlt oder etwas Substanzielles. Hinzu kommt eine gewisse Frustration mit gelegentlich schlampiger mathematischer Darstellung. Bereits im Kapitel über Schieberegister, der ersten Gelegenheit zu etwas technischeren Rechnungen, stolpert man über vergessene Voraussetzungen in Definitionen und Bemerkungen. Da das Buch fast alles anspricht – ein Thema, das ausgespart wurde, sind Faktorisierungsmethoden – wird auch auf forschungsrelevante Themen eingegangen. Erstaunlicherweise sind gerade hier die Literaturverweise recht ausführlich, so dass das Buch über ein langes Verzeichnis an Zeitschriften- und Konferenzartikeln verfügt.

Vom Stil her versuchen die Autoren möglichst leicht verständlich und textorientiert zu erklären. Dies geht zu Lasten der Übersicht und zu Lasten des Tiefgangs. Je nach Geschmack kann der Stil entweder leicht zugänglich erscheinen, oder aber auch der Verständlichkeit selbst abträglich sein. Mit Wiederholungen ist zu rechnen.

Als Zielgruppe des Buches kommen Leser in Frage, die sich einen erstmaligen Überblick über Kryptografie und ihre aktuellen Anwendungen verschaffen wollen und dabei weniger Wert auf Beweise legen. Für diese ist das Buch leicht zugänglich und besticht sicherlich durch seine enorme Themenabdeckung. In der mathematischen Darstellung gibt es dagegen bessere Bücher.

Rezension: Timo Hanke (Aachen) aus Computeralgebra-Rundbrief, Nr. 47 - Oktober 2010