Fast Modular Exponentiation

Binary exponentiation computes a^e mod m in O(log e) by squaring the base and multiplying into the answer when the current bit of e is 1.

Why this shows up in the real world

Cryptography, competitive programming, and combinatorics lean on primes, residues mod n, and fast arithmetic on huge integers.

Core idea (explained for students)

Invariant: res holds product of selected powers. Always reduce mod m after multiply to avoid overflow. Same idea powers matrices or combines with CRT for huge exponents.

Try this in Python

def mod_pow(base: int, exp: int, mod: int) -> int:
    res = 1
    base %= mod
    while exp:
        if exp & 1:
            res = res * base % mod
        base = base * base % mod
        exp >>= 1
    return res


print(mod_pow(2, 1000000000, 1000000007))

Common mistakes

• Linear loop over exponent (TLE for e≈10⁹).
• Forgetting % mod on intermediate products.
• Using Fermat inverse when mod is not prime.

Key takeaways

• Template mod_pow should be muscle memory.
• For (a^e) % m with composite m, use Euler theorem or CRT split.