def modExponentiate(a, b, n):
    ''' Computes a ^ b mod n '''
    assert b >= 0
    if b == 0:
        result = 1
    elif b == 1:
        result = a % n
    elif b % 2 == 0:
        k = modExponentiate(a, b / 2, n) 
        result = (k * k) % n
    else:
        k = modExponentiate(a, b / 2, n)
        result = (k * k * a) % n

    return result