BIGNUM MATH

By D. CAZIO

CONTENTS INTRODUCTION MULTIPLE PRECISION ARITHMETIC WHAT IS MULTIPLE PRECISION ARITHMETIC? THE NEED FOR MULTIPLE PRECISION ARITHMETIC BENE?TS OF MULTIPLE PRECISION ARITHMETIC PURPOSE OF THIS TEXT DISCUSSION AND NOTATION NOTATION PRECISION NOTATION ALGORITHM INPUTS AND OUTPUTS MATHEMATICAL EXPRESSIONS WORK E?ORT EXERCISES INTRODUCTION TO LIBTOMMATH WHAT IS LIBTOMMATH? GOALS OF LIBTOMMATH CHOICE OF LIBTOMMATH CODE BASE API SIMPLICITY OPTIMIZATIONS PORTABILITY AND STABILITY CHOICE GETTING STARTED LIBRARY BASICS WHAT IS A MULTIPLE PRECISION INTEGER? THE MP INT STRUCTURE ARGUMENT PASSING RETURN VALUES INITIALIZATION AND CLEARING INITIALIZING AN MP INT CLEARING AN MP INT MAINTENANCE ALGORITHMS AUGMENTING AN MP INT’S PRECISION INITIALIZING VARIABLE PRECISION MP INTS MULTIPLE INTEGER INITIALIZATIONS AND CLEARINGS CLAMPING EXCESS DIGITS BASIC OPERATIONS ASSIGNING VALUES TO MP INT STRUCTURES COPYING AN MP INT CREATING A CLONE ZEROING AN INTEGER SIGN MANIPULATION ABSOLUTE VALUE INTEGER NEGATION SMALL CONSTANTS SETTING SMALL CONSTANTS SETTING LARGE CONSTANTS COMPARISONS UNSIGNED COMPARISONS SIGNED COMPARISONS BASIC ARITHMETIC ADDITION AND SUBTRACTION LOW LEVEL ADDITION LOW LEVEL SUBTRACTION HIGH LEVEL ADDITION HIGH LEVEL SUBTRACTION BIT AND DIGIT SHIFTING MULTIPLICATION BY TWO DIVISION BY TWO POLYNOMIAL BASIS OPERATIONS MULTIPLICATION BY X DIVISION BY X POWERS OF TWO MULTIPLICATION BY POWER OF TWO DIVISION BY POWER OF TWO REMAINDER OF DIVISION BY POWER OF TWO MULTIPLICATION AND SQUARING THE MULTIPLIERS MULTIPLICATION THE BASELINE MULTIPLICATION FASTER MULTIPLICATION BY THE “COMBA” METHOD EVEN FASTER MULTIPLICATION POLYNOMIAL BASIS MULTIPLICATION KARATSUBA MULTIPLICATION TOOM-COOK 3-WAY MULTIPLICATION SIGNED MULTIPLICATION SQUARING THE BASELINE SQUARING ALGORITHM FASTER SQUARING BY THE “COMBA” METHOD EVEN FASTER SQUARING POLYNOMIAL BASIS SQUARING KARATSUBA SQUARING TOOM-COOK SQUARING HIGH LEVEL SQUARING MODULAR REDUCTION BASICS OF MODULAR REDUCTION THE BARRETT REDUCTION FIXED POINT ARITHMETIC CHOOSING A RADIX POINT TRIMMING THE QUOTIENT TRIMMING THE RESIDUE THE BARRETT ALGORITHM THE BARRETT SETUP ALGORITHM THE MONTGOMERY REDUCTION DIGIT BASED MONTGOMERY REDUCTION BASELINE MONTGOMERY REDUCTION FASTER “COMBA” MONTGOMERY REDUCTION MONTGOMERY SETUP THE DIMINISHED RADIX ALGORITHM CHOICE OF MODULI CHOICE OF K RESTRICTED DIMINISHED RADIX REDUCTION UNRESTRICTED DIMINISHED RADIX REDUCTION ALGORITHM COMPARISON EXPONENTIATION EXPONENTIATION BASICS SINGLE DIGIT EXPONENTIATION K-ARY EXPONENTIATION OPTIMAL VALUES OF K SLIDING WINDOW EXPONENTIATION MODULAR EXPONENTIATION BARRETT MODULAR EXPONENTIATION QUICK POWER OF TWO HIGHER LEVEL ALGORITHMS INTEGER DIVISION WITH REMAINDER QUOTIENT ESTIMATION NORMALIZED INTEGERS RADIX-? DIVISION WITH REMAINDER SINGLE DIGIT HELPERS SINGLE DIGIT ADDITION AND SUBTRACTION SINGLE DIGIT MULTIPLICATION SINGLE DIGIT DIVISION SINGLE DIGIT ROOT EXTRACTION RANDOM NUMBER GENERATION FORMATTED REPRESENTATIONS READING RADIX-N INPUT GENERATING RADIX-N OUTPUT NUMBER THEORETIC ALGORITHMS GREATEST COMMON DIVISOR COMPLETE GREATEST COMMON DIVISOR LEAST COMMON MULTIPLE JACOBI SYMBOL COMPUTATION JACOBI SYMBOL MODULAR INVERSE GENERAL CASE PRIMALITY TESTS TRIAL DIVISION THE FERMAT TEST THE MILLER-RABIN TEST BIBLIOGRAPHY