Preface xi

Abbreviations and Standard Notation xiii

Chapter I. Introduction 1

I.1. Cryptography Based on Groups 2
I.2. What Types of Group are Used 6
I.3. What it Means in Practice 8

Chapter II. Finite Field Arithmetic 11

II.1. Fields of Odd Characteristic 11
II.2. Fields of Characteristic Two 19

Chapter III. Arithmetic on an Elliptic Curve 29

III.1. General Elliptic Curves 30
III.2. The Group Law 31
III.3. Elliptic Curves over Finite Fields 34
III.4. The Division Polynomials 39
III.5. The Weil Pairing 42
III.6. Isogenies, Endomorphisms and Torsion 44
III.7. Various Functions and q-Expansions 46
III.8. Modular Polynomials and Variants 50

Chapter IV. Efficient Implementation of Elliptic Curves 57

IV.1. Point Addition 57
IV.2. Point Multiplication 62
IV.3. Frobenius Expansions 73
IV.4. Point Compression 76

Chapter V. The Elliptic Curve Discrete Logarithm Problem 79

V.1. The Simplification of Pohlig and Hellman 80
V.2. The MOV Attack 82
V.3. The Anomalous Attack 88
V.4. Baby Step/Giant Step 91
V.5. Tame and Wild Kangaroos 93
V.6. Index Calculus Methods 97
V.7. Summary 98

Chapter VI. Determining the Group Order 101

VI.1. Main Approaches 101
VI.2. Checking the Group Order 103
VI.3. The Method of Shanks and Mestre 104
VI.4. Subfield Curves 104
VI.5. Searching for Good Curves 106

Chapter VII. Schoof's Algorithm and Extensions 109

VII.1. Schoof 's Algorithm 109
VII.2. Beyond Schoof 114
VII.3. More on the Modular Polynomials 118
VII.4. Finding Factors of Division Polynomials
through Isogenies: Odd Characteristic 122
VII.5. Finding Factors of Division Polynomials
through Isogenies: Characteristic Two 133
VII.6. Determining the Trace Modulo a Prime Power 138
VII.7. The Elkies Procedure 139
VII.8. The Atkin Procedure 140
VII.9. Combining the Information from Elkies and Atkin Primes 142
VII.10. Examples 144
VII.11. Further Discussion 147

Chapter VIII. Generating Curves using Complex Multiplication 149

VIII.1. The Theory of Complex Multiplication 149
VIII.2. Generating Curves over Large Prime Fields using CM 151
VIII.3. Weber Polynomials 155
VIII.4. Further Discussion 157

Chapter IX. Other Applications of Elliptic Curves 159

IX.1. Factoring Using Elliptic Curves 159
IX.2. The Pocklington-Lehmer Primality Test 162
IX.3. The ECPP Algorithm 164
IX.4. Equivalence between DLP and DHP 166

Chapter X. Hyperelliptic Cryptosystems 171

X.1. Arithmetic of Hyperelliptic Curves 171
X.2. Generating Suitable Curves 173
X.3. The Hyperelliptic Discrete Logarithm Problem 176

Appendix A. Curve Examples 181

A.1. Odd Characteristic 181
A.2. Characteristic Two 186

Bibliography 191

Author Index 199

Subject Index 201