Leseecke

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

Elliptic Curves
Number Theory and Cryptography

L. C. Washington
Chapman and Hall (CRC), 79,95 $

ISBN 1-584-88365-0

Eines der aktuellsten Bücher über kryptographische Anwendungen elliptischer Kurven ist das Buch I. Blake, G. Serroussi, N. Smart: Elliptic Curves in Cryptography, Cambridge Univ. Press 1999. In dessen Vorwort wird aber festgestellt: ”We try and give a flavour of the mathematics involved for those who are interested. We decided however not to include most proofs since that not only would dramatically increase the size of the book but also would not serve its main purpose.“

Das vorliegende Buch schließt diese Lücke. In den Kapiteln 1 bis 4 wird die elementare Theorie der elliptischen Kurven entwickelt. Dies beinhaltet Grundlagen, Torsionspunkte sowie elliptische Kurven über endlichen Körpern (inklusive Schoof-Algorithmus etc.)

In den darauf folgenden Kapiteln 5 und 6 werden die wesentlichen kryptographischen Algorithmen und Attacken kurz und präzise beschrieben und durch Beispiele unterlegt. (Komplexitätsaussagen werden allerdings nicht bewiesen.) Kapitel 7 enthält die auf der EC-Methode beruhenden Fundamentalalgorithmen zur Primzerlegung und Primzahlerkennung. Die tieferen für die genannten Algorithmen benötigten Resultate über elliptische Kurven, dies sind komplexe Multiplikation, Hasse- und Tate-Lichtenbaum-Paarung, Zetafunktion und Hasse-Weil-Schranke, werden in den Kapiteln 10 bis 12 bewiesen.

Daneben geht das Buch noch auf einige zahlentheoretische Fragestellungen ein, wie etwa die Gruppe der rationalen Punkte in Kapitel 8. Es werden der Satz von Mordell-Weil bewiesen und die Tate-Shafarevich-Gruppe eingeführt. Im letzten Kapitel 13 schließlich wird ein kurzer Überblick über den Beweis des fermatschen Satzes von Wiles gegeben, bei dem die Theorie der elliptischen Kurven eine tragende Rolle spielt.

Bei der vorliegenden Monographie handelt es sich also um ein Buch über elliptische Kurven mit Ausrichtung auf die Bedürfnisse der Computeralgebra. Unter den Anwendern ist es dabei vor allem für diejenigen von Interesse, die nicht nur die Algorithmen, sondern (insbesondere) auch die zugrunde liegende Theorie kennen lernen möchten. Es stellt daher eine sehr willkommene Ergänzung bzw. Grundlage für Bücher wie das eingangs erwähnte dar.

Ich halte das Buch für sehr geeignet sowohl zum (vertiefenden) Selbststudium von Kryptologen etc. als auch als Begleitlektüre für (Computeralgebra-) Vorlesungen wie elliptische Kurven mit Anwendungen.

Rezension: B. Heinrich Matzat (Heidelberg) aus Computeralgebra-Rundbrief, Nr. 35 - Oktober 2004