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 : Fq → Fq 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