Modular Exponentiation

Computing a base raised to a large power modulo m in logarithmic time by repeated squaring.

The problem

Modular exponentiation computes (base^exp) mod m. Doing this by naive repeated multiplication takes O(exp) multiplications and produces enormous intermediate values. Fast exponentiation, or exponentiation by squaring, reduces this to O(log exp) modular multiplications, keeping every intermediate value below m^2.

Repeated squaring

Kronos motion — power balance

Write the exponent in binary. Squaring the base steps through powers base^1, base^2, base^4, and so on; multiplying in the current base whenever the corresponding exponent bit is set accumulates the answer. Reducing modulo m after every multiplication bounds the size of all values.

Implementation

python

def mod_pow(base, exp, m):
    result = 1
    base %= m
    while exp > 0:
        if exp & 1:
            result = (result * base) % m
        base = (base * base) % m
        exp >>= 1
    return result

Where it is essential

Public-key cryptography (RSA, Diffie-Hellman) rests entirely on fast modular exponentiation.
Primality tests such as Fermat and Miller-Rabin evaluate powers modulo a candidate.
Rolling hashes and the number-theoretic transform precompute powers of a base.
Computing modular inverses via Fermat's little theorem uses base^(m-2) mod m for prime m.

Related tools

When the modulus is not prime, modular inverses come from the extended Euclidean algorithm rather than Fermat. The same square-and-multiply idea generalizes to matrix exponentiation for linear recurrences.