Bos J.W., Lenstra A.K. (eds.) Topics in Computational Number Theory Inspired by Peter L. Montgomery

Cambridge: Cambridge University Press, 2017. — 281 p.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.Biographical Sketch
Overview
Simultaneous InversionMontgomery Multiplication
Interleaved Montgomery Multiplication
Using Montgomery Arithmetic in Practice
Computing the Montgomery Constants μ and R
On the Final Conditional Subtraction
Montgomery Multiplication in Fk
Using Primes of a Special Form
Faster Modular Reduction with Primes of a Special Form
Faster Montgomery Reduction with Primes of a Special Form
Concurrent Computing of Montgomery Multiplication
Montgomery Multiplication Using SIMD Extensions
A Column-Wise SIMD Approach
Montgomery Multiplication Using the Residue Number System Representation
Introduction and Summary
Montgomery’s Novel Modular Multiplication Algorithm
Standard Acceleration Techniques
The Classical Algorithm
Montgomery
Interleaving Multiplication Steps with Modular Reduction
Traditional
Bounding the Partial ProductUsing Redundant Representations
Montgomery
Changing the Size of the Hardware Multiplier
Traditional
Montgomery
Precomputing Multiples of B and N
Propagating Carries and Carry-Save Inputs
Scaling the Modulus
Systolic Arrays
A Systolic Array for A×B
Scalability
A Linear Systolic Array
A Systolic Array for Modular Multiplication
Side-Channel Concerns and Solutions
Logic Gate TechnologyFast Scalar Multiplication on the Clock
Differential Addition Chains
Montgomery Curves as Weierstrass Curves
The Group Law for Weierstrass Curves
Other Views of the Group Law
Edwards Curves and Their Group Law
Montgomery Curves as Edwards Curves
Elliptic-Curve Cryptography (ECC)
Examples of Noteworthy Montgomery Curves
Doubling: The Weierstrass View
Optimized Doublings
Completeness of Generic Doubling Formulas
Doubling: The Edwards View
Differential Addition: The Weierstrass View
Quasi-Completeness
Differential Addition: The Edwards View
The Montgomery Ladder Step
Constant-Time Ladders
Completeness of the Ladder
A Two-Dimensional Ladder
Introduction to the Two-Dimensional Ladder
Recursive Definition of the Two-Dimensional Ladder
The Even-Even Pair in Each Line: Doubling
Larger Differences
Examples of Large-Difference Chains
Allowing d to VaryTwo-Step Approach
Smoothness and L-notation
Generic Analysis
Smoothness Testing
Filtering
Dixon’s Random Squares Method
Continued Fraction Method
Linear Sieve
Quadratic Sieving: Plain
Quadratic Sieving: Fancy
Multiple Polynomial Quadratic Sieve
Number Field Sieve
Earlier Methods to Compute Discrete Logarithms
Special Number Field Sieve
General Number Field Sieve
Coppersmith’s Modifications
Provable Methods
Early Methods
General Remarks
A Lattice Based Method
Skewness
Base m Method and Skewness
Root Sieve
Later Developments
Linear Systems for Integer Factoring
The Standard Lanczos Algorithm
The Case of Characteristic Two
Orthogonalizing a Sequence of Subspaces
Construction of the Next Iterate
Simplifying the Recurrence Equation
Termination
Implementation in Parallel
Recent DevelopmentsFFT Extension for the Elliptic Curve Method
The POLYEVAL Algorithm
The POLYGCD Algorithm
Choice of Points of Evaluation
FFT Extension for the p − 1 and p + 1 Methods
Constructing F(X ) by Scaling and Multiplying
Evaluation of a Polynomial Along a Geometric Progression
Cryptographic Pairings
Preliminaries
Elliptic Curves
Pairings
Finite Field Arithmetic for Pairings
Montgomery Multiplication
Finite Field Inversions
Simultaneous Inversions
Costs for Doubling and Addition Steps
Working over Extension Fields
Simultaneous Inversions in Pairing Computation
The Double-Add Operation and Parabolas
Description of the Algorithm
Application to Pairings
Squared Pairings
The Squared Weil Pairing
The Squared Tate PairingSubject Index