def exponentiate(base, exp, p):
    """
    uses the square and multiply algorithm to 
    get (base^exp)%p

    :param base: base of the exponentiation
    :param exp: power that the base is being raised to
    :param p: prime modulus 

    :returns: (base^exp) mod p
    """
    e = "{0:b}".format(exp)  # bitstring of the exponent

    z = 1
    for c in e:
        z = z * z % p

        if int(c) == 1:
            z = z * base % p
    return z