Chapter 1．Cryptography 1
1．Early History 1
2．The Idea of Public Key Cryptography 2
3．The RSA Cryptosystem 5
4．Diffie-Hellman and the Digital Signature Algorithm 8
5．Secret Sharing,Coin Flipping,and Time Spent on Homework 10
6．Passwords,Signatures,and Ciphers 12
7．Practical Cryptosystems and Useful Impractical Ones 13
Exercises 17
Chapter 2．Complexity of Computations 18
1．The Big-O Notation 18
Exercises 21
2．Length of Numbers 22
Exercises 23
3．Time Estimates 24
Exercises 31
4．P,NP,and NP-Completeness 34
Exercises 41
5．Promise Problems 44
6．Randomized Algorithms and Complexity Classes 45
Exercises 48
7．Some Other Complexity Classes 48
Exercises 52
Chapter 3．Algebra 53
1．Fields 53
Exercises 55
2．Finite Fields 55
Exercises 61
3．The Euclidean Algorithm for Polynomials 63
Exercises 64
4．Polynomial Rings 65
Exercises 70
5．Gr？bner Bases 70
Exercises 78
Chapter 4．Hidden Monomial Cryptosystems 80
1．The Imai-Matsumoto System 80
Exercises 86
2．Patarin's Little Dragon 87
Exercises 95
3．Systems That Might Be More Secure 96
Exercises 102
Chapter 5．Combinatorial-Algebraic Cryptosystems 103
1．History 103
2．Irrelevance of Brassard's Theorem 104
Exercises 105
3．Concrete Combinatorial-Algebraic Systems 105
Exercises 109
4．The Basic Computational Algebra Problem 111
Exercises 112
5．Cryptographic Version of Ideal Membership 112
6．Linear Algebra Attacks 113
7．Designing a Secure System 114
Chapter 6．Elliptic and Hyperelliptic Cryptosystems 117
1．Elliptic Curves 117
Exercises 129
2．Elliptic Curve Cryptosystems 131
Exercises 136
3．Elliptic Curve Analogues of Classical Number Theory Problems 137
Exercises 139
4．Cultural Background:Conjectures on Elliptic Curves and Surprising Relations with Other Problems 139
5．Hyperelliptic Curves 144
Exercises 148
6．Hyperelliptic Cryptosystems 148
Exercises 154
Appendix．An Elementary Introduction to Hyperelliptic Curves&by Alfred J.Menezes,Yi-Hong Wu,and Robert J.Zuccherato 155
1．Basic Definitions and Properties 156
2．Polynomial and Rational Functions 159
3．Zeros and Poles 161
4．Divisors 167
5．Representing Semi-Reduced Divisors 169
6．Reduced Divisors 171
7．Adding Reduced Divisors 172
Exercises 178
Answers to Exercises 179
Bibliography 193
Subject Index 201