## BigNum Math: Implementing Cryptographic Multiple Precision ArithmeticImplementing 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. * 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 |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

1 | |

13 | |

Chapter 3 Basic Operations | 35 |

Chapter 4 Basic Arithmetic | 53 |

Chapter 5 Multiplication and Squaring | 91 |

Chapter 6 Modular Reduction | 147 |

Chapter 7 Exponentiation | 191 |

Chapter 8 Higher Level Algorithms | 217 |

Chapter 9 Number Theoretic Algorithms | 255 |

289 | |

291 | |

### Common terms and phrases

a->sign a->used a.sign a.used addition alias aliases allocated array b->used b.used Barrett reduction bignum bitcpy carry column copy data type DIGIT_BIT digs division double precision endif example exponent Figure File function goto ERR goto LBL_ERR goto X1Y1 greatest common divisor ifdef implementation init initialized inner loop input int res iteration ix++ Jacobi symbol Karatsuba multiplication leading digit least common multiple LibTom projects LibTomMath modular exponentiation modular inverse modular reduction modulo Montgomery Reduction mp add mp mul mp sub mp_clamp mp_clear mp_digit mp_int MP_MASK MP_NEG mp_rshd mp_word MP_ZPOS mpcopy mpgrow mpint structure multiple precision integer NULL number of digits oldused operations optimization Output performed pointer polynomial basis precision arithmetic quotient radix point represent residue result return MP_OKAY return res Return(MP significant bit single digit single precision multiplications Sliding Window squaring step subtraction tmpa tmpb tmpc tmpc++ tmpx unsigned winsize zero

### Popular passages

Page 289 - Montgomery. Modular multiplication without trial division. Mathematics of Computation, 44(170):519521, April 1985.

Page xvi - Tom projects, would not exist in its current form if it were not for a plethora of kind people donating their time, resources, and kind words to help support my work.