Leseecke

Die Entstehung der Knotentheorie
Kontexte und Konstruktionen einer modernen mathematischen Theorie

Moritz Epple
Vieweg Verlag, 1999, 449 Seiten, 52,00 €

ISBN 3-528-06787-X

Knotenpraxis kennen wir alle vom Schuhebinden, einige vom Segeln oder Bergsteigen. Angesichts der Vielfachheit der Knoten als "verknotete oder verschlungene Raumkurven" ist es nicht erstaunlich, dass sich die Beschäftigung mit ihnen ab dem Ende des 18. Jahrhunderts zu einer eigenen mathematischen Theorie "verknotete", die dann im 20. Jahrhundert als Knotentheorie etablierte Teildisziplin der Topologie wurde.

Dieses Buch zeichnet diese Geschichte nach. Sie beginnt bei der Leibnizschen Idee einer von der Größe unabhängigen "Analysis situs" (oder "Geometria situs"), der ersten Mathematisierung von Verkettungen und Knoten durch Gauß und führt über Kelvins auf Knoten basierenden Atomtheorie und Maxwells Klassifikationssystem schließlich zur Re-Mathematisierung der Knoten in der Mathematik des 20. und 21. Jahrhunderts. Dabei ist etwa die Hälfte des Buches der modernen Mathematik gewidmet, so dass man wohl behaupten kann, dieses Buch erfüllt auch seinen zweiten Anspruch, nämlich die Konstruktion dieser Theorie, was sie heute ist, mitzuerleben.

Der Umfang (und Anspruch) des Buches lässt es schließlich auch zu, dass zu diesem Zweck die Entstehung der Topologie als eigenständige Disziplin entwickelt wird. In den letzten beiden Jahrhunderten treten dann diejenigen Namen auf, die man entweder eineindeutig anderen Disziplinen zuordnet oder gänzlich unbekannt sind: Poincaré, Dehn, Heegard, Wirtinger, Tietze, Reidemeister, Alexander. Es gibt also einiges zur Ehre dieser neuen alten Disziplin nachzuholen. Wer diese Einladung annimmt, wird auch am Literaturverzeichnis seine Frende haben.

Mit diesem Buch sollten also alle eingefangen sein, die ein allgemeines Interesse an der Geschichte der Mathematik haben, ohne auf die dahinter- oder besser darinsteckende Mathematik verzichten zu wollen. Deshalb ist es auch nur symbolisch zu verstehen, dass Epple diejenigen Passagen, die höhere Mathematik voraussetzen, mit einem ª gekennzeichnet hat - denn selbst wer diese wenigen Passagen übergeht, wird einen reichen Fundus an Mathematik mit nach Hause nehmen können. Man kann also sagen: Dieses Buch ist Knotentheorie mit allem was dazugehört.

(Rezension: Mark Krüger)

Diophantine Equations and Power Integral Bases

I. Gáal
Birkhäuser Verlag, Basel, Boston, Berlin, 2002, 282 Seiten, 55,14 €

ISBN 0-8176-4271-4

Das vorliegende Buch führt in den aktuellen Stand der Forschung auf dem Gebiet der algorithmischen Berechnung von Indexformgleichungen. Mit der Hilfe von Indexformgleichungen kann man entscheiden, ob der Ring der ganzen Zahlen eines Zahlkörpers vom Grad n eine Potenzganzheitsbasis besitzt, d. h. als Z–Modul von 1, α, α², . . . , α^n–1 erzeugt wird. Während diese Frage bei quadratischen Körpern immer eine positive Antwort besitzt, gibt es bereits bei kubischen Körpern negative Beispiele. Die Berechnung eines solchen Elements α geht über eine sogenannte Indexformgleichung. Diese diophantische Gleichung hat im Allgemeinen n – 1 Unbekannte und Grad n(n–1)/2. Daher ist die Lösung allgemeiner Indexformgleichungen von hohem Grad ein äußerst schwieriges Problem.

