''' CS1800
    Fall 2019 - London
    RSA Encryption -- Helper Functions
'''

def modexp(x, e, m):
    ''' Function: modexp
        Parameters: x, e, and m -- all integers
        Returns: x ^ e (mod m) -- also an int
    '''
    y = 1
    while e > 0:
        if e % 2 == 0:
            x = (x * x) % m
            e = e / 2
        else:
            y = (x * y) % m
            e = e - 1
    return y

def gcd(a, b):
    ''' Function: gcd
        Parameters: two integers a, b with b != 0
        Returns: an int, the greatest common divisor of a and b
    '''
    if a == 0:
        return b
    return gcd(b % a, a)

def totient(n):
    ''' Function: totient
        Parameter: an integer, n
        Returns: phi of n, the number of pos-ints that are co-prime to n
    '''
    result = 1
    for i in range(2, n): 
        if gcd(i, n) == 1: 
            result += 1
    return result