Leseecke

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

Cryptography and Computational Number Theory

K.-Y. Lam, I. Shparlinski, H. Wang, C. Xing (Herausgeber)
Birkhäuser Verlag, Boston, Basel, Berlin, 2001, 392 Seiten, 155 $

ISBN 3-7643-6510-2

Die beiden im Titel genannten Gebiete und ihre wechselseitigen Beziehungen waren Gegenstand des CCNT Workshops im November 1999 in Singapur. Die Entwicklung in diesen Bereichen verläuft gerade in den letzten Jahren sehr rasant, so dass es Ziel des Workshops war, einerseits einen Überblick über den Stand der Forschung zu geben und andererseits neue Aspekte zu benennen und darzustellen und so die Forschung weiter voranzutreiben. Der Workshop war Treffpunkt für Mathematiker, Informatiker, Programmierer und Ingenieure. In den Tagungsband aufgenommen wurden 27 Arbeiten aus den verschiedensten Gebieten, was natürlicherweise zur Folge hat, dass bei der Besprechung eine Auswahl zu treffen war. Diese wiederum muss nach persönlichen Vorlieben geschehen, was der Leser entschuldigen möchte. So steht bei den ausgewählten Artikeln der zahlentheoretische Aspekt und dessen Bedeutung für die kryptographischen Anwendungen im Vordergrund.

A. Conflitti: On Elements of High Order in Finite Fields.
In den endlichen Gruppen mit kryptographischer Relevanz spielt speziell die Ordnung eines Elementes eine Rolle; so ist es von Bedeutung, Elemente hoher Ordnung zu konstruieren (wie etwa speziell Basispunkte auf elliptischen Kurven). In diesem Artikel werden endliche Körper F_qn betrachtet, und es wird eine Abschätzung für die Ordnung eines Elementes α ∈ F_qn vom Grad n, die auf S. Gao zurückgeht, verbessert. Betrachtet werden Elemente α, die einer speziellen Gleichung X^m - g(X) genügen, wobei m eine q-Potenz ist und der Grad von g beschränkt ist. Dabei wird, ähnlich wie bei Gao, eine Sequenz multiplikativ unabhängiger Hilfspolynome konstruiert. Die Abschätzung ist in extremen Fällen quadratisch in der alten unteren Schranke. Conflitti schlägt vor, auch Wurzeln α von Gleichungen X^mh(X)- g(X) zu betrachten und hier analoge Aussagen zu machen.

