Fast Exponentiation

Fast exponentiation computes powers by repeatedly squaring instead of multiplying one copy at a time.

It reduces exponentiation from linear in the exponent to logarithmic in the exponent.

Core Idea

The exponent is processed through its binary representation. When the current bit is set, the result is multiplied by the current base. Each step squares the base and halves the exponent.

This works especially well with modular arithmetic.

Python Example

def power_mod(base, exponent, mod):
    result = 1
    base %= mod
 
    while exponent > 0:
        if exponent % 2 == 1:
            result = (result * base) % mod
        base = (base * base) % mod
        exponent //= 2
 
    return result

Python’s built-in pow(base, exponent, mod) performs modular exponentiation efficiently.

Common Confusions

Fast exponentiation is not only for very large bases. The key is a large exponent.

When a modulus is involved, applying % mod during the loop prevents numbers from becoming unnecessarily huge.

When To Use It

Use fast exponentiation for modular powers, repeated doubling-like transitions, cryptography-adjacent arithmetic, and recurrence acceleration patterns.