内容

目次

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.- 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.- 3. Algebra.- §1. Fields.- Exercises.- §2. Finite Fields.- Exercises.- §3. The Euclidean Algorithm for Polynomials.- Exercises.- §4. Polynomial Rings.- Exercises.- §5. Gröbner Bases.- Exercises.- 4. Hidden Monomial Cryptosystems.- § 1. The Imai-Matsumoto System.- Exercises.- §2. Patarin’s Little Dragon.- Exercises.- §3. Systems That Might Be More Secure.- Exercises.- 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.- 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.- §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.