BigNum Math
Implementing Cryptographic Multiple Precision Arithmetic
- 1st Edition - August 18, 2006
- Latest edition
- Author: Tom St Denis
- Language: English
Implementing cryptography requires integers of significant magnitude to resist cryptanalytic attacks. Modern programming languages only provide support for integers which are… Read more
Implementing cryptography requires integers of significant magnitude to resist cryptanalytic attacks. Modern programming languages only provide support for integers which are relatively small and single precision. The purpose of this text is to instruct the reader regarding how to implement efficient multiple precision algorithms.
Bignum math is the backbone of modern computer security algorithms. It is the ability to work with hundred-digit numbers efficiently using techniques that are both elegant and occasionally bizarre. This book introduces the reader to the concept of bignum algorithms and proceeds to build an entire library of functionality from the ground up. Through the use of theory, pseudo-code and actual fielded C source code the book explains each and every algorithm that goes into a modern bignum library. Excellent for the student as a learning tool and practitioner as a reference alike BigNum Math is for anyone with a background in computer science who has taken introductory level mathematic courses. The text is for students learning mathematics and cryptography as well as the practioner who needs a reference for any of the algorithms documented within.
Bignum math is the backbone of modern computer security algorithms. It is the ability to work with hundred-digit numbers efficiently using techniques that are both elegant and occasionally bizarre. This book introduces the reader to the concept of bignum algorithms and proceeds to build an entire library of functionality from the ground up. Through the use of theory, pseudo-code and actual fielded C source code the book explains each and every algorithm that goes into a modern bignum library. Excellent for the student as a learning tool and practitioner as a reference alike BigNum Math is for anyone with a background in computer science who has taken introductory level mathematic courses. The text is for students learning mathematics and cryptography as well as the practioner who needs a reference for any of the algorithms documented within.
* Complete coverage of Karatsuba Multiplication, the Barrett Algorithm, Toom-Cook 3-Way Multiplication, and More
* Tom St Denis is the developer of the industry standard cryptographic suite of tools called LibTom.
* This book provides step-by-step exercises to enforce concepts
* Tom St Denis is the developer of the industry standard cryptographic suite of tools called LibTom.
* This book provides step-by-step exercises to enforce concepts
Any programmer implementing public-key cryptography algorithms needs to grasp BigNum Math. BigNum Math is for anyone with a background in computer science who has taken introductory level mathematic courses. The text is for students learning mathematics and cryptography as well as the practioner who needs a reference for any of the algorithms documented within.
Introduction 1
1.1 Multiple Precision Arithmetic
1.1.1 What is Multiple Precision Arithmetic?
1.1.2 The Need for Multiple Precision Arithmetic
1.1.3 Benefits of Multiple Precision Arithmetic
1.2 Purpose of This Text
1.3 Discussion and Notation
1.3.1 Notation
1.3.2 Precision Notation
1.3.3 Algorithm Inputs and Outputs
1.3.4 Mathematical Expressions
1.4 Exercises
1.5 Introduction to LibTomMath
1.5.1 What is LibTomMath?
1.5.2 Goals of LibTomMath
1.6 Choice of LibTomMath
1.6.1 Code Base
1.6.3 Optimizations
1.6.4 Portability and Stability
1.6.5 Choice
2 Getting Started 13
2.1 Library Basics
2.2 What is a Multiple Precision Integer?
2.2.1 The mp int Structure
2.3 Argument Passing
2.5 Initialization and Clearing
2.5.1 Initializing an mp int
2.5.2 Clearing an mp int
2.6 Maintenance Algorithms
2.6.1 Augmenting an mp int’s Precision
2.6.2 Initializing Variable Precision mp ints
2.6.3 Multiple Integer Initializations and Clearings
2.6.4 Clamping Excess Digit
3 Basic Operations 35
3.1 Introduction
3.2 Assigning Values to mp int Structures
3.2.1 Copying an mp int
3.3 Zeroing an Integer .
3.4 Sign Manipulation
3.4.1 Absolute Value
3.4.2 Integer Negation
3.5.1 Setting Small Constants .
3.5.2 Setting Large Constants .
3.6 Comparisons .
3.6.1 Unsigned Comparisions
3.6.2 Signed Comparisons
4 Basic Arithmetic 53
4.1 Introduction
4.2.2 Low Level Subtraction
4.2.4 High Level Subtractio
4.3 Bit and Digit Shifting
4.3.2 Division by Two
4.4 Polynomial Basis Operation
4.4.1 Multiplication by x .
4.4.2 Division by x
4.5 Powers of Two
4.5.1 Multiplication by Power of Two
4.5.2 Division by Power of Two
4.5.3 Remainder of Division by Power of Two
5 Multiplication and Squaring 91
5.1 The Multipliers
5.2 Multiplication
5.2.1 The Baseline Multiplication
5.2.2 Faster Multiplication by the “Comba” Method
5.2.3 Polynomial Basis Multiplication
5.2.5 Toom-Cook 3-Way Multiplication
5.2.6 Signed Multiplication
5.3 Squaring
5.3.1 The Baseline Squaring Algorithm
5.3.2 Faster Squaring by the “Comba” Method
5.3.3 Polynomial Basis Squaring
5.3.4 Karatsuba Squaring
5.3.5 Toom-Cook Squaring
5.3.6 High Level Squaring
6.2 The Barrett Reduction
6.2.1 Fixed Point Arithmetic . .
6.2.5 The Barrett Algorithm
6.2.6 The Barrett Setup Algorithm
6.3 The Montgomery Reduction .
6.3.1 Digit Based Montgomery Reduction
6.3.2 Baseline Montgomery Reduction
6.3.3 Faster “Comba” Montgomery Reduction
6.3.4 Montgomery Setup
6.4 The Diminished Radix Algorithm
6.4.1 Choice of Moduli
6.4.2 Choice of k
6.4.3 Restricted Diminished Radix Reduction
6.4.4 Unrestricted Diminished Radix Reduction
6.5 Algorithm Comparison .
7 Exponentiation 187
7.1 Exponentiation Basics
7.1.1 Single Digit Exponentiation
7.2.1 Optimal Values of k
7.2.2 Sliding-Window Exponentiation
7.3 Modular Exponentiation
7.3.1 Barrett Modular Exponentiation
7.4 Quick Power of Two
8 Higher Level Algorithms 211
8.1 Integer Division with Remainde
8.1.1 Quotient Estimation
8.1.2 Normalized Integers
8.1.3 Radix-ß Division with Remainder
8.2 Single Digit Helpers
8.2.2 Single Digit Multiplication
8.2.3 Single Digit Division
8.2.4 Single Digit Root Extraction
8.3 Random Number Generation
8.4 Formatted Representations
8.4.1 Reading Radix-n Input
8.4.2 Generating Radix-n Output
9 Number Theoretic Algorithms
9.1 Greatest Common Divisor
9.2 Least Common Multiple
9.3 Jacobi Symbol Computation
9.3.1 Jacobi Symbol
9.4 Modular Inverse
9.4.1 General Case
9.5 Primality Tests
9.5.2 The Fermat Test
9.5.3 The Miller-Rabin Test
1.1 Multiple Precision Arithmetic
1.1.1 What is Multiple Precision Arithmetic?
1.1.2 The Need for Multiple Precision Arithmetic
1.1.3 Benefits of Multiple Precision Arithmetic
1.2 Purpose of This Text
1.3 Discussion and Notation
1.3.1 Notation
1.3.2 Precision Notation
1.3.3 Algorithm Inputs and Outputs
1.3.4 Mathematical Expressions
1.4 Exercises
1.5 Introduction to LibTomMath
1.5.1 What is LibTomMath?
1.5.2 Goals of LibTomMath
1.6 Choice of LibTomMath
1.6.1 Code Base
1.6.3 Optimizations
1.6.4 Portability and Stability
1.6.5 Choice
2 Getting Started 13
2.1 Library Basics
2.2 What is a Multiple Precision Integer?
2.2.1 The mp int Structure
2.3 Argument Passing
2.5 Initialization and Clearing
2.5.1 Initializing an mp int
2.5.2 Clearing an mp int
2.6 Maintenance Algorithms
2.6.1 Augmenting an mp int’s Precision
2.6.2 Initializing Variable Precision mp ints
2.6.3 Multiple Integer Initializations and Clearings
2.6.4 Clamping Excess Digit
3 Basic Operations 35
3.1 Introduction
3.2 Assigning Values to mp int Structures
3.2.1 Copying an mp int
3.3 Zeroing an Integer .
3.4 Sign Manipulation
3.4.1 Absolute Value
3.4.2 Integer Negation
3.5.1 Setting Small Constants .
3.5.2 Setting Large Constants .
3.6 Comparisons .
3.6.1 Unsigned Comparisions
3.6.2 Signed Comparisons
4 Basic Arithmetic 53
4.1 Introduction
4.2.2 Low Level Subtraction
4.2.4 High Level Subtractio
4.3 Bit and Digit Shifting
4.3.2 Division by Two
4.4 Polynomial Basis Operation
4.4.1 Multiplication by x .
4.4.2 Division by x
4.5 Powers of Two
4.5.1 Multiplication by Power of Two
4.5.2 Division by Power of Two
4.5.3 Remainder of Division by Power of Two
5 Multiplication and Squaring 91
5.1 The Multipliers
5.2 Multiplication
5.2.1 The Baseline Multiplication
5.2.2 Faster Multiplication by the “Comba” Method
5.2.3 Polynomial Basis Multiplication
5.2.5 Toom-Cook 3-Way Multiplication
5.2.6 Signed Multiplication
5.3 Squaring
5.3.1 The Baseline Squaring Algorithm
5.3.2 Faster Squaring by the “Comba” Method
5.3.3 Polynomial Basis Squaring
5.3.4 Karatsuba Squaring
5.3.5 Toom-Cook Squaring
5.3.6 High Level Squaring
6.2 The Barrett Reduction
6.2.1 Fixed Point Arithmetic . .
6.2.5 The Barrett Algorithm
6.2.6 The Barrett Setup Algorithm
6.3 The Montgomery Reduction .
6.3.1 Digit Based Montgomery Reduction
6.3.2 Baseline Montgomery Reduction
6.3.3 Faster “Comba” Montgomery Reduction
6.3.4 Montgomery Setup
6.4 The Diminished Radix Algorithm
6.4.1 Choice of Moduli
6.4.2 Choice of k
6.4.3 Restricted Diminished Radix Reduction
6.4.4 Unrestricted Diminished Radix Reduction
6.5 Algorithm Comparison .
7 Exponentiation 187
7.1 Exponentiation Basics
7.1.1 Single Digit Exponentiation
7.2.1 Optimal Values of k
7.2.2 Sliding-Window Exponentiation
7.3 Modular Exponentiation
7.3.1 Barrett Modular Exponentiation
7.4 Quick Power of Two
8 Higher Level Algorithms 211
8.1 Integer Division with Remainde
8.1.1 Quotient Estimation
8.1.2 Normalized Integers
8.1.3 Radix-ß Division with Remainder
8.2 Single Digit Helpers
8.2.2 Single Digit Multiplication
8.2.3 Single Digit Division
8.2.4 Single Digit Root Extraction
8.3 Random Number Generation
8.4 Formatted Representations
8.4.1 Reading Radix-n Input
8.4.2 Generating Radix-n Output
9 Number Theoretic Algorithms
9.1 Greatest Common Divisor
9.2 Least Common Multiple
9.3 Jacobi Symbol Computation
9.3.1 Jacobi Symbol
9.4 Modular Inverse
9.4.1 General Case
9.5 Primality Tests
9.5.2 The Fermat Test
9.5.3 The Miller-Rabin Test
- Edition: 1
- Latest edition
- Published: August 18, 2006
- Language: English
TS
Tom St Denis
Tom St Denis is the author of the industry standard LibTom series of projects. Tom is a senior software developer and cryptographer for the Advanced Micro Devices Corporation. He has been engaged in various international development contracts and speaking engagements since 2004. He is at work on his next book, Cryptography for Developers.
Affiliations and expertise
senior software developer and cryptographer for the Advanced Micro Devices Corporation.Read BigNum Math on ScienceDirect