Die Lösung von Indexformgleichungen kann in vielen Fällen auf andere diophantische Gleichungen zurückgeführt werden. Daher führt der Autor den Leser in die Behandlung von Einheiten-, Thue- und Normformgleichungen ein. Hier werden die wichtigsten Methoden kurz vorgestellt. An mehreren Stellen gibt es ausführliche Beispiele, die einerseits das Verständnis fördern, andererseits aber auch die Effizienz der neuen Methoden zeigen. Dieser Teil des Buches hat Übersichtscharakter, d. h. dass einige Beweise zitiert werden.

In der zweiten Hälfte des Buches werden die Indexformgleichungen behandelt. Wie bereits gesagt ist das allgemeine Problem recht schwer und nur bis Grad 5 effizient lösbar. So werden die einzelnen Grade getrennt behandelt. Ein klassisches Ergebnis ist mittlerweile, dass sich Indexformgleichungen vom Grad 3 auf einfache Thue-Gleichungen zurückführen lassen. Es stellt sich heraus, dass sich die zugehörigen Indexformgleichungen deutlich vereinfachen, wenn mehr Struktur über die Galoisgruppe des Zahlkörpers bekannt ist. Im günstigsten Fall ist der gegebene Körper ein Kompositum von Teilkörpern, was die Lösung deutlich vereinfacht. Hier können z. B. Grad 9-Erweiterungen effizient gelöst werden. Auch die einfache Existenz von Teilkörpern ist sehr nützlich für die Lösung des zugehörigen Problems.

Das Buch endet mit mehreren großen Körpertabellen im Grad 3, 4 und 6, die Informationen zu den Potenzganzheitsbasen enthalten.

Als Voraussetzung für dieses Buch sind einfache Kenntnisse in algebraischer Zahlentheorie nützlich. So sollte man wissen, was der Ring der ganzen Zahlen eines Zahlkörpers ist und wie seine Einheitengruppe aussieht. Insgesamt sollte dieses Buch für Studenten im Hauptstudium mit Schwerpunkt Algebra/Zahlentheorie geeignet sein. Es ist sehr schön, dass endlich die Ergebnisse über Potenzganzheitsbasen in einem Buch vorliegen. Da zusätzlich auch andere diophantische Probleme behandelt werden, ist dieses Buch auch für Forscher in der konstruktiven Zahlentheorie interessant.

Rezension: Jürgen Klüners (Kassel) aus Computeralgebra-Rundbrief, Nr. 33 - Oktober 2003

Einführung in die Kryptographie

Johannes Buchmann
Springer-Lehrbuch, Springer-Verlag Berlin-Heidelberg-New York 1999, pp.229, 49,90 DM
2. erw. Aufl., Springer-Verlag, Berlin, Heidelberg, New York, 2001, 231 Seiten, 27,52 €
Springer, 2010, 304 Seiten, 5. Aufl., 32,99

ISBN: 3-540-66059-3
ISBN: 3-540-41283-2
ISBN: 3-642-11185-8

Es folgen die Rezensionen von: H. Meyn (1. Aufl.), J. Apel (2. Aufl.) und E. Behrends

Rezension zur 1. Auflage

Das Buch enthält die folgenden Abschnitte: Ganze Zahlen - Kongruenzen und Restklassenringe - Verschlüsselung - Wahrscheinlichkeit und perfekte Sicherheit - Der DES-Algorithmus - Primzahlerzeugung - Public-Key Verschlüsselung - Faktorisierung - Diskrete Logarithmen - Kryptographische Hash-Funktionen - Digitale Signaturen - Andere Gruppen - Identifikation - Public-Key-Infrastrukturen.

Aus dem Vorwort: ,,Ich wende mich in diesem Buch an Leser, die moderne kryptographische Techniken und ihre mathematischen Fundamente kennenlernen wollen, aber nicht über die entsprechenden mathematischen Spezialkenntnisse verfügen. Mein Ziel ist es, in die Basistechniken der modernen Kryptographie einzuführen. Ich setze dabei zwar mathematische Vorbildung voraus, führe aber in die Grundlagen von linearer Algebra, Algebra, Zahlentheorie und Wahrscheinlichkeitstheorie ein, soweit diese Gebiete für die behandelten kryptographischen Verfahren relevant sind."

