O(log n). Doubling the represented exponent through squaring halves the remaining exponent each step.

Write the exponent as selected powers of two. Repeated squaring prepares base¹, base², base⁴, and so on; set bits choose which ones enter the answer.

What the function promises: Return base^exponent modulo positive modulus for a nonnegative integer exponent.

def modular_power(base, exponent, modulus):
    if exponent < 0 or modulus <= 0: raise ValueError("Invalid input")
    answer = 1 % modulus
    base %= modulus
    while exponent:
        if exponent & 1: answer = answer * base % modulus
        base = base * base % modulus
        exponent >>= 1
    return answer

assert modular_power(3,13,100) == 23
assert modular_power(10,0,1) == 0

Work and storage: O(log exponent) modular multiplications and O(1) stored integers.

When to recognize it: Doubling the represented exponent through squaring halves the remaining exponent each step.

Check before applying it: Modular division needs an inverse and cannot be replaced by ordinary integer division.

Require an invertible base modulo m, compute its modular inverse, then exponentiate that inverse.