Multiprecision Integer Arithmetic

• Introduction (1 chapter)

  Introduction to Multiprecision Integers

• Basic (2 chapters)

  Integer representation / Basic operations

• Intermediate (4 chapters)

  Fast multiplication / Fast division / Modular arithmetic / Integer GCD

• Advanced (6 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 (2 chapters)

1. Chapter 2 Multiprecision Integer Representation

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

2. Chapter 3 Basic Integer Operations

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

Intermediate (4 chapters)

1. Chapter 4 Fast Multiplication Algorithms

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

2. Chapter 5 Fast Division Algorithms

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

3. Chapter 6 Modular Arithmetic

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

4. Chapter 7 Integer GCD Algorithms

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

Advanced (6 chapters)

1. Chapter 8 Unbalanced Toom-Cook Multiplication

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

2. Chapter 9 NTT Implementation Comparison

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

3. Chapter 10 Primality Testing

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

4. Chapter 11 Integer Factorization

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

5. Chapter 12 Block Lanczos

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

6. Chapter 13 Number-Theoretic Functions

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