Mathematics of Public Key Cryptography
Version 0.4
Steven Galbraith
This webpage contains some draft chapters of an advanced mathematics
textbook. Please note that this book is still in the process of being
written and that any aspects are subject to change at any time.
You are also warned that the book contains errors (I hope that, with
your help, some of these errors can be removed).
The book is currently too long and will have to be
shortened.
Hence, you should assume that page numbers, section
numbers, theorem numbers etc will change and that
some of the contents may disappear.
The reason for putting this material on the web is that I
want to receive feedback on the book. Please send me an email
(s.galbraith@math.auckland.ac.nz) if you find anything
which is incorrect, poorly explained or misleading.
Also tell me if you think there is something important which I
have not included. All such contributions will be acknowledged.
Sample Chapters
The current overambitious table of contents
1. Introduction
Part I: Background
2. Background Mathematics (Appendix)
3. Basic Algorithms
4. Hash Functions (Appendix)
Part II: Algebraic Groups
5. Introduction to Algebraic Groups
6. Varieties
7. Tori, LUC and XTR
8. Curves and Divisor Class Groups
9. Rational Maps on Curves and Divisors
10. Elliptic Curves
11. Hyperelliptic Curves
12. Algebraic Groups over Rings
Part III: Exponentiation, Factoring and Discrete Logarithms
13. Basic Algorithms for Algebraic Groups
14. Primality Testing and Integer Factorisation using
algebraic groups
15. Basic Discrete Logarithm Algorithms
16. Factoring and Discrete Logarithms Using Pseudorandom Walks
17. Factoring and Discrete Logarithms in Subexponential Time
Part IV: Lattices
Preface and Table of Notation for Part IV
18. Lattices
19. Lattice Reduction
20. Algorithms for the Closest and Shortest Vector Problem
21. Coppersmith's Method and Other Applications
22. Cryptosystems Based on Lattices
Part V: Cryptography Related to Discrete Logarithms
23. The Diffie-Hellman Problem and Cryptographic Applications
24. Results on the Diffie-Hellman Problem
25. Digial Signatures Based on Discrete Logarithms
26. Public Key Encryption Based on Discrete Logarithms
27. Efficient Implementation of Discrete Logarithm Cryptography
Part VI: Cryptography Related to Integer Factorisation
28. The RSA and Rabin Cryptosystems
Part VII: Advanced Topics in Elliptic and Hyperelliptic Curves
29. Isogenies
30. Complex Multiplication
31. Point Counting
32. Pairings
33. Other Topics
Hints and Solutions to Exercises
References
Index