#!/usr/bin/env python3

# TODO:
# Second implementation.
# This one works by thinking of y as a binary number
# Here's how it works when trying to calculate 5^117 mod 19:

# 1) Write the exponent (y) as a binary number:
#    117 = (1110101) = 2^0 + 2^2 + 2^4 + 2^5 + 2^6 

# 2) Calculate 5^y mod C where y is a power of two <= B:
#    5^1  mod 19 = 5
#    5^2  mod 19 = 5 * 5   mod 19 = 25  mod 19 = 6
#    2^4  mod 19 = 6 * 6   mod 19 = 36  mod 19 = 17
#    2^8  mod 19 = 17 * 17 mod 19 = 289 mod 19 = 4
#    2^16 mod 19 = 4 * 4   mod 19 = 16  mod 19 = 16
#    2^32 mod 19 = 16 * 16 mod 19 = 256 mod 19 = 9
#    2^64 mod 19 = 9 * 9   mod 19 = 81  mod 19 = 5

# 3) Use modular multiplication properties to combine the calculated mod C values
#    5^117 mod 19 = (5^1 * 5^4 * 5^16 * 5^32 * 5^64) mod 19
#                 = ((5^1 mod 19) * (5^4 mod 19) * (5^16 mod 19) * (5^32 mod 19) * (5^64) mod 19) mod 19
#                 = (5 * 17 * 16 * 9 * 5) mod 19
#                 = 61200 mod 19
#                 = 1

# -------------------------------------------

def fast_exp(x, y, p):
    """
     Computes x^y mod p using the following properties:
     1) x^y = x^(y/2) * x^(y/2)     if y is even
     2) x^y = x^(y/2) * x^(y/2) * x if y is odd
     3) x*y mod C = ((x mod C) * (y mod C)) mod C

     Complexity: O(n^3) where n = max {number of bits of x, number of bits of y, p}

    :param x: integer, base
    :param y: integer, exponent
    :param p: integer, modulo
    :return: x^y mod p
    """

    if y == 0:
        return 1

    r = fast_exp(x, int(y/2), p)

    if y % 2 == 0:
        return r*r % p
    else:
        return r*r*x % p

if __name__ == "__main__":
    n1 = fast_exp(2, 6, 5)
    n2 = fast_exp(3, 10, 15)