This book is intended as a text for a course on cryptography with emphasis on algebraic methods. It is written so as to be accessible to graduate or advanced undergraduate students, as well as to scientists in other fields. The first three chapters form a self-contained introduction to basic concepts and techniques. Here my approach is intuitive and informal. For example, the treatment of computational complexity in Chapter 2, while lacking formalistic rigor, emphasizes the aspects of the subject that are most important in cryptography.

Chapter 1. Cryptography

 §1. Early History

 §2. The Idea of Public Key Cryptography

 §3. The RSA Cryptosystem

 §4. Diffie-Hellman and the Digital Signature Algorithm

 §5. Secret Sharing, Coin Flipping, and Time Spent on Homework

 §6. Passwords, Signatures, and Ciphers

 §7. Practical Cryptosystems and Useful Impractical Ones

Exercises

Chapter 2. Complexity of Computations

 § 1. The Big-O Notation

Exercises

 §2. Length of Numbers

Exercises

 §3. Time Estimates

Exercises

 §4. P, NP, and NP-Completeness

Exercises

 §5. Promise Problems

 §6. Randomized Algorithms and Complexity Classes

Exercises

 §7. Some Other Complexity Classes

Exercises

Chapter 3. Algebra

 §1. Fields

Exercises

 §2. Finite Fields

Exercises

 §3. The Euclidean Algorithm for Polynomials

Exercises

 §4. Polynomial Rings

Exercises

 §5. Grobner Bases

Exercises

Chapter 4. Hidden Monomial Cryptosystems

 §1. The Imai-Matsumoto System

Exercises

 §2. Patarin's Little Dragon

Exercises

 §3. Systems That Might Be More Secure

Exercises

Chapter 5. Combinatorial-Algebraic Cryptosystems

 §1. History

 §2. Irrelevance of Brassard's Theorem

Exercises

 §3. Concrete Combinatorial-Algebraic Systems

Exercises

 §4. The Basic Computational Algebra Problem

Exercises

 §5. Cryptographic Version of Ideal Membership

 §6. Linear Algebra Attacks

 §7. Designing a Secure System

Chapter 6. Elliptic and Hyperelliptic Cryptosystems

 §1. Elliptic Curves

Exercises

 §2. Elliptic Curve Cryptosystems

Exercises

 §3. Elliptic Curve Analogues of Classical Number Theory Problems

Exercises

 §4. Cultural Background: Conjectures on Elliptic Curves

and Surprising Relations with Other Problems

 §5. Hyperelliptic Curves

Exercises

 §6. Hyperelliptic Cryptosystems

Exercises

Appendix. An Elementary Introduction to Hyperelliptic Curves

by Alfred J. Menezes, Yi-Hong Wu, and Robert J. Zuccherato

 §1. Basic Definitions and Properties

 §2. Polynomial and Rational Functions

 §3. Zeros and Poles

 §4. Divisors

 §5. Representing Semi-Reduced Divisors

 §6. Reduced Divisors

 §7. Adding Reduced Divisors

Exercises

Answers to Exercises

Bibliography

Subject Index