Elliptic Curves: Number Theory and Cryptography, Second Edition

Description

Like its bestselling predecessor, Elliptic Curves: Number Theory and Cryptography, Second Edition develops the theory of elliptic curves to provide a basis for both number theoretic and cryptographic applications. With additional exercises, this edition offers more comprehensive coverage of the fundamental theory, techniques, and applications of elliptic curves. New to the Second Edition Chapters on isogenies and hyperelliptic curves A discussion of alternative coordinate systems, such as projective, Jacobian, and Edwards coordinates, along with related computational issues A more complete treatment of the Weil and Tate–Lichtenbaum pairings Doud’s analytic method for computing torsion on elliptic curves over Q An explanation of how to perform calculations with elliptic curves in several popular computer algebra systems Taking a basic approach to elliptic curves, this accessible book prepares readers to tackle more advanced problems in the field. It introduces elliptic curves over finite fields early in the text, before moving on to interesting applications, such as cryptography, factoring, and primality testing. The book also discusses the use of elliptic curves in Fermat’s Last Theorem. Relevant abstract algebra material on group theory and fields can be found in the appendices. Cover Title Page Copyright Page Dedication Page Preface Preface to Second Edition Suggestions to Reader Table of Contents 1 Introduction Exercises 2 The Basic Theory 2.1 Weierstrass Equations 2.2 The Group Law 2.3 Projective Space and the Point at Infinity 2.4 Proof of Associativity 2.4.1 The Theorems of Pappus and Pascal 2.5 Other Equations for Elliptic Curves 2.5.1 Legendre Equation 2.5.2 Cubic Equations 2.5.3 Quartic Equations 2.5.4 Intersection of Two Quadratic Surfaces 2.6 Other Coordinate Systems 2.6.1 Projective Coordinates 2.6.2 Jacobian Coordinates 2.6.3 Edwards Coordinates 2.7 The j-invariant 2.8 Elliptic Curves in Characteristic 2 2.9 Endomorphisms 2.10 Singular Curves 2.11 Elliptic Curves mod n Exercises 3 Torsion Points 3.1 Torsion Points 3.2 Division Polynomials 3.3 The Weil Pairing 3.4 The Tate-Lichtenbaum Pairing Exercises 4 Elliptic Curves over Finite Fields 4.1 Examples 4.2 The Frobenius Endomorphism 4.3 Determining the Group Order 4.3.1 Subfield Curves 4.3.2 Legendre Symbols 4.3.3 Orders of Points 4.3.4 Baby Step, Giant Step 4.4 A Family of Curves 4.5 Schoof’s Algorithm 4.6 Supersingular Curves Exercises 5 The Discrete Logarithm Problem 5.1 The Index Calculus 5.2 General Attacks on Discrete Logs 5.2.1 Baby Step, Giant Step 5.2.2 Pollard’s ρ and λ Methods 5.2.3 The Pohlig-Hellman Method 5.3 Attacks with Pairings 5.3.1 The MOV Attack 5.3.2 The Frey-Rück Attack 5.4 Anomalous Curves 5.5 Other Attacks Exercises 6 Elliptic Curve Cryptography 6.1 The Basic Setup 6.2 Diffie-Hellman Key Exchange 6.3 Massey-Omura Encryption 6.4 ElGamal Public Key Encryption 6.5 ElGamal Digital Signatures 6.6 The Digital Signature Algorithm 6.7 ECIES 6.8 A Public Key Scheme Based on Factoring 6.9 A Cryptosystem Based on the Weil Pairing Exercises 7 Other Applications 7.1 Factoring Using Elliptic Curves 7.2 Primality Testing Exercises 8 Elliptic Curves over Q 8.1 The Torsion Subgroup. The Lutz-Nagell Theorem 8.2 Descent and the Weak Mordell-Weil Theorem 8.3 Heights and the Mordell-Weil Theorem 8.4 Examples 8.5 The Height Pairing 8.6 Fermat’s Infinite Descent 8.7 2-Selmer Groups; Shafarevich-Tate Groups 8.8 A Nontrivial Shafarevich-Tate Group 8.9 Galois Cohomology Exercises 9 Elliptic Curves over C 9.1 Doubly Periodic Functions 9.2 Tori are Elliptic Curves 9.3 Elliptic Curves over C 9.4 Computing Periods 9.4.1 The Arithmetic-Geometric Mean 9.5 Division Polynomials 9.6 The Torsion Subgroup: Doud’s Method Exercises 10 Complex Multiplication 10.1 Elliptic Curves over C 10.2 Elliptic Curves over Finite Fields 10.3 Integrality of j-invariants 10.4 Numerical Examples 10.5 Kronecker’s Jugendtraum Exercises 11 Divisors 11.1 Definitions and Examples 11.2 The Weil Pairing 11.3 The Tate-Lichtenbaum Pairing 11.4 Computation of the Pairings 11.5 Genus One Curves and Elliptic Curves 11.6 Equivalence of the Definitions of the Pairings 11.6.1 The Weil Pairing 11.6.2 The Tate-Lichtenbaum Pairing 11.7 Nondegeneracy of the Tate-Lichtenbaum Pairing Exercises 12 Isogenies 12.1 The Complex Theory 12.2 The Algebraic Theory 12.3 Vélu’s Formulas 12.4 Point Counting 12.5 Complements Exercises 13 Hyperelliptic Curves 13.1 Basic Definitions 13.2 Divisors 13.3 Cantor’s Algorithm 13.4 The Discrete Logarithm Problem Exercises 14 Zeta Functions 14.1 Elliptic Curves over Finite Fields 14.2 Elliptic Curves over Q Exercises 15 Fermat’s Last Theorem 15.1 Overview 15.2 Galois Representations 15.3 Sketch of Ribet’s Proof 15.4 Sketch of Wiles’s Proof A Number Theory B Groups C Fields D Computer Packages D.1 Pari D.2 Magma D.3 SAGE References Index