"""

 a_to_the_b_mod_c.py

 A tricky way to get large powers.

 Some of this is taken from e.g.
 en.wikipedia.org/wiki/Exponentiation_by_squaring
 blog.madpython.com/2010/08/07/algorithms-in-python-binary-exponentiation

"""

def power_mod(a, b, c):
    return abc_steps(a,b,c)[0]

def abc_steps(a, b, c, verbose=False):
    """ Return a**b % c for big a,b,c in O(log(b)) 
        >>> abc_steps(2, 4, 10)                   # 2**4 mod 10
        (6, 11)
        >>> abc_steps(123, 45, 1001)              # 123 ** 45 mod 1001
        (967, 23)
        >>> abc_steps(123456789, 314159, 100001)
        (82520, 69)
    """
    steps = 1
    result = 1
    base = a
    b = int(b)
    while b != 0:
        if verbose:
            print "result=%i, base=%i, b=%i " % (result, base, b)
        if b % 2 == 1:
            result = result * base % c
            steps += 1       # result *=
        base = base**2 % c
        b = b/2
        steps += 3           # if, base, b
    return (result, steps)

if __name__ == '__main__':
    import doctest
    doctest.testmod()