Mathematical Algorithms

Mathematical algorithms supply the reusable machinery of number theory: fast exponentiation, modular arithmetic, gcd, primality, and combinatorics. They power hashing, cryptography (RSA, Diffie-Hellman), and countless competitive-programming problems.

Modular Arithmetic

All operations work modulo m with a few rules:

(a + b) mod m = ((a mod m) + (b mod m)) mod m
(a · b) mod m = ((a mod m) · (b mod m)) mod m
(a − b) mod m = ((a mod m) − (b mod m) + m) mod m

Modular inverses — the number a⁻¹ with a·a⁻¹ ≡ 1 (mod m) — exist iff gcd(a, m) = 1 and are computed with the extended Euclidean algorithm or Fermat’s little theorem when m is prime.

Fast Exponentiation

Computing aⁿ mod m in O(log n) by repeated squaring:

power(a, n, m):
  result = 1
  while n > 0:
    if n & 1: result = result * a % m
    a = a * a % m
    n >>= 1
  return result

This is the engine of RSA (modular exponentiation with huge exponents) and of modular inverses via a^(m−2) mod m when m is prime.

gcd and Euclid’s Algorithm

gcd(a, b):
  while b != 0:
    a, b = b, a % b
  return a

The extended version also returns coefficients x, y with a·x + b·y = gcd(a, b) — which is exactly how modular inverses are found. The worst case (consecutive Fibonacci numbers) runs in O(log n).

Primality and the Sieve

• Sieve of Eratosthenes — mark composites in O(n log log n); every prime below n falls out of the unmarked cells.
• Trial division — test divisors up to √n; fine for small n.
• Miller–Rabin — probabilistic test for large n, deterministic for practical ranges.

The sieve doubles as a way to precompute smallest-prime-factors (SPF), giving O(log n) factorization.

Combinatorics Under Modulus

Choosing k of n items, modulo a prime m, uses precomputed factorials and modular inverses:

nCk = fact[n] · inv(fact[k]) · inv(fact[n−k]) mod m

The binomial coefficients also emerge from Pascal’s triangle, which is itself a dynamic program — C(n,k) = C(n−1,k−1) + C(n−1,k).

Where You’ll Use It

• Hashing — string polynomial hashes rely on modular arithmetic and inverses.
• Cryptography — RSA/DH need fast exponentiation, gcd, and primality.
• Probability and counting — nCk/nPk under modulus in DP-heavy problems.
• Number-theoretic problems — divisors, GCD families, and CRT.

Practice Trajectory

1. Implement power, gcd, and extended Euclid by hand.
2. Build a sieve and a smallest-prime-factor array; factor a number in O(log n).
3. Implement modular inverse via both Fermat and extended Euclid.
4. Precompute factorials + inverses and answer nCk mod m queries.
5. Solve: modular-exponentiation, gcd, and combinatorics problem sets.

When It’s the Right Tool