Topics in Computational Number Theory Inspired by Peter L. Montgomery (London Mathematical Society Lecture Note)

Peter L. Montgomery has made significant contributions to computational number theory, introducing many basic tools such as Montgomery multiplication, Montgomery simultaneous inversion, Montgomery curves, and the Montgomery ladder. This book features state-of-the-art research in computational number theory related to Montgomery's work and its impact on computational efficiency and cryptography. Topics cover a wide range of topics such as Montgomery multiplication for both hardware and software implementations; Montgomery curves and twisted Edwards curves as proposed in the latest standards for elliptic curve cryptography; and cryptographic pairings. This book provides a comprehensive overview of integer factorization techniques, including dedicated chapters on polynomial selection, the block Lanczos method, and the FFT extension for algebraic-group factorization algorithms. Graduate students and researchers in applied number theory and cryptography will benefit from this survey of Montgomery's work. Contents 5 Contributors 12 Preface 14 1 Introduction 16 1.1 Outline 16 1.2 Biographical Sketch 16 1.3 Overview 20 1.4 Simultaneous Inversion 23 2 Montgomery Arithmetic from a Software Perspective 25 2.1 Introduction 25 2.2 Montgomery Multiplication 27 2.2.1 Interleaved Montgomery Multiplication 30 2.2.2 Using Montgomery Arithmetic in Practice 31 2.2.3 Computing the Montgomery Constants μ and R2 33 2.2.4 On the Final Conditional Subtraction 34 2.2.5 Montgomery Multiplication in F2k 36 2.3 Using Primes of a Special Form 37 2.3.1 Faster Modular Reduction with Primes of a Special Form 38 2.3.2 Faster Montgomery Reduction with Primes of a Special Form 39 2.4 Concurrent Computing of Montgomery Multiplication 41 2.4.1 Related Work on Concurrent Computing of Montgomery Multiplication 42 2.4.2 Montgomery Multiplication Using SIMD Extensions 42 2.4.3 A Column-Wise SIMD Approach 46 2.4.4 Montgomery Multiplication Using the Residue Number System Representation 51 3 Hardware Aspects of Montgomery Modular Multiplication 55 3.1 Introduction and Summary 55 3.2 Historical Remarks 57 3.3 Montgomery’s Novel Modular Multiplication Algorithm 57 3.4 Standard Acceleration Techniques 58 3.5 Shifting the Modulus N 59 3.5.1 The Classical Algorithm 59 3.5.2 Montgomery 60 3.6 Interleaving Multiplication Steps with Modular Reduction 61 3.7 Accepting Inaccuracy in Quotient Digits 63 3.7.1 Traditional 63 3.7.2 Bounding the Partial Product 65 3.7.3 Montgomery 67 3.7.4 Summary 67 3.8 Using Redundant Representations 68 3.8.1 Traditional 69 3.8.2 Montgomery 69 3.9 Changing the Size of the Hardware Multiplier 70 3.10 Shifting an Operand 72 3.10.1 Traditional 72 3.10.2 Montgomery 75 3.11 Precomputing Multiples of B and N 76 3.12 Propagating Carries and Carry-Save Inputs 77 3.13 Scaling the Modulus 80 3.14 Systolic Arrays 82 3.14.1 A Systolic Array for A×B 83 3.14.2 Scalability 85 3.14.3 A Linear Systolic Array 87 3.14.4 A Systolic Array for Modular Multiplication 88 3.15 Side-Channel Concerns and Solutions 91 3.16 Logic Gate Technology 95 3.17 Conclusion 96 4 Montgomery Curves and the Montgomery Ladder 97 4.1 Introduction 97 4.2 Fast Scalar Multiplication on the Clock 98 4.2.1 The Lucas Ladder 100 4.2.2 Differential Addition Chains 100 4.3 Montgomery Curves 102 4.3.1 Montgomery Curves as Weierstrass Curves 102 4.3.2 The Group Law for Weierstrass Curves 103 4.3.3 Other Views of the Group Law 104 4.3.4 Edwards Curves and Their Group Law 105 4.3.5 Montgomery Curves as Edwards Curves 107 4.3.6 Elliptic-Curve Cryptography (ECC) 108 4.3.7 Examples of Noteworthy Montgomery Curves 109 4.4 Doubling Formulas without y 110 4.4.1 Doubling: The Weierstrass View 110 4.4.2 Optimized Doublings 111 4.4.3 A Word of Warning: Projective Coordinates 112 4.4.4 Completeness of Generic Doubling Formulas 112 4.4.5 Doubling: The Edwards View 113 4.5 Differential-Addition Formulas 114 4.5.1 Differential Addition: The Weierstrass View 114 4.5.2 Optimized Differential Addition 116 4.5.3 Quasi-Completeness 116 4.5.4 Differential Addition: The Edwards View 118 4.6 The Montgomery Ladder 119 4.6.1 The Montgomery Ladder Step 119 4.6.2 Constant-Time Ladders 120 4.6.3 Completeness of the Ladder 121 4.7 A Two-Dimensional Ladder 122 4.7.1 Introduction to the Two-Dimensional Ladder 123 4.7.2 Recursive Definition of the Two-Dimensional Ladder 124 4.7.3 The Odd-Odd Pair in Each Line: First Addition 125 4.7.4 The Even-Even Pair in Each Line: Doubling 125 4.7.5 The Other Pair in Each Line: Second Addition 126 4.8 Larger Differences 126 4.8.1 Examples of Large-Difference Chains 127 4.8.2 CFRC, PRAC, etc 129 4.8.3 Allowing d to Vary 129 5 General Purpose Integer Factoring 131 5.1 Introduction 131 5.2 General Purpose Factoring 132 5.2.1 Two-Step Approach 132 5.2.2 Smoothness and L-notation 134 5.2.3 Generic Analysis 135 5.2.4 Smoothness Testing 136 5.2.5 Finding Dependencies 138 5.2.6 Filtering 138 5.2.7 Overall Effort 141 5.3 Presieving General Purpose Factoring 141 5.3.1 Dixon’s Random Squares Method 141 5.3.2 Continued Fraction Method 142 5.4 Linear and Quadratic Sieve 144 5.4.1 Linear Sieve 144 5.4.2 Quadratic Sieving: Plain 147 5.4.3 Quadratic Sieving: Fancy 148 5.4.4 Multiple Polynomial Quadratic Sieve 149 5.5 Number Field Sieve 152 5.5.1 Earlier Methods to Compute Discrete Logarithms 154 5.5.2 Special Number Field Sieve 160 5.5.3 General Number Field Sieve 167 5.5.4 Coppersmith’s Modifications 173 5.6 Provable Methods 175 6 Polynomial Selection for the Number Field Sieve 176 6.1 The Problem 176 6.2 Early Methods 176 6.3 General Remarks 179 6.4 A Lattice Based Method 181 6.5 Skewness 183 6.6 Base m Method and Skewness 185 6.7 Root Sieve 186 6.8 Later Developments 188 7 The Block Lanczos Algorithm 190 7.1 Linear Systems for Integer Factoring 190 7.2 The Standard Lanczos Algorithm 191 7.3 The Case of Characteristic Two 194 7.4 Orthogonalizing a Sequence of Subspaces 195 7.5 Construction of the Next Iterate 196 7.6 Simplifying the Recurrence Equation 197 7.7 Termination 199 7.8 Implementation in Parallel 201 7.9 Recent Developments 202 8 FFT Extension for Algebraic-Group Factorization Algorithms 204 8.1 Introduction 204 8.2 FFT Extension for the Elliptic Curve Method 206 8.2.1 The Product Tree Algorithm 207 8.2.2 The POLYEVAL Algorithm 207 8.2.3 The POLYGCD Algorithm 210 8.2.4 Choice of Points of Evaluation 212 8.2.5 A Numerical Example 214 8.3 FFT Extension for the p − 1 and p + 1 Methods 214 8.3.1 Constructing F(X ) by Scaling and Multiplying 216 8.3.2 Evaluation of a Polynomial Along a Geometric Progression 217 9 Cryptographic Pairings 221 9.1 Preliminaries 222 9.1.1 Elliptic Curves 223 9.1.2 Pairings 224 9.1.3 Pairing-Friendly Elliptic Curves 228 9.2 Finite Field Arithmetic for Pairings 228 9.2.1 Montgomery Multiplication 229 9.2.2 Multiplication in Extension Fields 230 9.2.3 Finite Field Inversions 230 9.2.4 Simultaneous Inversions 233 9.3 Affine Coordinates for Pairing Computation 234 9.3.1 Costs for Doubling and Addition Steps 234 9.3.2 Working over Extension Fields 238 9.3.3 Simultaneous Inversions in Pairing Computation 240 9.4 The Double-Add Operation and Parabolas 242 9.4.1 Description of the Algorithm 243 9.4.2 Application to Scalar Multiplication 244 9.4.3 Application to Pairings 244 9.5 Squared Pairings 246 9.5.1 The Squared Weil Pairing 247 9.5.2 The Squared Tate Pairing 248 Bibliography 250 Subject Index 276 Contents......Page 5 Contributors......Page 12 Preface......Page 14 1.2 Biographical Sketch......Page 16 1.3 Overview......Page 20 1.4 Simultaneous Inversion......Page 23 2.1 Introduction......Page 25 2.2 Montgomery Multiplication......Page 27 2.2.1 Interleaved Montgomery Multiplication......Page 30 2.2.2 Using Montgomery Arithmetic in Practice......Page 31 2.2.3 Computing the Montgomery Constants μ and R2......Page 33 2.2.4 On the Final Conditional Subtraction......Page 34 2.2.5 Montgomery Multiplication in F2k......Page 36 2.3 Using Primes of a Special Form......Page 37 2.3.1 Faster Modular Reduction with Primes of a Special Form......Page 38 2.3.2 Faster Montgomery Reduction with Primes of a Special Form......Page 39 2.4 Concurrent Computing of Montgomery Multiplication......Page 41 2.4.2 Montgomery Multiplication Using SIMD Extensions......Page 42 2.4.3 A Column-Wise SIMD Approach......Page 46 2.4.4 Montgomery Multiplication Using the Residue Number System Representation......Page 51 3.1 Introduction and Summary......Page 55 3.3 Montgomery’s Novel Modular Multiplication Algorithm......Page 57 3.4 Standard Acceleration Techniques......Page 58 3.5.1 The Classical Algorithm......Page 59 3.5.2 Montgomery......Page 60 3.6 Interleaving Multiplication Steps with Modular Reduction......Page 61 3.7.1 Traditional......Page 63 3.7.2 Bounding the Partial Product......Page 65 3.7.4 Summary......Page 67 3.8 Using Redundant Representations......Page 68 3.8.2 Montgomery......Page 69 3.9 Changing the Size of the Hardware Multiplier......Page 70 3.10.1 Traditional......Page 72 3.10.2 Montgomery......Page 75 3.11 Precomputing Multiples of B and N......Page 76 3.12 Propagating Carries and Carry-Save Inputs......Page 77 3.13 Scaling the Modulus......Page 80 3.14 Systolic Arrays......Page 82 3.14.1 A Systolic Array for A×B......Page 83 3.14.2 Scalability......Page 85 3.14.3 A Linear Systolic Array......Page 87 3.14.4 A Systolic Array for Modular Multiplication......Page 88 3.15 Side-Channel Concerns and Solutions......Page 91 3.16 Logic Gate Technology......Page 95 3.17 Conclusion......Page 96 4.1 Introduction......Page 97 4.2 Fast Scalar Multiplication on the Clock......Page 98 4.2.2 Differential Addition Chains......Page 100 4.3.1 Montgomery Curves as Weierstrass Curves......Page 102 4.3.2 The Group Law for Weierstrass Curves......Page 103 4.3.3 Other Views of the Group Law......Page 104 4.3.4 Edwards Curves and Their Group Law......Page 105 4.3.5 Montgomery Curves as Edwards Curves......Page 107 4.3.6 Elliptic-Curve Cryptography (ECC)......Page 108 4.3.7 Examples of Noteworthy Montgomery Curves......Page 109 4.4.1 Doubling: The Weierstrass View......Page 110 4.4.2 Optimized Doublings......Page 111 4.4.4 Completeness of Generic Doubling Formulas......Page 112 4.4.5 Doubling: The Edwards View......Page 113 4.5.1 Differential Addition: The Weierstrass View......Page 114 4.5.3 Quasi-Completeness......Page 116 4.5.4 Differential Addition: The Edwards View......Page 118 4.6.1 The Montgomery Ladder Step......Page 119 4.6.2 Constant-Time Ladders......Page 120 4.6.3 Completeness of the Ladder......Page 121 4.7 A Two-Dimensional Ladder......Page 122 4.7.1 Introduction to the Two-Dimensional Ladder......Page 123 4.7.2 Recursive Definition of the Two-Dimensional Ladder......Page 124 4.7.4 The Even-Even Pair in Each Line: Doubling......Page 125 4.8 Larger Differences......Page 126 4.8.1 Examples of Large-Difference Chains......Page 127 4.8.3 Allowing d to Vary......Page 129 5.1 Introduction......Page 131 5.2.1 Two-Step Approach......Page 132 5.2.2 Smoothness and L-notation......Page 134 5.2.3 Generic Analysis......Page 135 5.2.4 Smoothness Testing......Page 136 5.2.6 Filtering......Page 138 5.3.1 Dixon’s Random Squares Method......Page 141 5.3.2 Continued Fraction Method......Page 142 5.4.1 Linear Sieve......Page 144 5.4.2 Quadratic Sieving: Plain......Page 147 5.4.3 Quadratic Sieving: Fancy......Page 148 5.4.4 Multiple Polynomial Quadratic Sieve......Page 149 5.5 Number Field Sieve......Page 152 5.5.1 Earlier Methods to Compute Discrete Logarithms......Page 154 5.5.2 Special Number Field Sieve......Page 160 5.5.3 General Number Field Sieve......Page 167 5.5.4 Coppersmith’s Modifications......Page 173 5.6 Provable Methods......Page 175 6.2 Early Methods......Page 176 6.3 General Remarks......Page 179 6.4 A Lattice Based Method......Page 181 6.5 Skewness......Page 183 6.6 Base m Method and Skewness......Page 185 6.7 Root Sieve......Page 186 6.8 Later Developments......Page 188 7.1 Linear Systems for Integer Factoring......Page 190 7.2 The Standard Lanczos Algorithm......Page 191 7.3 The Case of Characteristic Two......Page 194 7.4 Orthogonalizing a Sequence of Subspaces......Page 195 7.5 Construction of the Next Iterate......Page 196 7.6 Simplifying the Recurrence Equation......Page 197 7.7 Termination......Page 199 7.8 Implementation in Parallel......Page 201 7.9 Recent Developments......Page 202 8.1 Introduction......Page 204 8.2 FFT Extension for the Elliptic Curve Method......Page 206 8.2.2 The POLYEVAL Algorithm......Page 207 8.2.3 The POLYGCD Algorithm......Page 210 8.2.4 Choice of Points of Evaluation......Page 212 8.3 FFT Extension for the p − 1 and p + 1 Methods......Page 214 8.3.1 Constructing F(X ) by Scaling and Multiplying......Page 216 8.3.2 Evaluation of a Polynomial Along a Geometric Progression......Page 217 9 Cryptographic Pairings......Page 221 9.1 Preliminaries......Page 222 9.1.1 Elliptic Curves......Page 223 9.1.2 Pairings......Page 224 9.2 Finite Field Arithmetic for Pairings......Page 228 9.2.1 Montgomery Multiplication......Page 229 9.2.3 Finite Field Inversions......Page 230 9.2.4 Simultaneous Inversions......Page 233 9.3.1 Costs for Doubling and Addition Steps......Page 234 9.3.2 Working over Extension Fields......Page 238 9.3.3 Simultaneous Inversions in Pairing Computation......Page 240 9.4 The Double-Add Operation and Parabolas......Page 242 9.4.1 Description of the Algorithm......Page 243 9.4.3 Application to Pairings......Page 244 9.5 Squared Pairings......Page 246 9.5.1 The Squared Weil Pairing......Page 247 9.5.2 The Squared Tate Pairing......Page 248 Bibliography......Page 250 Subject Index......Page 276 Written in honor of Peter L. Montgomery, this book surveys his many contributions to computational number theory and cryptography. For graduate students and researchers, it features state-of-the-art research by experts in the field focusing on the impact of Montgomery's ideas and algorithms on computational efficiency and cryptographic security.