Aritmética modular

a ≡ b (mod n) significa que n divide a − b: os dois deixam o mesmo resto. É a aritmética do relógio e dos inteiros de tamanho fixo. Um uint32 faz toda a aritmética mod 2³².

(a + b) mod n = ((a mod n) + (b mod n)) mod n
(a · b) mod n = ((a mod n) · (b mod n)) mod n

Essas propriedades permitem reduzir a cada passo e manter os números pequenos. É assim que hashes polinomiais (Rabin–Karp) e geradores congruenciais funcionam.

Exponenciação rápida

Calcular aᵉ mod n multiplicando e vezes é inviável para expoentes de 2048 bits. Elevando ao quadrado repetidamente, bastam O(log e) multiplicações:

def pow_mod(a, e, n):
    r = 1
    a %= n
    while e:
        if e & 1:
            r = r * a % n
        a = a * a % n
        e >>= 1
    return r

assert pow_mod(3, 200, 1_000_007) == pow(3, 200, 1_000_007)