Chapter 14 Contents

Chapter 14 Contents
14 Efficient Implementation
14.1 Introduction
14.2 Multiple-precision integer arithmetic
14.2.1 Radix representation
14.2.2 Addition and subtraction
14.2.3 Multiplication
14.2.4 Squaring
14.2.5 Division
14.3 Multiple-precision modular arithmetic
14.3.1 Classical modular multiplication
14.3.2 Montgomery reduction
14.3.3 Barrett reduction
14.3.4 Reduction methods for moduli of special form
14.4 Greatest common divisor algorithms
14.4.1 Binary gcd algorithm
14.4.2 Lehmer's gcd algorithm
14.4.3 Binary extended gcd algorithm
14.5 Chinese remainder theorem for integers
14.5.1 Residue number systems
14.5.2 Garner's algorithm
14.6 Exponentiation
14.6.1 Techniques for general exponentiation
14.6.2 Fixed-exponent exponentiation algorithms
14.6.3 Fixed-base exponentiation algorithms
14.7 Exponent recoding
14.7.1 Signed-digit representation
14.7.2 String-replacement representation
14.8 Notes and further references
Return to the Table of contents