Multiprecision Integer Arithmetic

• Introduction (1 chapter)

  Introduction to Multiprecision Integers

• Basic (3 chapters)

  Integer representation / Basic operations

• Intermediate (4 chapters)

  Fast multiplication / Fast division / Modular arithmetic / Integer GCD

• Advanced (5 chapters)

  Unbalanced Toom-Cook / NTT comparison / Primality testing / Integer factorization / Block Lanczos / Number-theoretic functions

Introduction (1 chapter)

1. Chapter 1 Introduction to Multiprecision Integers

   The 64-bit wall, use cases for multiprecision integers, representation choices, memory management, overview of major libraries

Basic (3 chapters)

1. Chapter 2 Multiprecision Integer Representation

   Limb arrays, sign-magnitude vs two's complement, endianness, SBO, sangi design choices

2. Chapter 3 Basic Integer Operations

   Schoolbook add/subtract/multiply/divide, carry propagation, comparison, string conversion

3. Chapter 4 Integer GCD Algorithms

   Classical Euclid, Binary GCD (Stein), Lehmer, HGCD, Extended GCD, modular inverse

Intermediate (4 chapters)

1. Chapter 5 Fast Multiplication Algorithms

   Karatsuba, Toom-Cook 3/4/6/8, NTT, 5-smooth NTT, squaring optimization, threshold design

2. Chapter 6 Fast Division Algorithms

   Knuth's Algorithm D, Burnikel-Ziegler, Newton reciprocal iteration, Exact Division, sangi implementation

3. Chapter 7 Modular Arithmetic

   Barrett reduction, Montgomery multiplication, CRT, fast modular exponentiation, constant-time implementations

4. Chapter 8 Number-Theoretic Functions

   Möbius μ, Euler totient φ, divisor functions σ_k, Jacobi symbol, Dirichlet convolution, Möbius inversion

Advanced (5 chapters)

1. Chapter 9 Unbalanced Toom-Cook Multiplication

   Toom-4,2 / Toom-8, pre-pad + addmul_1, application to unbalanced invert_approx

2. Chapter 10 NTT Implementation Comparison

   Prime NTT, Small Prime NTT, Goldilocks NTT, Double FFT, 5-smooth NTT, AVX2 butterflies

3. Chapter 11 Primality Testing

   Miller-Rabin, Fermat, Baillie-PSW, APRCL, AKS, practical combined strategies

4. Chapter 12 Integer Factorization

   Trial division, Pollard rho/Brent, Pollard p-1, Fermat, ECM, SIQS, GNFS

5. Chapter 13 Block Lanczos

   GF(2) sparse matrix solver, Coppersmith blocking, CSR format, final stage of GNFS

• How Computers Multiply Thousand-Digit Numbers

  Reading How a machine with only a small box cuts numbers into chunks, speeds up multiplication by divide and conquer, and ends up hunting gigantic primes. A relaxed look at climbing the wall of digits.