Edit
kc3-lang/libtommath/tommath.pdf
Tom St Denis
- tommath.pdf
-
%PDF-1.4 5 0 obj << /S /GoTo /D (chapter.1) >> endobj 8 0 obj (Introduction) endobj 9 0 obj << /S /GoTo /D (section.1.1) >> endobj 12 0 obj (Multiple Precision Arithmetic) endobj 13 0 obj << /S /GoTo /D (subsection.1.1.1) >> endobj 16 0 obj (The Need for Multiple Precision Arithmetic) endobj 17 0 obj << /S /GoTo /D (subsection.1.1.2) >> endobj 20 0 obj (What is Multiple Precision Arithmetic?) endobj 21 0 obj << /S /GoTo /D (subsection.1.1.3) >> endobj 24 0 obj (Benefits of Multiple Precision Arithmetic) endobj 25 0 obj << /S /GoTo /D (section.1.2) >> endobj 28 0 obj (Purpose of This Text) endobj 29 0 obj << /S /GoTo /D (section.1.3) >> endobj 32 0 obj (Discussion and Notation) endobj 33 0 obj << /S /GoTo /D (subsection.1.3.1) >> endobj 36 0 obj (Notation) endobj 37 0 obj << /S /GoTo /D (subsection.1.3.2) >> endobj 40 0 obj (Precision Notation) endobj 41 0 obj << /S /GoTo /D (subsection.1.3.3) >> endobj 44 0 obj (Algorithm Inputs and Outputs) endobj 45 0 obj << /S /GoTo /D (subsection.1.3.4) >> endobj 48 0 obj (Mathematical Expressions) endobj 49 0 obj << /S /GoTo /D (subsection.1.3.5) >> endobj 52 0 obj (Work Effort) endobj 53 0 obj << /S /GoTo /D (section.1.4) >> endobj 56 0 obj (Exercises) endobj 57 0 obj << /S /GoTo /D (chapter.2) >> endobj 60 0 obj (Introduction to LibTomMath) endobj 61 0 obj << /S /GoTo /D (section.2.1) >> endobj 64 0 obj (What is LibTomMath?) endobj 65 0 obj << /S /GoTo /D (section.2.2) >> endobj 68 0 obj (Goals of LibTomMath) endobj 69 0 obj << /S /GoTo /D (section.2.3) >> endobj 72 0 obj (Choice of LibTomMath) endobj 73 0 obj << /S /GoTo /D (subsection.2.3.1) >> endobj 76 0 obj (Code Base) endobj 77 0 obj << /S /GoTo /D (subsection.2.3.2) >> endobj 80 0 obj (API Simplicity) endobj 81 0 obj << /S /GoTo /D (subsection.2.3.3) >> endobj 84 0 obj (Optimizations) endobj 85 0 obj << /S /GoTo /D (subsection.2.3.4) >> endobj 88 0 obj (Portability and Stability) endobj 89 0 obj << /S /GoTo /D (subsection.2.3.5) >> endobj 92 0 obj (Choice) endobj 93 0 obj << /S /GoTo /D (chapter.3) >> endobj 96 0 obj (Getting Started) endobj 97 0 obj << /S /GoTo /D (section.3.1) >> endobj 100 0 obj (Library Basics) endobj 101 0 obj << /S /GoTo /D (section.3.2) >> endobj 104 0 obj (What is a Multiple Precision Integer?) endobj 105 0 obj << /S /GoTo /D (subsection.3.2.1) >> endobj 108 0 obj (The mp\137int Structure) endobj 109 0 obj << /S /GoTo /D (section.3.3) >> endobj 112 0 obj (Argument Passing) endobj 113 0 obj << /S /GoTo /D (section.3.4) >> endobj 116 0 obj (Return Values) endobj 117 0 obj << /S /GoTo /D (section.3.5) >> endobj 120 0 obj (Initialization and Clearing) endobj 121 0 obj << /S /GoTo /D (subsection.3.5.1) >> endobj 124 0 obj (Initializing an mp\137int) endobj 125 0 obj << /S /GoTo /D (subsection.3.5.2) >> endobj 128 0 obj (Clearing an mp\137int) endobj 129 0 obj << /S /GoTo /D (section.3.6) >> endobj 132 0 obj (Maintenance Algorithms) endobj 133 0 obj << /S /GoTo /D (subsection.3.6.1) >> endobj 136 0 obj (Augmenting an mp\137int's Precision) endobj 137 0 obj << /S /GoTo /D (subsection.3.6.2) >> endobj 140 0 obj (Initializing Variable Precision mp\137ints) endobj 141 0 obj << /S /GoTo /D (subsection.3.6.3) >> endobj 144 0 obj (Multiple Integer Initializations and Clearings) endobj 145 0 obj << /S /GoTo /D (subsection.3.6.4) >> endobj 148 0 obj (Clamping Excess Digits) endobj 149 0 obj << /S /GoTo /D (chapter.4) >> endobj 152 0 obj (Basic Operations) endobj 153 0 obj << /S /GoTo /D (section.4.1) >> endobj 156 0 obj (Introduction) endobj 157 0 obj << /S /GoTo /D (section.4.2) >> endobj 160 0 obj (Assigning Values to mp\137int Structures) endobj 161 0 obj << /S /GoTo /D (subsection.4.2.1) >> endobj 164 0 obj (Copying an mp\137int) endobj 165 0 obj << /S /GoTo /D (subsection.4.2.2) >> endobj 168 0 obj (Creating a Clone) endobj 169 0 obj << /S /GoTo /D (section.4.3) >> endobj 172 0 obj (Zeroing an Integer) endobj 173 0 obj << /S /GoTo /D (section.4.4) >> endobj 176 0 obj (Sign Manipulation) endobj 177 0 obj << /S /GoTo /D (subsection.4.4.1) >> endobj 180 0 obj (Absolute Value) endobj 181 0 obj << /S /GoTo /D (subsection.4.4.2) >> endobj 184 0 obj (Integer Negation) endobj 185 0 obj << /S /GoTo /D (section.4.5) >> endobj 188 0 obj (Small Constants) endobj 189 0 obj << /S /GoTo /D (subsection.4.5.1) >> endobj 192 0 obj (Setting Small Constants) endobj 193 0 obj << /S /GoTo /D (subsection.4.5.2) >> endobj 196 0 obj (Setting Large Constants) endobj 197 0 obj << /S /GoTo /D (section.4.6) >> endobj 200 0 obj (Comparisons) endobj 201 0 obj << /S /GoTo /D (subsection.4.6.1) >> endobj 204 0 obj (Unsigned Comparisions) endobj 205 0 obj << /S /GoTo /D (subsection.4.6.2) >> endobj 208 0 obj (Signed Comparisons) endobj 209 0 obj << /S /GoTo /D (chapter.5) >> endobj 212 0 obj (Basic Arithmetic) endobj 213 0 obj << /S /GoTo /D (section.5.1) >> endobj 216 0 obj (Introduction) endobj 217 0 obj << /S /GoTo /D (section.5.2) >> endobj 220 0 obj (Addition and Subtraction) endobj 221 0 obj << /S /GoTo /D (subsection.5.2.1) >> endobj 224 0 obj (Low Level Addition) endobj 225 0 obj << /S /GoTo /D (subsection.5.2.2) >> endobj 228 0 obj (Low Level Subtraction) endobj 229 0 obj << /S /GoTo /D (subsection.5.2.3) >> endobj 232 0 obj (High Level Addition) endobj 233 0 obj << /S /GoTo /D (subsection.5.2.4) >> endobj 236 0 obj (High Level Subtraction) endobj 237 0 obj << /S /GoTo /D (section.5.3) >> endobj 240 0 obj (Bit and Digit Shifting) endobj 241 0 obj << /S /GoTo /D (subsection.5.3.1) >> endobj 244 0 obj (Multiplication by Two) endobj 245 0 obj << /S /GoTo /D (subsection.5.3.2) >> endobj 248 0 obj (Division by Two) endobj 249 0 obj << /S /GoTo /D (section.5.4) >> endobj 252 0 obj (Polynomial Basis Operations) endobj 253 0 obj << /S /GoTo /D (subsection.5.4.1) >> endobj 256 0 obj (Multiplication by x) endobj 257 0 obj << /S /GoTo /D (subsection.5.4.2) >> endobj 260 0 obj (Division by x) endobj 261 0 obj << /S /GoTo /D (section.5.5) >> endobj 264 0 obj (Powers of Two) endobj 265 0 obj << /S /GoTo /D (subsection.5.5.1) >> endobj 268 0 obj (Multiplication by Power of Two) endobj 269 0 obj << /S /GoTo /D (subsection.5.5.2) >> endobj 272 0 obj (Division by Power of Two) endobj 273 0 obj << /S /GoTo /D (subsection.5.5.3) >> endobj 276 0 obj (Remainder of Division by Power of Two) endobj 277 0 obj << /S /GoTo /D (chapter.6) >> endobj 280 0 obj (Multiplication and Squaring) endobj 281 0 obj << /S /GoTo /D (section.6.1) >> endobj 284 0 obj (The Multipliers) endobj 285 0 obj << /S /GoTo /D (section.6.2) >> endobj 288 0 obj (Multiplication) endobj 289 0 obj << /S /GoTo /D (subsection.6.2.1) >> endobj 292 0 obj (The Baseline Multiplication) endobj 293 0 obj << /S /GoTo /D (subsection.6.2.2) >> endobj 296 0 obj (Faster Multiplication by the ``Comba'' Method) endobj 297 0 obj << /S /GoTo /D (subsection.6.2.3) >> endobj 300 0 obj (Polynomial Basis Multiplication) endobj 301 0 obj << /S /GoTo /D (subsection.6.2.4) >> endobj 304 0 obj (Karatsuba Multiplication) endobj 305 0 obj << /S /GoTo /D (subsection.6.2.5) >> endobj 308 0 obj (Toom-Cook 3-Way Multiplication) endobj 309 0 obj << /S /GoTo /D (subsection.6.2.6) >> endobj 312 0 obj (Signed Multiplication) endobj 313 0 obj << /S /GoTo /D (section.6.3) >> endobj 316 0 obj (Squaring) endobj 317 0 obj << /S /GoTo /D (subsection.6.3.1) >> endobj 320 0 obj (The Baseline Squaring Algorithm) endobj 321 0 obj << /S /GoTo /D (subsection.6.3.2) >> endobj 324 0 obj (Faster Squaring by the ``Comba'' Method) endobj 325 0 obj << /S /GoTo /D (subsection.6.3.3) >> endobj 328 0 obj (Polynomial Basis Squaring) endobj 329 0 obj << /S /GoTo /D (subsection.6.3.4) >> endobj 332 0 obj (Karatsuba Squaring) endobj 333 0 obj << /S /GoTo /D (subsection.6.3.5) >> endobj 336 0 obj (Toom-Cook Squaring) endobj 337 0 obj << /S /GoTo /D (subsection.6.3.6) >> endobj 340 0 obj (High Level Squaring) endobj 341 0 obj << /S /GoTo /D (chapter.7) >> endobj 344 0 obj (Modular Reduction) endobj 345 0 obj << /S /GoTo /D (section.7.1) >> endobj 348 0 obj (Basics of Modular Reduction) endobj 349 0 obj << /S /GoTo /D (section.7.2) >> endobj 352 0 obj (The Barrett Reduction) endobj 353 0 obj << /S /GoTo /D (subsection.7.2.1) >> endobj 356 0 obj (Fixed Point Arithmetic) endobj 357 0 obj << /S /GoTo /D (subsection.7.2.2) >> endobj 360 0 obj (Choosing a Radix Point) endobj 361 0 obj << /S /GoTo /D (subsection.7.2.3) >> endobj 364 0 obj (Trimming the Quotient) endobj 365 0 obj << /S /GoTo /D (subsection.7.2.4) >> endobj 368 0 obj (Trimming the Residue) endobj 369 0 obj << /S /GoTo /D (subsection.7.2.5) >> endobj 372 0 obj (The Barrett Algorithm) endobj 373 0 obj << /S /GoTo /D (subsection.7.2.6) >> endobj 376 0 obj (The Barrett Setup Algorithm) endobj 377 0 obj << /S /GoTo /D (section.7.3) >> endobj 380 0 obj (The Montgomery Reduction) endobj 381 0 obj << /S /GoTo /D (subsection.7.3.1) >> endobj 384 0 obj (Digit Based Montgomery Reduction) endobj 385 0 obj << /S /GoTo /D (subsection.7.3.2) >> endobj 388 0 obj (Baseline Montgomery Reduction) endobj 389 0 obj << /S /GoTo /D (subsection.7.3.3) >> endobj 392 0 obj (Faster ``Comba'' Montgomery Reduction) endobj 393 0 obj << /S /GoTo /D (subsection.7.3.4) >> endobj 396 0 obj (Montgomery Setup) endobj 397 0 obj << /S /GoTo /D (section.7.4) >> endobj 400 0 obj (The Diminished Radix Algorithm) endobj 401 0 obj << /S /GoTo /D (subsection.7.4.1) >> endobj 404 0 obj (Choice of Moduli) endobj 405 0 obj << /S /GoTo /D (subsection.7.4.2) >> endobj 408 0 obj (Choice of k) endobj 409 0 obj << /S /GoTo /D (subsection.7.4.3) >> endobj 412 0 obj (Restricted Diminished Radix Reduction) endobj 413 0 obj << /S /GoTo /D (subsection.7.4.4) >> endobj 416 0 obj (Unrestricted Diminished Radix Reduction) endobj 417 0 obj << /S /GoTo /D (section.7.5) >> endobj 420 0 obj (Algorithm Comparison) endobj 421 0 obj << /S /GoTo /D (chapter.8) >> endobj 424 0 obj (Exponentiation) endobj 425 0 obj << /S /GoTo /D (section.8.1) >> endobj 428 0 obj (Exponentiation Basics) endobj 429 0 obj << /S /GoTo /D (subsection.8.1.1) >> endobj 432 0 obj (Single Digit Exponentiation) endobj 433 0 obj << /S /GoTo /D (section.8.2) >> endobj 436 0 obj (k-ary Exponentiation) endobj 437 0 obj << /S /GoTo /D (subsection.8.2.1) >> endobj 440 0 obj (Optimal Values of k) endobj 441 0 obj << /S /GoTo /D (subsection.8.2.2) >> endobj 444 0 obj (Sliding-Window Exponentiation) endobj 445 0 obj << /S /GoTo /D (section.8.3) >> endobj 448 0 obj (Modular Exponentiation) endobj 449 0 obj << /S /GoTo /D (subsection.8.3.1) >> endobj 452 0 obj (Barrett Modular Exponentiation) endobj 453 0 obj << /S /GoTo /D (section.8.4) >> endobj 456 0 obj (Quick Power of Two) endobj 457 0 obj << /S /GoTo /D (chapter.9) >> endobj 460 0 obj (Higher Level Algorithms) endobj 461 0 obj << /S /GoTo /D (section.9.1) >> endobj 464 0 obj (Integer Division with Remainder) endobj 465 0 obj << /S /GoTo /D (subsection.9.1.1) >> endobj 468 0 obj (Quotient Estimation) endobj 469 0 obj << /S /GoTo /D (subsection.9.1.2) >> endobj 472 0 obj (Normalized Integers) endobj 473 0 obj << /S /GoTo /D (subsection.9.1.3) >> endobj 476 0 obj (Radix- Division with Remainder) endobj 477 0 obj << /S /GoTo /D (section.9.2) >> endobj 480 0 obj (Single Digit Helpers) endobj 481 0 obj << /S /GoTo /D (subsection.9.2.1) >> endobj 484 0 obj (Single Digit Addition and Subtraction) endobj 485 0 obj << /S /GoTo /D (subsection.9.2.2) >> endobj 488 0 obj (Single Digit Multiplication) endobj 489 0 obj << /S /GoTo /D (subsection.9.2.3) >> endobj 492 0 obj (Single Digit Division) endobj 493 0 obj << /S /GoTo /D (subsection.9.2.4) >> endobj 496 0 obj (Single Digit Root Extraction) endobj 497 0 obj << /S /GoTo /D (section.9.3) >> endobj 500 0 obj (Random Number Generation) endobj 501 0 obj << /S /GoTo /D (section.9.4) >> endobj 504 0 obj (Formatted Representations) endobj 505 0 obj << /S /GoTo /D (subsection.9.4.1) >> endobj 508 0 obj (Reading Radix-n Input) endobj 509 0 obj << /S /GoTo /D (subsection.9.4.2) >> endobj 512 0 obj (Generating Radix-n Output) endobj 513 0 obj << /S /GoTo /D (chapter.10) >> endobj 516 0 obj (Number Theoretic Algorithms) endobj 517 0 obj << /S /GoTo /D (section.10.1) >> endobj 520 0 obj (Greatest Common Divisor) endobj 521 0 obj << /S /GoTo /D (subsection.10.1.1) >> endobj 524 0 obj (Complete Greatest Common Divisor) endobj 525 0 obj << /S /GoTo /D (section.10.2) >> endobj 528 0 obj (Least Common Multiple) endobj 529 0 obj << /S /GoTo /D (section.10.3) >> endobj 532 0 obj (Jacobi Symbol Computation) endobj 533 0 obj << /S /GoTo /D (subsection.10.3.1) >> endobj 536 0 obj (Jacobi Symbol) endobj 537 0 obj << /S /GoTo /D (section.10.4) >> endobj 540 0 obj (Modular Inverse) endobj 541 0 obj << /S /GoTo /D (subsection.10.4.1) >> endobj 544 0 obj (General Case) endobj 545 0 obj << /S /GoTo /D (section.10.5) >> endobj 548 0 obj (Primality Tests) endobj 549 0 obj << /S /GoTo /D (subsection.10.5.1) >> endobj 552 0 obj (Trial Division) endobj 553 0 obj << /S /GoTo /D (subsection.10.5.2) >> endobj 556 0 obj (The Fermat Test) endobj 557 0 obj << /S /GoTo /D (subsection.10.5.3) >> endobj 560 0 obj (The Miller-Rabin Test) endobj 561 0 obj << /S /GoTo /D [562 0 R /Fit ] >> endobj 564 0 obj << /Length 443 /Filter /FlateDecode >> stream xڍR