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.
Author(s): Joppe W. Bos, Arjen K. Lenstra
Publisher: Cambridge University Press
Year: 2017
Language: English
Pages: 281
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
