Fast Exponentiation

Math / Number Theory O(log exp) O(1)

Computes baseᵉˣᵖ mod m in O(log exp) by squaring the base and multiplying it in only where the exponent has a 1-bit.

13 = 1101₂

result = 1base = 3exp = 13

BaseExpMod

1/18

Compute 3^13 mod 100. Start with result = 1.

Invariantresult · base^exp is the answer throughout; each round halves the exponent.

current bitprocessed bit

fast-exponentiation.c

long long power(long long b, long long e, long long m) {
    long long result = 1;
    b %= m;
    while (e > 0) {
        if (e & 1)                /* low bit set? */
            result = result * b % m;
        b = b * b % m;            /* square */
        e >>= 1;                  /* shift right */
    }
    return result;
}

How Fast Exponentiation works

Square the base repeatedly (b, b², b⁴, …) and multiply into the result only where the exponent's binary digit is 1. 2⁶⁴-sized exponents take just 64 rounds.

When to use it

Modular powers in cryptography, fast matrix powers for linear recurrences, big exponents anywhere.