Raise a number to a huge power, modulo m

Repeated squaring: look at the exponent's bits from lowest to highest. Keep a running answer; whenever the current bit is 1, multiply it by the current square. Square that value and shift the exponent right each step. The loop runs once per bit of exp, so it is O(log exp) multiplications with O(1) extra space, and taking mod m each time keeps the numbers small.

Multiplying exp times would be O(exp): a billion steps.

The same idea speeds up matrix powers, which gives O(log n) Fibonacci numbers.

Python's pow(base, exp, mod) does this for you; in an interview, write it to show the idea.

def power_mod(base: int, exp: int, mod: int) -> int:
    acc, sq = 1 % mod, base % mod
    while exp:
        if exp & 1:  # this bit of the exponent is set
            acc = acc * sq % mod
        sq = sq * sq % mod
        exp >>= 1
    return acc

Common mistakes

• Forgetting the final % mod when exp is 0 and mod is 1 (the answer must be 0).
• Computing base ** exp first, which builds an enormous integer.

Walk through the bits of a small exponent such as 13 (binary 1101); it makes the loop obvious.

Follow-up questions

Think of your answer first, then open the hint.

1. How would you compute modular inverses?

   Show hint

   With a prime modulus, base^(m - 2) mod m by Fermat's little theorem.

2. Can this be done recursively?

   Show hint

   Yes: square the result of exp // 2 and multiply by base if exp is odd; stack depth is O(log exp).