Number-Theoretic Algorithms

What you'll learn

A handful of number-theoretic algorithms underpin cryptography and competitive programming. They're short, fast, and beautiful: the GCD, modular exponentiation, the sieve of primes, and primality testing.

By the end you'll be able to:

• Compute the GCD — and solve ax + by = gcd
• Work in modular arithmetic, including inverses
• Generate primes with the sieve and test primality

Euclid's GCD

The oldest algorithm still in use: the greatest common divisor of a and b equals the GCD of b and a mod b — repeat until the remainder is 0. It's O(log min(a, b)). The extended version also finds integers x, y with ax + by = gcd(a, b) — the key to modular inverses:

def gcd(a, b):
    while b:
        a, b = b, a % b       # replace (a, b) with (b, a mod b)
    return a

# extended: also find x, y with a*x + b*y = gcd(a, b)
def ext_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = ext_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

Modular arithmetic

Arithmetic that wraps around a modulus m is everywhere in cryptography and hashing. Addition and multiplication distribute over mod, so you can reduce at every step to keep numbers small. Two staples:

• Modular exponentiation — xⁿ mod m by fast exponentiation (Module 12), reducing mod m after each multiply: O(log n) and overflow-free.
• Modular inverse — the number x⁻¹ with x·x⁻¹ ≡ 1 (mod m). Find it with extended Euclid, or with Fermat's little theorem (x^{m-2} mod m) when m is prime.

The sieve of Eratosthenes

To find every prime up to n, start with all numbers "prime," then repeatedly take the next prime and cross off its multiples. Starting each at i² (smaller multiples are already crossed) makes it O(n log log n) — nearly linear:

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    i = 2
    while i * i <= n:
        if is_prime[i]:
            for j in range(i * i, n + 1, i):   # mark multiples of i
                is_prime[j] = False
        i += 1
    return [x for x in range(2, n + 1) if is_prime[x]]

Primality & cryptography

Testing one large number for primality by trial division up to √n is O(√n) — too slow for cryptographic sizes. Miller-Rabin is a fast probabilistic test: a few random witnesses declare a number prime with overwhelming confidence in O(k log³ n). These tests generate the large primes behind RSA, whose security rests on how hard factoring their product is.

Recap & quick check

Sometimes the fastest correct algorithm is a random one. Next up: Module 33 — Randomized Algorithms.