D. Kohel: Rational Groups of Elliptic Curves Suitable for Cryptography.
Die Arbeit von Kohel gibt einen guten Überblick über die verschiedenen Methoden, elliptische Kurven zu konstruieren, die für kryptographische Zwecke geeignet sind, das bedeutet konkret, deren Ordnung einen großen Primfaktor enthält. Die beiden hauptsächlichen Methoden hierfür sind einerseits die Zufallsmethode (also Bestimmen der Ordnung "zufällig'' gewählter Kurven) und andererseits die Methode der komplexen Multiplikation (CM-Methode, Konstruktion einer geeigneten Kurve zu vorgegebener Diskriminante). Es werden beide Methoden vorgestellt und Varianten gegeben. Ein bisschen zu sehr betont wird die bekannte Tatsache, dass bei der Konstruktion von Kurven nach der CM-Methode bei Festlegung der Charakteristik des zu Grunde liegenden Körpers der Zufallsaspekt natürlich zu kurz kommt. Übrigens ist angesichts der Tatsache, dass mit Hilfe der Zufallsmethode heute die Punkteanzahl einer elliptischen Kurve sehr schnell berechnet werden kann, die CM-Methode ohnehin in den Anwendungen nicht übermäßig relevant. Der Artikel eignet sich gut für "Einsteiger'', die sich einen Überblick verschaffen wollen.

R. Peralta: Elliptic Curve Factorization Using a "Partially Oblivious'' Function.
Es geht um die Faktorisierung großer ganzer Zahlen N = P ⋅ R, wobei P eine Primzahl ist, die R nicht teilt. Der Autor beschreibt eine Variation von Lenstra's Elliptic Curve Method, die mit Hilfe einer speziellen Klasse von Funktionen, den "teilweise vergesslichen'' Funktionen (im Deutschen klingt es nicht besser als im Englischen) schneller als die herkömmliche Methode ist. Dabei handelt es sich um Funktionen f : Z/NZ → Z, die, grob gesprochen, die Periode P haben und einer Wahrscheinlichkeitsbedingung genügen. Solche Funktionen existieren für den Fall, dass R ein perfektes Quadrat ist. Es gibt Kryptosysteme, in denen solche Zahlen benutzt werden, doch ist der hier vorgestellte Algorithmus nicht schnell genug, um diese ernsthaft anzugreifen.

A. De Bonis, A. De Santis: New Results on the Randomness of Visual Cryptography Schemes.
In kryptographischen Anwendungen ist es stets notwendig, "gute'' Zufallszahlen zu erzeugen. Da dies sehr schwer ist, besteht eine Alternative darin, Verfahren zu konstruieren, die mit möglichst wenigen Zufallszahlen auskommen. In dieser Arbeit werden diese Fragen bei Verfahren behandelt, die auf visueller Kryptographie beruhen. Der Artikel ist auch ohne Vorkenntnisse zu verstehen, wenn auch Grundkenntnisse in visueller Kryptographie das Verständnis natürlich enorm erleichtern.

Abschließend möchte ich betonen, dass dieser Tagungsband überraschend weit gefächert ist und - wie es auch schon Anspruch der Tagung war - sicher neben dem anwendungsinteressierten Mathematiker auch viele Wissenschaftler aus anderen Gebieten anspricht.

Rezension: Markus Wessler (Kassel) aus Computeralgebra-Rundbrief, Nr. 29 - Oktober 2001

Algorithmische Methoden
Zahlen, Vektoren, Polynome

P. Kügler, W. Windsteiger
Birkhäuser Verlag, 2009, 160 Seiten, 18,90 €

ISBN 978-3-7643-8434-0

Das vorliegende Buch ist als einsemestrige Einführung in die algorithmische Mathematik konzipiert, gerichtet an Studierende vorwiegend des dritten Semesters. Kenntnisse über die Grundstrukturen von Analysis und linearer Algebra (speziell Zahlen, Vektoren, Polynome) werden also vorausgesetzt – eine kurze Übersicht des benötigten Stoffs findet sich gleichwohl zu Beginn des jeweiligen Kapitels – und weite Teile des Buches sind mit der Implementation dieser Strukturen und der zugehörigen Rechenoperationen auf dem Computer befasst.

Das Buch umfasst vier Kapitel. Das erste Kapitel führt die Grundbegriffe des Buches ein, auf eher informelle Weise und anhand von Beispielen, die dann in den folgenden Kapiteln wiederholt aufgegriffen werden. Bei diesen Begriffen handelt es sich einerseits um Grundkonzepte der Informatik (Schleifen, Rekursion), und andererseits um Kriterien für die Bewertung von Algorithmen, zum Beispiel (relative und absolute) Rundungsfehler, die Kondition eines Problems, Korrektheit, Stabilität (vorwärts und rückwärts), Komplexität. Die im weiteren Verlauf des Buches entwickelten Algorithmen werden anhand dieser Qualitätsmerkmale analysiert und Weiterentwicklungen daraus motiviert. Wie an den aufgezählten Kriterien zu erkennen ist, liegt der Schwerpunkt der Analyse auf numerischen Aspekten.

Die algorithmische Umsetzung wird in einem recht intuitiven Pseudocode dokumentiert. Sämtliche im Buch beschriebenen Algorithmen wurden sowohl in MATLAB als auch in Mathematica implementiert (als Vertreter vorwiegend numerischer beziehungsweise symbolischer Mathematik-Pakete); die Implementationen sind frei über das Internet verfügbar.

Kapitel 2 behandelt die algorithmische Behandlung von Zahlbereichen, von natürlichen über rationale zu den reellen Zahlen. Es werden jeweils das Problem der Darstellung dieser Zahlen im Rechner und die mittlerweile gebräuchlichen (IEEE-)Standardlösungen dafür diskutiert, gefolgt von der Implementation der Grundrechenarten. Dabei werden neben den naheliegenden auch effizientere Lösungen präsentiert (etwa: der Karatsuba-Algorithmus zur Multiplikation ganzer Zahlen oder Henrici-Algorithmen für die Addition und Multiplikation in ).

Kapitel 3 ist mit der Übertragung der Grundrechenarten auf Vektoren – genauer, Elementen von d – befasst. Die Implementation des Gram-Schmidt-Orthonormalisierungsverfahrens mitsamt einer Analyse des Stabilitätsverhaltens, schließt das Kapitel ab. Das letzte Kapitel behandelt Polynome, und dort speziell Algorithmen zur Polynomdivision mit Rest, den euklidischen Algorithmus, Polynomauswertung und -interpolation. Am Ende jedes Kapitels finden sich Übungsaufgaben zur Vertiefung des Stoffes.

Die Autoren sind sichtlich um eine lebendige und problemorientierte Darstellung ihres Stoffes bemüht. Der Großteil der im ersten Kapitel entwickelten Kriterien beschäftigt sich mit dem Grundproblem der numerischen Mathematik, nämlich der approximativen Behandlung (potenziell) unendlicher mathematischer Objekte mit endlichen Speicherplatz- und Zeitressourcen. Die Darstellung in diesem Kapitel springt zeitweise munter zwischen algorithmischen Konzepten (Schleifen, Rekursion, etc.), numerischen Begriffen (Fehlerabschätzungen, Maschinengenauigkeit) und mathematischen Sätzen, was zumindest beim Rezensenten eine gewisse Desorientierung zur Folge hatte.

Das Bemühen, die nötigen Begriffe anhand möglichst konkreter Beispiele einzuführen, ist hier erkennbar und an einigen Stellen auch durchaus erfolgreich. Zumindest im ersten Kapitel aber scheint mir dies durch einen Mangel an Struktur und Kohärenz (zu) teuer erkauft. Eine weitere in meinen Augen problematische strukturelle Entscheidung der Autoren betrifft die Darstellung der reellen Zahlen im Computer, die erst im zweiten Kapitel ausführlich behandelt wird. Viele der in Kapitel 1 entwickelten numerischen Begriffe lassen sich aber meines Erachtens wesentlich präziser beschreiben und motivieren, wenn man explizit auf diese Darstellung verweisen kann; zudem wäre der Leser dann bereits hinreichend für die zugrundeliegende Problematik sensibilisiert.

Rezension: Hartmut Führ, Aachen aus Computeralgebra-Rundbrief, Nr. 45 - Oktober 2009

Analysis
Band 2 - Ein Lehrbuch

E. Behrends
Vieweg Verlag, Wiesbaden, 2007, 2. Aufl., 378 Seiten, 27,99 €

ISBN: 3-834-80102-X

Warum besprechen wir im Computeralgebra-Rundbrief ein Analysis-Buch? Der Grund ist einfach: Dieses Buch unterscheidet sich von ähnlichen Büchern durch die Themenwahl. Natürlich werden auch in diesem Buch die üblichen Themen einer Analysis-II-Vorlesung behandelt: Funktionenräume (punktweise und gleichmäßige Konvergenz, Räume stetiger Funktionen, Vollständigkeit), Integration (Hauptsatz, parameterabhängige Integrale, L_p-Normen), Anwendungen der Integralrechung (Weierstraßscher Approximationssatz, Kurvendiskussion, Kurvenlänge, Laplacetransformation, Differentialgleichungen), Differentialrechung im Rⁿ (lineare Abbildungen, Differenzierbarkeit und partielle Ableitungen, Satz von Taylor, Extremwertaufgaben, Koordinatentransformationen, Satz über implizite Funktionen, Extremwerte mit Nebenbedingungen).

Aber das Neue an diesem Buch ist, dass zusätzlich Themen behandelt werden, die zum Themenkreis der Computeralgebra gehören und die bisher nicht in Lehrbüchern dieser Art zu finden sind, obwohl sie wichtige Ergänzungen zu den eingeführten Begriffsbildungen darstellen.

Sehr interessant ist Abschnitt 6.6: exp(x²) hat keine "einfache" Stammfunktion. In diesem Abschnitt werden Körper mit Differentiation eingeführt, es werden algebraische und transzendente Körpererweiterungen betrachtet. Dann wird der Satz von Liouville und Ostrowski präsentiert, der elementare Stammfunktionen elementarer Funktionen charakterisiert. Schließlich gelingt der Beweis, dass die Funktion exp(x²) keine elementare Stammfunktion haben kann.

Es wird also in diesem Lehrbuch der Risch-Algorithmus zur Integration elementarer Funktionen an einem speziellen Beispiel vorgeführt. Dies ist meines Erachtens sehr lobenswert, da sich durch die immer häufigere Nutzung von Computeralgebrasystemen jeder Mathematikstudierende die Frage stellen sollte, wie eigentlich ein Computeralgebrasystem integriert. Wenn auch der Risch-Algorithmus momentan nicht in jedem Computeralgebrasystem verfügbar ist, so lernt man in diesem Lehrbuch immerhin, wie es gemacht werden könnte. Dies zeigt insbesondere, dass eine fehlende Ausgabe bei einem Computeralgebrasystem bedeuten kann, dass die Rechnung bewiesen hat, dass eine Ausgabe eines bestimmten Typs gar nicht existiert.

In einem weiteren Abschnitt (Abschnitt 7.5) wird die Transzendenz der Eulerschen Zahl e und die Irrationalität der Kreiszahl π bewiesen. In diesem Zusammenhang wird die Approximierbarkeit rationaler Zahlen genau untersucht, wobei hier ebenfalls klassische Resultate der Computeralgebra einfließen.

Das Buch ist sorgfältig geschrieben, sollte in keiner Bücherei fehlen und kann jedem Studierenden ans Herz gelegt werden.

Rezension: Wolfram Koepf (Kassel) aus Computeralgebra-Rundbrief, Nr. 35 - Oktober 2004

ClassPad im Mathematikunterricht
Nach einer Idee von Wolfram Koepf

Matthias Bernhard, Christian Wesselsky
Vieweg+Teubner, Wiesbaden, 2009, 185 Seiten, 22,99 €

ISBN 978-38348-0840-0

Hier erschien ein Klassiker des Computereinsatzes im Mathematikunterricht – Wolfram Koepfs „DERIVE für den Mathematikunterricht“ von 1996 – unter Nutzung eines anderen Werkzeugs teilweise neu. Eingesetzt wurde jetzt der Taschencomputer ClassPad von CASIO. CASIO unterstützt seit Jahren die Herausgabe von Veröffentlichungen, die dem Computereinsatz im Unterricht Impulse geben (wie dies auch Mitbewerber tun). Nach Ansicht des Rezensenten stellt die Bernhard-Wesselsky-Koepf-Veröffentlichung in diesem Kontext eine interessante Bereicherung dar. Manche Anregung kann direkt und unmittelbar im Mathematikunterricht der gymnasialen Oberstufe umgesetzt werden, anderes ist eher in Projektphasen und systematisierenden Wiederholungen einsetzbar und wieder anderes erhöht „nur“ den Weitblick der unterrichtenden Lehrerinnen und Lehrer. All das ist wichtig und lohnenswert. Praktiker vor Ort benötigen Materialien, die auch helfen, ihre Werkzeugkompetenz weiterzuentwickeln und diese nicht umfassend voraussetzen. In der vorliegenden Veröffentlichung sind Erlauterungen und Abbildungen konkret auf den ClassPad zugeschnitten. Es gibt zahlreiche Übungsaufgaben einschließlich Lösungen. Eine beiliegende CD-ROM stellt diverse Programme und elektronische Arbeitsblätter bereit. Damit geht das vorliegende Buch über die Koepf-Veröffentlichung von 1996 hinaus.

Das Buch von 2009 besteht aus sechs Kapiteln. Kapitel 1 (Geometrie) thematisiert Berechnungen an Dreiecken und die näherungsweise Berechnung von . Im Kapitel 2 (Kegelschnitte) geht es erwartungsgemäß um Ellipse, Parabel, Hyperbel sowie um Transformationen und Polarkoordinatendarstellung. Die Autoren machen sich für die (Wieder-)Aufnahme des Themas „Kegelschnitte“ in den schulischen Mathematikunterricht stark (wie auch bereits Koepf 1996), und zwar wegen dessen wissenschaftlicher Bedeutung, und verweisen darauf, dass ClassPad helfen kann, das Thema relativ zügig durchzunehmen. Dem ist einerseits zuzustimmen, andererseits ist dem entgegenzuhalten, dass Schule kollabieren würde, wäre sie in der Pflicht, alles Wichtige zu thematisieren. Schule nimmt immer eine inhaltliche Auswahl vor (über die man sicher streiten kann) und sollte sich ansonsten auf das Gewährleisten eines dauerhaft verfügbaren Wissens und Könnens ihrer Absolventen konzentrieren. Im Kapitel 3 (Flächenberechnung) werden mehrere numerische Integrationsverfahren behandelt und grafisch dargestellt, es geht um das Volumen und den Oberflächeninhalt von Rotationskörpern. Kapitel 4 (Partielle Integration) beschreibt im Grunde genommen, wie gewisse Grenzen des ClassPad beim Bestimmen von Integralen überwunden werden können – und zwar mithilfe des ClassPad selbst. Besonders interessante Schwerpunkte des Kapitels 5 (Lineare Gleichungssysteme und Matrizen) sind die Kondition linearer Gleichungssysteme und die Hilbert-Matrix. Eines der Einstiegsbeispiele in das Kapitel (Preisermittlung von Waschpulver, Bohnen und Milch mit Hilfe eines linearen Gleichungssystems) dürften kritische Schülerinnen und Schüler als für sie persönlich irrelevant erkennen. Im anwendungsorientierten Kapitel 6 (Einfache Differentialgleichungen) geht es um die Methode Trennung der Variablen und um lineare Differentialgleichungen erster Ordnung. Die Schwingungsgleichung wird genauer untersucht; auf Anschaulichkeit wird viel Wert gelegt.

Das Buch stellt einen interessanten Beitrag dar, Computer im Mathematikunterricht intelligent einzusetzen. Vier Themen aus Koepfs Buch von 1996 wurden nicht übernommen. Hierzu muss in der Originalveröffentlichung nachgeschlagen werden.

Rezension: Michael Fothe (Jena) aus Computeralgebra-Rundbrief, Nr. 47 - Oktober 2010