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