Chapter 31: Number-Theoretic Algorithms: Modular Arithmetic, GCD, and RSA

Modular arithmetic is formalized through group theory: the additive group Zₙ is closed under addition mod n, while the multiplicative group Zₙ* consists of elements relatively prime to n, with Euler's phi function φ(n) counting their quantity, Lagrange's theorem constraining subgroup orders, and primitive roots generating the entire group through repeated exponentiation. Modular linear equations ax ≡ b (mod n) have exactly gcd(a,n) solutions when gcd(a,n) divides b, and the Chinese Remainder Theorem maps systems of congruences with pairwise coprime moduli to a unique solution mod N = n₁ × n₂ × ···, enabling component-wise modular computation. Euler's theorem establishes that a^φ(n) ≡ 1 (mod n) for gcd(a,n) = 1, with Fermat's little theorem as the prime special case, and modular exponentiation via repeated squaring computes aᵇ mod n in O(log b) multiplications — the computational backbone of RSA, which encrypts as C = Mᵉ mod n and decrypts as M = Cᵈ mod n using a public exponent e and private inverse d ≡ e⁻¹ mod φ(n), with security resting on the hardness of factoring n = pq. The chapter closes with primality testing: trial division is too slow for cryptographic primes, the pseudoprime test is fooled by Carmichael numbers, and the Miller-Rabin test provides a probabilistic solution where at least half of all bases witness compositeness for any composite n, reducing error probability to 2⁻ˢ after s independent iterations.