Modular Exponentiation

Problem

Compute base raised to exp modulo mod using fast modular exponentiation in O(log exp) multiplications.

Reduce base modulo mod first, square the base each round while halving the exponent, and multiply into the result whenever the current bit is set. Assume mod >= 1 and exp >= 0, and return 0 when mod is 1.

Hint

Keep every intermediate product reduced modulo mod to avoid huge numbers.

Test cases

case 1

in: [2,10,1000]

expected: 24

case 2

in: [3,0,7]

expected: 1

case 3

in: [5,3,13]

expected: 8

case 4

in: [10,100,7]

expected: 4

case 5

in: [0,0,1]

expected: 0

Starter codePython

def mod_pow(base, exp, mod):
    # Your code here
    pass

5 test cases · run your code against them in the editor