Modular Exponentiation

Medium · rating 1300 · math, number-theory

Read three integers a, b, m. Print ab mod m.

Constraints: 0 ≤ a, b ≤ 109, 1 ≤ m ≤ 109

Editorial

Modular Exponentiation computes aᵇ mod m efficiently — a core operation in cryptography (RSA, Diffie–Hellman) and a frequent interview question. Computing aᵇ directly overflows and is far too slow for large exponents.

Fast (binary) exponentiation

Square the base repeatedly and multiply it into the result whenever the current bit of the exponent is 1, reducing mod m at every step to keep the numbers small.

result = 1
a %= m
while b > 0:
    if b & 1:
        result = result * a % m
    a = a * a % m
    b >>= 1
return result

Complexity

Time: O(log b). Space: O(1).

Open Modular Exponentiation in Code Arena →