diff options
author | jan.nijtmans <nijtmans@users.sourceforge.net> | 2016-11-16 15:22:26 (GMT) |
---|---|---|
committer | jan.nijtmans <nijtmans@users.sourceforge.net> | 2016-11-16 15:22:26 (GMT) |
commit | 68111aa5bf7fc228dcfda8beb9de265734925b56 (patch) | |
tree | fed7fb157cbaef79f43a45b27379a0fd2d64e6ea /libtommath/tommath.out | |
parent | 29606e4a7b43adb9f923fb5781d3b9a93d9ba1c8 (diff) | |
parent | 2adcff3e5ba6e09366ef4208ab81768803ba15bd (diff) | |
download | tcl-68111aa5bf7fc228dcfda8beb9de265734925b56.zip tcl-68111aa5bf7fc228dcfda8beb9de265734925b56.tar.gz tcl-68111aa5bf7fc228dcfda8beb9de265734925b56.tar.bz2 |
(experimental) Upgrade to libtommath 1.0 (actually by merging all changes between libtommath 0.42.0 and 1.0). Still to be tested thourougly, before doing anything with it.
Diffstat (limited to 'libtommath/tommath.out')
-rw-r--r-- | libtommath/tommath.out | 278 |
1 files changed, 139 insertions, 139 deletions
diff --git a/libtommath/tommath.out b/libtommath/tommath.out index 9f62617..de4aada 100644 --- a/libtommath/tommath.out +++ b/libtommath/tommath.out @@ -1,139 +1,139 @@ -\BOOKMARK [0][-]{chapter.1}{Introduction}{} -\BOOKMARK [1][-]{section.1.1}{Multiple Precision Arithmetic}{chapter.1} -\BOOKMARK [2][-]{subsection.1.1.1}{What is Multiple Precision Arithmetic?}{section.1.1} -\BOOKMARK [2][-]{subsection.1.1.2}{The Need for Multiple Precision Arithmetic}{section.1.1} -\BOOKMARK [2][-]{subsection.1.1.3}{Benefits of Multiple Precision Arithmetic}{section.1.1} -\BOOKMARK [1][-]{section.1.2}{Purpose of This Text}{chapter.1} -\BOOKMARK [1][-]{section.1.3}{Discussion and Notation}{chapter.1} -\BOOKMARK [2][-]{subsection.1.3.1}{Notation}{section.1.3} -\BOOKMARK [2][-]{subsection.1.3.2}{Precision Notation}{section.1.3} -\BOOKMARK [2][-]{subsection.1.3.3}{Algorithm Inputs and Outputs}{section.1.3} -\BOOKMARK [2][-]{subsection.1.3.4}{Mathematical Expressions}{section.1.3} -\BOOKMARK [2][-]{subsection.1.3.5}{Work Effort}{section.1.3} -\BOOKMARK [1][-]{section.1.4}{Exercises}{chapter.1} -\BOOKMARK [1][-]{section.1.5}{Introduction to LibTomMath}{chapter.1} -\BOOKMARK [2][-]{subsection.1.5.1}{What is LibTomMath?}{section.1.5} -\BOOKMARK [2][-]{subsection.1.5.2}{Goals of LibTomMath}{section.1.5} -\BOOKMARK [1][-]{section.1.6}{Choice of LibTomMath}{chapter.1} -\BOOKMARK [2][-]{subsection.1.6.1}{Code Base}{section.1.6} -\BOOKMARK [2][-]{subsection.1.6.2}{API Simplicity}{section.1.6} -\BOOKMARK [2][-]{subsection.1.6.3}{Optimizations}{section.1.6} -\BOOKMARK [2][-]{subsection.1.6.4}{Portability and Stability}{section.1.6} -\BOOKMARK [2][-]{subsection.1.6.5}{Choice}{section.1.6} -\BOOKMARK [0][-]{chapter.2}{Getting Started}{} -\BOOKMARK [1][-]{section.2.1}{Library Basics}{chapter.2} -\BOOKMARK [1][-]{section.2.2}{What is a Multiple Precision Integer?}{chapter.2} -\BOOKMARK [2][-]{subsection.2.2.1}{The mp\137int Structure}{section.2.2} -\BOOKMARK [1][-]{section.2.3}{Argument Passing}{chapter.2} -\BOOKMARK [1][-]{section.2.4}{Return Values}{chapter.2} -\BOOKMARK [1][-]{section.2.5}{Initialization and Clearing}{chapter.2} -\BOOKMARK [2][-]{subsection.2.5.1}{Initializing an mp\137int}{section.2.5} -\BOOKMARK [2][-]{subsection.2.5.2}{Clearing an mp\137int}{section.2.5} -\BOOKMARK [1][-]{section.2.6}{Maintenance Algorithms}{chapter.2} -\BOOKMARK [2][-]{subsection.2.6.1}{Augmenting an mp\137int's Precision}{section.2.6} -\BOOKMARK [2][-]{subsection.2.6.2}{Initializing Variable Precision mp\137ints}{section.2.6} -\BOOKMARK [2][-]{subsection.2.6.3}{Multiple Integer Initializations and Clearings}{section.2.6} -\BOOKMARK [2][-]{subsection.2.6.4}{Clamping Excess Digits}{section.2.6} -\BOOKMARK [0][-]{chapter.3}{Basic Operations}{} -\BOOKMARK [1][-]{section.3.1}{Introduction}{chapter.3} -\BOOKMARK [1][-]{section.3.2}{Assigning Values to mp\137int Structures}{chapter.3} -\BOOKMARK [2][-]{subsection.3.2.1}{Copying an mp\137int}{section.3.2} -\BOOKMARK [2][-]{subsection.3.2.2}{Creating a Clone}{section.3.2} -\BOOKMARK [1][-]{section.3.3}{Zeroing an Integer}{chapter.3} -\BOOKMARK [1][-]{section.3.4}{Sign Manipulation}{chapter.3} -\BOOKMARK [2][-]{subsection.3.4.1}{Absolute Value}{section.3.4} -\BOOKMARK [2][-]{subsection.3.4.2}{Integer Negation}{section.3.4} -\BOOKMARK [1][-]{section.3.5}{Small Constants}{chapter.3} -\BOOKMARK [2][-]{subsection.3.5.1}{Setting Small Constants}{section.3.5} -\BOOKMARK [2][-]{subsection.3.5.2}{Setting Large Constants}{section.3.5} -\BOOKMARK [1][-]{section.3.6}{Comparisons}{chapter.3} -\BOOKMARK [2][-]{subsection.3.6.1}{Unsigned Comparisions}{section.3.6} -\BOOKMARK [2][-]{subsection.3.6.2}{Signed Comparisons}{section.3.6} -\BOOKMARK [0][-]{chapter.4}{Basic Arithmetic}{} -\BOOKMARK [1][-]{section.4.1}{Introduction}{chapter.4} -\BOOKMARK [1][-]{section.4.2}{Addition and Subtraction}{chapter.4} -\BOOKMARK [2][-]{subsection.4.2.1}{Low Level Addition}{section.4.2} -\BOOKMARK [2][-]{subsection.4.2.2}{Low Level Subtraction}{section.4.2} -\BOOKMARK [2][-]{subsection.4.2.3}{High Level Addition}{section.4.2} -\BOOKMARK [2][-]{subsection.4.2.4}{High Level Subtraction}{section.4.2} -\BOOKMARK [1][-]{section.4.3}{Bit and Digit Shifting}{chapter.4} -\BOOKMARK [2][-]{subsection.4.3.1}{Multiplication by Two}{section.4.3} -\BOOKMARK [2][-]{subsection.4.3.2}{Division by Two}{section.4.3} -\BOOKMARK [1][-]{section.4.4}{Polynomial Basis Operations}{chapter.4} -\BOOKMARK [2][-]{subsection.4.4.1}{Multiplication by x}{section.4.4} -\BOOKMARK [2][-]{subsection.4.4.2}{Division by x}{section.4.4} -\BOOKMARK [1][-]{section.4.5}{Powers of Two}{chapter.4} -\BOOKMARK [2][-]{subsection.4.5.1}{Multiplication by Power of Two}{section.4.5} -\BOOKMARK [2][-]{subsection.4.5.2}{Division by Power of Two}{section.4.5} -\BOOKMARK [2][-]{subsection.4.5.3}{Remainder of Division by Power of Two}{section.4.5} -\BOOKMARK [0][-]{chapter.5}{Multiplication and Squaring}{} -\BOOKMARK [1][-]{section.5.1}{The Multipliers}{chapter.5} -\BOOKMARK [1][-]{section.5.2}{Multiplication}{chapter.5} -\BOOKMARK [2][-]{subsection.5.2.1}{The Baseline Multiplication}{section.5.2} -\BOOKMARK [2][-]{subsection.5.2.2}{Faster Multiplication by the ``Comba'' Method}{section.5.2} -\BOOKMARK [2][-]{subsection.5.2.3}{Polynomial Basis Multiplication}{section.5.2} -\BOOKMARK [2][-]{subsection.5.2.4}{Karatsuba Multiplication}{section.5.2} -\BOOKMARK [2][-]{subsection.5.2.5}{Toom-Cook 3-Way Multiplication}{section.5.2} -\BOOKMARK [2][-]{subsection.5.2.6}{Signed Multiplication}{section.5.2} -\BOOKMARK [1][-]{section.5.3}{Squaring}{chapter.5} -\BOOKMARK [2][-]{subsection.5.3.1}{The Baseline Squaring Algorithm}{section.5.3} -\BOOKMARK [2][-]{subsection.5.3.2}{Faster Squaring by the ``Comba'' Method}{section.5.3} -\BOOKMARK [2][-]{subsection.5.3.3}{Polynomial Basis Squaring}{section.5.3} -\BOOKMARK [2][-]{subsection.5.3.4}{Karatsuba Squaring}{section.5.3} -\BOOKMARK [2][-]{subsection.5.3.5}{Toom-Cook Squaring}{section.5.3} -\BOOKMARK [2][-]{subsection.5.3.6}{High Level Squaring}{section.5.3} -\BOOKMARK [0][-]{chapter.6}{Modular Reduction}{} -\BOOKMARK [1][-]{section.6.1}{Basics of Modular Reduction}{chapter.6} -\BOOKMARK [1][-]{section.6.2}{The Barrett Reduction}{chapter.6} -\BOOKMARK [2][-]{subsection.6.2.1}{Fixed Point Arithmetic}{section.6.2} -\BOOKMARK [2][-]{subsection.6.2.2}{Choosing a Radix Point}{section.6.2} -\BOOKMARK [2][-]{subsection.6.2.3}{Trimming the Quotient}{section.6.2} -\BOOKMARK [2][-]{subsection.6.2.4}{Trimming the Residue}{section.6.2} -\BOOKMARK [2][-]{subsection.6.2.5}{The Barrett Algorithm}{section.6.2} -\BOOKMARK [2][-]{subsection.6.2.6}{The Barrett Setup Algorithm}{section.6.2} -\BOOKMARK [1][-]{section.6.3}{The Montgomery Reduction}{chapter.6} -\BOOKMARK [2][-]{subsection.6.3.1}{Digit Based Montgomery Reduction}{section.6.3} -\BOOKMARK [2][-]{subsection.6.3.2}{Baseline Montgomery Reduction}{section.6.3} -\BOOKMARK [2][-]{subsection.6.3.3}{Faster ``Comba'' Montgomery Reduction}{section.6.3} -\BOOKMARK [2][-]{subsection.6.3.4}{Montgomery Setup}{section.6.3} -\BOOKMARK [1][-]{section.6.4}{The Diminished Radix Algorithm}{chapter.6} -\BOOKMARK [2][-]{subsection.6.4.1}{Choice of Moduli}{section.6.4} -\BOOKMARK [2][-]{subsection.6.4.2}{Choice of k}{section.6.4} -\BOOKMARK [2][-]{subsection.6.4.3}{Restricted Diminished Radix Reduction}{section.6.4} -\BOOKMARK [2][-]{subsection.6.4.4}{Unrestricted Diminished Radix Reduction}{section.6.4} -\BOOKMARK [1][-]{section.6.5}{Algorithm Comparison}{chapter.6} -\BOOKMARK [0][-]{chapter.7}{Exponentiation}{} -\BOOKMARK [1][-]{section.7.1}{Exponentiation Basics}{chapter.7} -\BOOKMARK [2][-]{subsection.7.1.1}{Single Digit Exponentiation}{section.7.1} -\BOOKMARK [1][-]{section.7.2}{k-ary Exponentiation}{chapter.7} -\BOOKMARK [2][-]{subsection.7.2.1}{Optimal Values of k}{section.7.2} -\BOOKMARK [2][-]{subsection.7.2.2}{Sliding-Window Exponentiation}{section.7.2} -\BOOKMARK [1][-]{section.7.3}{Modular Exponentiation}{chapter.7} -\BOOKMARK [2][-]{subsection.7.3.1}{Barrett Modular Exponentiation}{section.7.3} -\BOOKMARK [1][-]{section.7.4}{Quick Power of Two}{chapter.7} -\BOOKMARK [0][-]{chapter.8}{Higher Level Algorithms}{} -\BOOKMARK [1][-]{section.8.1}{Integer Division with Remainder}{chapter.8} -\BOOKMARK [2][-]{subsection.8.1.1}{Quotient Estimation}{section.8.1} -\BOOKMARK [2][-]{subsection.8.1.2}{Normalized Integers}{section.8.1} -\BOOKMARK [2][-]{subsection.8.1.3}{Radix- Division with Remainder}{section.8.1} -\BOOKMARK [1][-]{section.8.2}{Single Digit Helpers}{chapter.8} -\BOOKMARK [2][-]{subsection.8.2.1}{Single Digit Addition and Subtraction}{section.8.2} -\BOOKMARK [2][-]{subsection.8.2.2}{Single Digit Multiplication}{section.8.2} -\BOOKMARK [2][-]{subsection.8.2.3}{Single Digit Division}{section.8.2} -\BOOKMARK [2][-]{subsection.8.2.4}{Single Digit Root Extraction}{section.8.2} -\BOOKMARK [1][-]{section.8.3}{Random Number Generation}{chapter.8} -\BOOKMARK [1][-]{section.8.4}{Formatted Representations}{chapter.8} -\BOOKMARK [2][-]{subsection.8.4.1}{Reading Radix-n Input}{section.8.4} -\BOOKMARK [2][-]{subsection.8.4.2}{Generating Radix-n Output}{section.8.4} -\BOOKMARK [0][-]{chapter.9}{Number Theoretic Algorithms}{} -\BOOKMARK [1][-]{section.9.1}{Greatest Common Divisor}{chapter.9} -\BOOKMARK [2][-]{subsection.9.1.1}{Complete Greatest Common Divisor}{section.9.1} -\BOOKMARK [1][-]{section.9.2}{Least Common Multiple}{chapter.9} -\BOOKMARK [1][-]{section.9.3}{Jacobi Symbol Computation}{chapter.9} -\BOOKMARK [2][-]{subsection.9.3.1}{Jacobi Symbol}{section.9.3} -\BOOKMARK [1][-]{section.9.4}{Modular Inverse}{chapter.9} -\BOOKMARK [2][-]{subsection.9.4.1}{General Case}{section.9.4} -\BOOKMARK [1][-]{section.9.5}{Primality Tests}{chapter.9} -\BOOKMARK [2][-]{subsection.9.5.1}{Trial Division}{section.9.5} -\BOOKMARK [2][-]{subsection.9.5.2}{The Fermat Test}{section.9.5} -\BOOKMARK [2][-]{subsection.9.5.3}{The Miller-Rabin Test}{section.9.5} +\BOOKMARK [0][-]{chapter.1}{Introduction}{}% 1 +\BOOKMARK [1][-]{section.1.1}{Multiple Precision Arithmetic}{chapter.1}% 2 +\BOOKMARK [2][-]{subsection.1.1.1}{What is Multiple Precision Arithmetic?}{section.1.1}% 3 +\BOOKMARK [2][-]{subsection.1.1.2}{The Need for Multiple Precision Arithmetic}{section.1.1}% 4 +\BOOKMARK [2][-]{subsection.1.1.3}{Benefits of Multiple Precision Arithmetic}{section.1.1}% 5 +\BOOKMARK [1][-]{section.1.2}{Purpose of This Text}{chapter.1}% 6 +\BOOKMARK [1][-]{section.1.3}{Discussion and Notation}{chapter.1}% 7 +\BOOKMARK [2][-]{subsection.1.3.1}{Notation}{section.1.3}% 8 +\BOOKMARK [2][-]{subsection.1.3.2}{Precision Notation}{section.1.3}% 9 +\BOOKMARK [2][-]{subsection.1.3.3}{Algorithm Inputs and Outputs}{section.1.3}% 10 +\BOOKMARK [2][-]{subsection.1.3.4}{Mathematical Expressions}{section.1.3}% 11 +\BOOKMARK [2][-]{subsection.1.3.5}{Work Effort}{section.1.3}% 12 +\BOOKMARK [1][-]{section.1.4}{Exercises}{chapter.1}% 13 +\BOOKMARK [1][-]{section.1.5}{Introduction to LibTomMath}{chapter.1}% 14 +\BOOKMARK [2][-]{subsection.1.5.1}{What is LibTomMath?}{section.1.5}% 15 +\BOOKMARK [2][-]{subsection.1.5.2}{Goals of LibTomMath}{section.1.5}% 16 +\BOOKMARK [1][-]{section.1.6}{Choice of LibTomMath}{chapter.1}% 17 +\BOOKMARK [2][-]{subsection.1.6.1}{Code Base}{section.1.6}% 18 +\BOOKMARK [2][-]{subsection.1.6.2}{API Simplicity}{section.1.6}% 19 +\BOOKMARK [2][-]{subsection.1.6.3}{Optimizations}{section.1.6}% 20 +\BOOKMARK [2][-]{subsection.1.6.4}{Portability and Stability}{section.1.6}% 21 +\BOOKMARK [2][-]{subsection.1.6.5}{Choice}{section.1.6}% 22 +\BOOKMARK [0][-]{chapter.2}{Getting Started}{}% 23 +\BOOKMARK [1][-]{section.2.1}{Library Basics}{chapter.2}% 24 +\BOOKMARK [1][-]{section.2.2}{What is a Multiple Precision Integer?}{chapter.2}% 25 +\BOOKMARK [2][-]{subsection.2.2.1}{The mp\137int Structure}{section.2.2}% 26 +\BOOKMARK [1][-]{section.2.3}{Argument Passing}{chapter.2}% 27 +\BOOKMARK [1][-]{section.2.4}{Return Values}{chapter.2}% 28 +\BOOKMARK [1][-]{section.2.5}{Initialization and Clearing}{chapter.2}% 29 +\BOOKMARK [2][-]{subsection.2.5.1}{Initializing an mp\137int}{section.2.5}% 30 +\BOOKMARK [2][-]{subsection.2.5.2}{Clearing an mp\137int}{section.2.5}% 31 +\BOOKMARK [1][-]{section.2.6}{Maintenance Algorithms}{chapter.2}% 32 +\BOOKMARK [2][-]{subsection.2.6.1}{Augmenting an mp\137int's Precision}{section.2.6}% 33 +\BOOKMARK [2][-]{subsection.2.6.2}{Initializing Variable Precision mp\137ints}{section.2.6}% 34 +\BOOKMARK [2][-]{subsection.2.6.3}{Multiple Integer Initializations and Clearings}{section.2.6}% 35 +\BOOKMARK [2][-]{subsection.2.6.4}{Clamping Excess Digits}{section.2.6}% 36 +\BOOKMARK [0][-]{chapter.3}{Basic Operations}{}% 37 +\BOOKMARK [1][-]{section.3.1}{Introduction}{chapter.3}% 38 +\BOOKMARK [1][-]{section.3.2}{Assigning Values to mp\137int Structures}{chapter.3}% 39 +\BOOKMARK [2][-]{subsection.3.2.1}{Copying an mp\137int}{section.3.2}% 40 +\BOOKMARK [2][-]{subsection.3.2.2}{Creating a Clone}{section.3.2}% 41 +\BOOKMARK [1][-]{section.3.3}{Zeroing an Integer}{chapter.3}% 42 +\BOOKMARK [1][-]{section.3.4}{Sign Manipulation}{chapter.3}% 43 +\BOOKMARK [2][-]{subsection.3.4.1}{Absolute Value}{section.3.4}% 44 +\BOOKMARK [2][-]{subsection.3.4.2}{Integer Negation}{section.3.4}% 45 +\BOOKMARK [1][-]{section.3.5}{Small Constants}{chapter.3}% 46 +\BOOKMARK [2][-]{subsection.3.5.1}{Setting Small Constants}{section.3.5}% 47 +\BOOKMARK [2][-]{subsection.3.5.2}{Setting Large Constants}{section.3.5}% 48 +\BOOKMARK [1][-]{section.3.6}{Comparisons}{chapter.3}% 49 +\BOOKMARK [2][-]{subsection.3.6.1}{Unsigned Comparisions}{section.3.6}% 50 +\BOOKMARK [2][-]{subsection.3.6.2}{Signed Comparisons}{section.3.6}% 51 +\BOOKMARK [0][-]{chapter.4}{Basic Arithmetic}{}% 52 +\BOOKMARK [1][-]{section.4.1}{Introduction}{chapter.4}% 53 +\BOOKMARK [1][-]{section.4.2}{Addition and Subtraction}{chapter.4}% 54 +\BOOKMARK [2][-]{subsection.4.2.1}{Low Level Addition}{section.4.2}% 55 +\BOOKMARK [2][-]{subsection.4.2.2}{Low Level Subtraction}{section.4.2}% 56 +\BOOKMARK [2][-]{subsection.4.2.3}{High Level Addition}{section.4.2}% 57 +\BOOKMARK [2][-]{subsection.4.2.4}{High Level Subtraction}{section.4.2}% 58 +\BOOKMARK [1][-]{section.4.3}{Bit and Digit Shifting}{chapter.4}% 59 +\BOOKMARK [2][-]{subsection.4.3.1}{Multiplication by Two}{section.4.3}% 60 +\BOOKMARK [2][-]{subsection.4.3.2}{Division by Two}{section.4.3}% 61 +\BOOKMARK [1][-]{section.4.4}{Polynomial Basis Operations}{chapter.4}% 62 +\BOOKMARK [2][-]{subsection.4.4.1}{Multiplication by x}{section.4.4}% 63 +\BOOKMARK [2][-]{subsection.4.4.2}{Division by x}{section.4.4}% 64 +\BOOKMARK [1][-]{section.4.5}{Powers of Two}{chapter.4}% 65 +\BOOKMARK [2][-]{subsection.4.5.1}{Multiplication by Power of Two}{section.4.5}% 66 +\BOOKMARK [2][-]{subsection.4.5.2}{Division by Power of Two}{section.4.5}% 67 +\BOOKMARK [2][-]{subsection.4.5.3}{Remainder of Division by Power of Two}{section.4.5}% 68 +\BOOKMARK [0][-]{chapter.5}{Multiplication and Squaring}{}% 69 +\BOOKMARK [1][-]{section.5.1}{The Multipliers}{chapter.5}% 70 +\BOOKMARK [1][-]{section.5.2}{Multiplication}{chapter.5}% 71 +\BOOKMARK [2][-]{subsection.5.2.1}{The Baseline Multiplication}{section.5.2}% 72 +\BOOKMARK [2][-]{subsection.5.2.2}{Faster Multiplication by the ``Comba'' Method}{section.5.2}% 73 +\BOOKMARK [2][-]{subsection.5.2.3}{Polynomial Basis Multiplication}{section.5.2}% 74 +\BOOKMARK [2][-]{subsection.5.2.4}{Karatsuba Multiplication}{section.5.2}% 75 +\BOOKMARK [2][-]{subsection.5.2.5}{Toom-Cook 3-Way Multiplication}{section.5.2}% 76 +\BOOKMARK [2][-]{subsection.5.2.6}{Signed Multiplication}{section.5.2}% 77 +\BOOKMARK [1][-]{section.5.3}{Squaring}{chapter.5}% 78 +\BOOKMARK [2][-]{subsection.5.3.1}{The Baseline Squaring Algorithm}{section.5.3}% 79 +\BOOKMARK [2][-]{subsection.5.3.2}{Faster Squaring by the ``Comba'' Method}{section.5.3}% 80 +\BOOKMARK [2][-]{subsection.5.3.3}{Polynomial Basis Squaring}{section.5.3}% 81 +\BOOKMARK [2][-]{subsection.5.3.4}{Karatsuba Squaring}{section.5.3}% 82 +\BOOKMARK [2][-]{subsection.5.3.5}{Toom-Cook Squaring}{section.5.3}% 83 +\BOOKMARK [2][-]{subsection.5.3.6}{High Level Squaring}{section.5.3}% 84 +\BOOKMARK [0][-]{chapter.6}{Modular Reduction}{}% 85 +\BOOKMARK [1][-]{section.6.1}{Basics of Modular Reduction}{chapter.6}% 86 +\BOOKMARK [1][-]{section.6.2}{The Barrett Reduction}{chapter.6}% 87 +\BOOKMARK [2][-]{subsection.6.2.1}{Fixed Point Arithmetic}{section.6.2}% 88 +\BOOKMARK [2][-]{subsection.6.2.2}{Choosing a Radix Point}{section.6.2}% 89 +\BOOKMARK [2][-]{subsection.6.2.3}{Trimming the Quotient}{section.6.2}% 90 +\BOOKMARK [2][-]{subsection.6.2.4}{Trimming the Residue}{section.6.2}% 91 +\BOOKMARK [2][-]{subsection.6.2.5}{The Barrett Algorithm}{section.6.2}% 92 +\BOOKMARK [2][-]{subsection.6.2.6}{The Barrett Setup Algorithm}{section.6.2}% 93 +\BOOKMARK [1][-]{section.6.3}{The Montgomery Reduction}{chapter.6}% 94 +\BOOKMARK [2][-]{subsection.6.3.1}{Digit Based Montgomery Reduction}{section.6.3}% 95 +\BOOKMARK [2][-]{subsection.6.3.2}{Baseline Montgomery Reduction}{section.6.3}% 96 +\BOOKMARK [2][-]{subsection.6.3.3}{Faster ``Comba'' Montgomery Reduction}{section.6.3}% 97 +\BOOKMARK [2][-]{subsection.6.3.4}{Montgomery Setup}{section.6.3}% 98 +\BOOKMARK [1][-]{section.6.4}{The Diminished Radix Algorithm}{chapter.6}% 99 +\BOOKMARK [2][-]{subsection.6.4.1}{Choice of Moduli}{section.6.4}% 100 +\BOOKMARK [2][-]{subsection.6.4.2}{Choice of k}{section.6.4}% 101 +\BOOKMARK [2][-]{subsection.6.4.3}{Restricted Diminished Radix Reduction}{section.6.4}% 102 +\BOOKMARK [2][-]{subsection.6.4.4}{Unrestricted Diminished Radix Reduction}{section.6.4}% 103 +\BOOKMARK [1][-]{section.6.5}{Algorithm Comparison}{chapter.6}% 104 +\BOOKMARK [0][-]{chapter.7}{Exponentiation}{}% 105 +\BOOKMARK [1][-]{section.7.1}{Exponentiation Basics}{chapter.7}% 106 +\BOOKMARK [2][-]{subsection.7.1.1}{Single Digit Exponentiation}{section.7.1}% 107 +\BOOKMARK [1][-]{section.7.2}{k-ary Exponentiation}{chapter.7}% 108 +\BOOKMARK [2][-]{subsection.7.2.1}{Optimal Values of k}{section.7.2}% 109 +\BOOKMARK [2][-]{subsection.7.2.2}{Sliding-Window Exponentiation}{section.7.2}% 110 +\BOOKMARK [1][-]{section.7.3}{Modular Exponentiation}{chapter.7}% 111 +\BOOKMARK [2][-]{subsection.7.3.1}{Barrett Modular Exponentiation}{section.7.3}% 112 +\BOOKMARK [1][-]{section.7.4}{Quick Power of Two}{chapter.7}% 113 +\BOOKMARK [0][-]{chapter.8}{Higher Level Algorithms}{}% 114 +\BOOKMARK [1][-]{section.8.1}{Integer Division with Remainder}{chapter.8}% 115 +\BOOKMARK [2][-]{subsection.8.1.1}{Quotient Estimation}{section.8.1}% 116 +\BOOKMARK [2][-]{subsection.8.1.2}{Normalized Integers}{section.8.1}% 117 +\BOOKMARK [2][-]{subsection.8.1.3}{Radix- Division with Remainder}{section.8.1}% 118 +\BOOKMARK [1][-]{section.8.2}{Single Digit Helpers}{chapter.8}% 119 +\BOOKMARK [2][-]{subsection.8.2.1}{Single Digit Addition and Subtraction}{section.8.2}% 120 +\BOOKMARK [2][-]{subsection.8.2.2}{Single Digit Multiplication}{section.8.2}% 121 +\BOOKMARK [2][-]{subsection.8.2.3}{Single Digit Division}{section.8.2}% 122 +\BOOKMARK [2][-]{subsection.8.2.4}{Single Digit Root Extraction}{section.8.2}% 123 +\BOOKMARK [1][-]{section.8.3}{Random Number Generation}{chapter.8}% 124 +\BOOKMARK [1][-]{section.8.4}{Formatted Representations}{chapter.8}% 125 +\BOOKMARK [2][-]{subsection.8.4.1}{Reading Radix-n Input}{section.8.4}% 126 +\BOOKMARK [2][-]{subsection.8.4.2}{Generating Radix-n Output}{section.8.4}% 127 +\BOOKMARK [0][-]{chapter.9}{Number Theoretic Algorithms}{}% 128 +\BOOKMARK [1][-]{section.9.1}{Greatest Common Divisor}{chapter.9}% 129 +\BOOKMARK [2][-]{subsection.9.1.1}{Complete Greatest Common Divisor}{section.9.1}% 130 +\BOOKMARK [1][-]{section.9.2}{Least Common Multiple}{chapter.9}% 131 +\BOOKMARK [1][-]{section.9.3}{Jacobi Symbol Computation}{chapter.9}% 132 +\BOOKMARK [2][-]{subsection.9.3.1}{Jacobi Symbol}{section.9.3}% 133 +\BOOKMARK [1][-]{section.9.4}{Modular Inverse}{chapter.9}% 134 +\BOOKMARK [2][-]{subsection.9.4.1}{General Case}{section.9.4}% 135 +\BOOKMARK [1][-]{section.9.5}{Primality Tests}{chapter.9}% 136 +\BOOKMARK [2][-]{subsection.9.5.1}{Trial Division}{section.9.5}% 137 +\BOOKMARK [2][-]{subsection.9.5.2}{The Fermat Test}{section.9.5}% 138 +\BOOKMARK [2][-]{subsection.9.5.3}{The Miller-Rabin Test}{section.9.5}% 139 |