Dem Verfasser ist es gelungen, dieser Zielsetzung gerecht zu werden. Alle zum Verständnis moderner krytopraphischen Techniken erforderlichen Begriffsbildungen werden in einer sehr klaren Sprache erläutert und, wenn möglich, sogleich an kleinen Beispielen verdeutlicht. Besonderer Wert wird auf die Beschreibung der zugrundeliegenden Ideen gelegt. Der Autor beschränkt sich auf die Darstellung derjenigen mathematischen Hilfsmittel, deren Beweis nicht mehr als eine Druckseite beansprucht. In der Summe ergibt sich ein Text von hoher Lesbarkeit.

Die Übungsaufgaben (mit Lösungen) sind genau am Text orientiert. Neben Aufgaben, die ein Überdenken der im Text gebrachten Argumente und Beweise erfordern, finden sich viele, die den Leser auffordern, die vorgestellten Techniken an moderat großen Beispielen mit Hilfe eines Computer-Algebra-Systems zu erproben.

(Die im Buch erwähnte Programm-Bibliothek LiDIA findet sich unter http://www.informatik.tu-darmstadt.de/TI/LiDIA/.)

Das Buch hat ein ausreichend detailliertes Sachverzeichnis und ein Literaturverzeichnis, in dem u.a. alle wichtigen, weiterführenden Werke über moderne Kryptographie zu finden sind.

Nochmals aus dem Vorwort: ,,Es ist nötig, daß die Anwender einschätzen können, ob die benutzten kryptographischen Methoden effizient und sicher genug sind. Dazu müssen sie nicht nur wissen, wie die kryptographischen Verfahren funktionieren, sondern sie müssen auch deren mathematischen Grundlagen verstehen."
Dies allen zur Beherzigung, die sich der praktischen Seite der Kryptographie zuwenden wollen!

Ein lehrreiches und preiswertes Buch.

Rezension: H. Meyn (Erlangen) aus Computeralgebra-Rundbrief, Nr. 27 - Oktober 2000

Rezensionen zur 2. Auflage

Dieses ursprünglich 1999 erschienene und nun bereits in der 2. Auflage vorliegende Buch aus der Springer-Lehrbuch-Reihe beschäftigt sich mit modernen kryptographischen Verfahren unter besonderer Berücksichtigung der mathematischen Hintergründe.

Das Buch ist in 14 Kapitel gegliedert, wovon sich acht der Beschreibung und Diskussion von kryptographischen Verfahren und darauf beruhenden Anwendungen widmen und die verbleibenden sechs Einführungen in die zahlentheoretischen und algorithmischen Hintergründe der Verfahren und der Attacken auf diese bieten.

In den ersten beiden Kapiteln (1. Ganze Zahlen, 2. Kongruenzen und Restklassen) werden die erforderlichen elementaren zahlentheoretischen Begriffe und Sätze bereitgestellt. Außerdem erfolgt eine kurze Einführung in die für die Gütebewertung kryptographischer Verfahren und Attacken außerordentlich bedeutsamen Komplexitätsbetrachtungen und -notationen.

Das 3. Kapitel (Verschlüsselung) gibt eine Einführung in die Problemstellung der Kryptographie, zeigt die wesentlichen Unterschiede symmetrischer und asymmetrischen Kryptosysteme auf, beschreibt eine Reihe klassischer symmetrischer Verschlüsselungsverfahren und geht auf die verschiedenen Betriebsmodi von Blockchiffren ein.

Kapitel 4 (Wahrscheinlichkeit und perfekte Sicherheit) stellt einige Begriffe der Wahrscheinlichkeitsrechnung bereit und formuliert auf dieser Grundlage die Anforderungen, die man an ein perfekt sicheres Kryptosystem stellen muss. Ebenfalls eingegangen wird auf die Generierung von (Pseudo-)Zufallszahlenfolgen, welche eine wesentliche Voraussetzung bei der praktischen Umsetzung (nahezu) perfekter Sicherheit darstellt. Im fünften Kapitel (Der DES-Algorithmus) wird das wohl berühmteste und gleichzeitig umstrittenste moderne symmetrische Kryptosystem beschrieben und analysiert.

Bevor in Kapitel 7 (Public-Key Verschlüsselung) die bekanntesten asymmetrischen Kryptosysteme (RSA, Rabin-Verschlüsselungsverfahren, Diffie-Hellman-Schlüsselaustausch, ElGamal) vorgestellt und diskutiert werden, stellt Kapitel 6 (Primzahlerzeugung) eine Reihe von Primzahltests bereit. Den darauf beruhenden schnellen Verfahren zur Primzahlerzeugung kommt eine Schlüsselrolle bei der Realisierung asymmetrischer Kryptosysteme zu. Die folgenden beiden Kapitel (8. Faktorisierung, 9. Diskrete Logarithmen) behandeln effiziente Verfahren zur Berechnung der beiden am häufigsten in Public-Key Systemen eingesetzten Einwegfunktionen. Derartige Verfahren stellen wichtige Werkzeuge für die Kryptoanalyse dar, womit ihnen gleichzeitig eine entscheidende Bedeutung bei der Gütebewertung von Kryptosystemen zukommt. Asymmetrische Kryptosysteme wie ElGamal, deren Sicherheit auf der Schwierigkeit der Berechnung diskreter Logarithmen basiert, erlauben den Einsatz elliptischer Kurven oder beliebiger endlicher Körper anstelle endlicher Primkörper. Die mathematischen Hintergründe dieser Varianten werden in Kapitel 12 (Andere Gruppen) beleuchtet.

Schließlich behandeln die Kapitel 10 (Kryptographische Hashfunktionen), 11 (Digitale Signaturen) sowie 13 (Identifikation) und 14 (Public-Key-Infrastrukturen) eine Auswahl von Anwendungsproblemen, die sich auf der Grundlage kryptographischer Verfahren lösen lassen.

Jedes Kapitel schließt mit einer Reihe von Übungen ab. Eine Liste der Lösungen findet man am Ende des Buches.

Das Buch richtet sich vorrangig an Leser, die die Wirkungsweise kryptographischer Verfahren und Attacken verstehen möchten. Spezielle Vorkenntnisse des Lesers werden vom Autor nicht vorausgesetzt, da der notwendige mathematische Apparat im Buch selbst entwickelt wird. Für Interessenten einer Anleitung zur effizienten Implementierung spezieller Verfahren sei angemerkt, dass die Behandlung von Implementationsfragen den Rahmen des Buches gesprengt hätte und daher nicht zu Buchmanns Hauptanliegen zählte.

Aus eigener Erfahrung kann ich das Buch wärmstens als Lehrbuch für eine Einführungsvorlesung für Studenten des Hauptstudiums in theoretischer Informatik oder Mathematik in das Gebiet der Kryptographie empfehlen. Ebenso eignet es sich ausgezeichnet für Studenten oder Wissenschaftler zur selbständigen Einarbeitung in das Fachgebiet der Kryptographie.

Rezension: Joachim Apel (Leipzig) aus Computeralgebra-Rundbrief, Nr. 30 - März 2002

Bald nach ihren Anfängen ist Kryptographie - die Wissenschaft vom Verschlüsseln und Enschlüsseln - auf eine mathematische Basis gestellt worden, schon seit längerer Zeit kommen auch sehr aufwändige Verfahren zum Einsatz.

Das Buch ist mit dem Anspruch geschrieben, die den heute wichtigen Verfahren zugrunde liegende Mathematik vorzustellen und die wichtigsten aktuellen Aspekte zu beschreiben: RSA, Hash-Funktionen, digitale Signaturen, zero-knowledge-Beweise. Dieser Anspruch wird eingelöst, es gibt wohl kein anderes Buch der letzten Zeit, das eine derartige Fülle an Information bei gleichzeitiger mathematischer Präzision bietet.

Es ist nicht ganz so klar, dass - wie im Vorwort zu lesen - das Buch ohne mathematische Spezialkenntnisse gelesen werden kann. Streng genommen stimmt das sicher, aber für Laien ist es eigentlich zu kompakt geschrieben.

Empfehlen kann man es allen, die schon vor dem Lesen des Buches an die Sprache der Mathematik herangeführt wurden. (Z.B. Studierenden der Mathematik, der Natur- und Ingenieurwissenschaften und der Informatik; und natürlich allen belastbaren Oberschülerinnen und -schülern.)

(Rezension: Ehrhard Behrends)

Computational Invariant Theory

H. Derksen, G. Kemper
Springer Verlag, New York, Berlin, Heidelberg, 2002, 268 Seiten, 90,00 €

ISBN 3-540-43476-3

Dieses Buch behandelt Invariantentheorie, d. h. den Ring der Polynome, die unter einer Gruppe invariant sind. Wie der Titel des Buches schon sagt, liegt ein Schwerpunkt auf den algorithmischen Aspekten zur Berechnung von Erzeugendensystemen des Invariantenringes. Dadurch hebt es sich deutlich von theoretischen Büchern zu diesem Thema ab. Das Buch von B. Sturmfels von 1993 zur algorithmischen Invariantentheorie hat das Interesse an diesem Gebiet stark geprägt.

Die Themenauswahl des Buches ist gekennzeichnet durch die wissenschaftlichen Arbeiten der Autoren zu diesem Thema. Der Algorithmus zur Berechnung eines Erzeugendensystems für linear reduktive algebraische Gruppen hat die Fachwelt bei seiner Entdeckung überrascht und begeistert. Der Algorithmus basiert auf Ideen von Hilbert, für die Hilbert seinerzeit kritisiert wurde, weil sie nicht konstruktiv sind. Hundert Jahre später wissen wir es besser. Hoffentlich teilt jeder Leser meinen Enthusiasmus für diesen Algorithmus.

Ein weiterer Schwerpunkt liegt auf der modularen Invariantentheorie. Hierbei teilt die Charakteristik des Körpers die Gruppenordnung, was fatale Konsequenzen für die algebraischen Strukturen hat, die für Algorithmen für Körper der Charakteristik 0 verwendet werden. Gerade deshalb ist dieses Thema für Algebraiker so interessant.

Ein besonderer Vorteil dieses Buches ist das reichhaltige Kapitel über Anwendungen. Es gibt Abschnitte, die in die Grundideen und die Literatur zur Lösung von polynomiellen Gleichungssystemen, Graphentheorie, Kombinatorik, Kodierungstheorie, dynamische Systeme, Computer Vision einführen. Die potentielle Leserschaft des Buches beschränkt sich deshalb nicht nur auf Algebraiker, die auf dem Gebiet der Computeralgebra und der Invariantentheorie arbeiten, sondern sollte auch algebraisch (vor)gebildete Anwender ansprechen.

Wie die Autoren formulieren, wendet sich das Buch an Forscher im Gebiet der Geometrie, Computeralgebra und der Invariantentheorie. Es kann aber sicherlich auch für ein Seminar verwendet werden, das auf eine einführende Vorlesung zur Computeralgebra aufbaut.

Da die Algorithmen zur Berechnung von fundamentalen Invarianten Gröbnerbasen und algorithmische kommutative Algebra verwenden, behandelt das erste Kapitel dieses Thema. Schon hier kann man bewundern, wie knapp, präzise und auf den Punkt genau die Autoren formulieren. Neben einer knappen Einführung in die Standardkonzepte rund um Gröbnerbasen ist der Algorithmus von de Jong zur Normalisierung enthalten.

Insgesamt gesehen ist dies ein sehr schönes Buch. Einige der Resultate sind nie zuvor in Buchform erschienen. Der einzige Nachteil, den ich an diesem Buch finden kann, ist folgender: Ich hätte das Buch gern einige Jahre früher zum Lesen gehabt.

Rezension: Karin Gatermann (Berlin) aus Computeralgebra-Rundbrief, Nr. 34 - März 2004

Cryptographic Applications of Analytic Number Theory
Complexity Lower Bounds and Pseudorandomness

I. Shparlinski
Birkhäuser Verlag, Basel, Boston, Berlin,2004, 411 Seiten, 104,86 €

ISBN 3-7643-6654-0

Anwendungen der Zahlentheorie in der Kryptographie wie RSA, Diffie-Hellman etc. sind allgemein bekannt. Das vorliegende Werk geht jedoch weit über diese Grundlagen hinaus und richtet sich an Leser, die bereits Vorbildung sowohl in Kryptographie als auch in der Zahlentheorie haben. Unterteilt ist das Buch in sieben Teile mit insgesamt 31 Kapiteln.

Der erste Teil (7 Kapitel) ist eine Einführung, in der alle später verwendeten Resultate und Bezeichnungen zusammen getragen werden.

Das erste Kapitel führt die im restlichen Buch verwendeten Notationen ein. Darunter sind auch eher exotische wie für den Rest von s bei Division durch m. Ich hätte es als hilfreich empfunden, wenn diese Notationen noch einmal in einem gesonderten Symbolverzeichnis zusammen gefasst worden wären. Die anderen Kapitel dieses Abschnitts wurden eher als eine ”Erinnerung“ an bereits bekannte Ergebnisse gestaltet. Ergebnisse wie der LLL-Algorithmus oder = O(log log(m + 1)) werden als bekannt vorausgesetzt.

Der zweite Teil (4 Kapitel) ist der Untersuchung des Diskreten-Logarithmus-Problems gewidmet. Dabei geht es um die Frage, wie gut der diskrete Logarithmus mit einfachen Funktionen angenähert werden kann. Die vier Kapitel beschäftigen sich jeweils mit der Approximation mod p, mod p–1, durch boolesche Funktionen und reellwertige Polynome. Der Autor konzentriert sich hier ganz auf die zahlentheoretischen Probleme, die Bedeutung der Resultate für die kryptographische Praxis wird nicht diskutiert.

Der dritte Teil (3 Kapitel) untersucht das Diffie-Hellman-Problem. Im Aufbau und in den Methoden ähneln die Untersuchungen denen aus dem zweiten Teil.

Im vierten Teil (8 Kapitel) werden verschiedene Public-Key-Kryptosysteme genauer untersucht. Die Resultate dieses Abschnitts sind aus Sicht der Kryptographie viel anwendungsbezogener als die der vorangegangenen Abschnitte.

Pseudozufallsgeneratoren sind das Thema des fünften Teils (5 Kapitel). Die einzelnen Kapitel sind unterschiedlichen Generatoren gewidmet (unter Anderem Blum-Blum-Shub, Naor-Reingold, 1/M). Hier kommen sowohl die kryptographischen Anwendungen als auch die zahlentheoretischen Methoden besonders gut zur Geltung.

Der sechste Teil enthält noch weitere 4 Kapitel, die vom Thema nicht in die anderen Teile gepasst haben. Im Einzelnen sind dies: zahlentheoretische Funktionen mit kryptographischen Anwendungen wie z. B. Testen der Quadratfreiheit (Kapitel 28), der Zusammenhang zwischen der arithmetischen Komplexität und der Komplexität eines zugehörigen booleschen Schaltkreises (Kapitel 29), Polynom-Approximation in endlichen Körpern (Kapitel 30), Untersuchung spezieller Funktionen wie z. B. Permutationspolynome (f : F_q → F_q ist bijektiv) (Kapitel 31).

Im siebten Teil stellt der Autor noch 55 offene Probleme vor. Die Auswahl erscheint mir sehr gelungen und ich denke, dass diese Liste eine gute Anregung für künftige Forschungen ist.

Das Literaturverzeichnis ist mit seinen 571 Einträgen sehr umfangreich und eignet sich gut für einen noch tieferen Einstieg in die Materie.

Fazit: Das Buch wird seinem Anspruch, sowohl für Kryptologen als auch Zahlentheoretiker interessant zu sein, voll und ganz gerecht. Für Einsteiger ist das Buch allerdings wegen der hohen Voraussetzungen an die Kenntnisse des Lesers weniger geeignet.

Rezension: Andreas Klein (Kassel) aus Computeralgebra-Rundbrief, Nr. 37 - Oktober 2005