Multiprecision Integers — Intermediate

Contents (Chapters 4–7)

Note: Chapters 1–3 are in the Basic section.

  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

Last updated: 2026-04-20