def mod_exp(base, exponent, modulus):
    """
    Computes s = (base ^ exponent) mod modulus
    (Bruce Schneier: "Applied Cryptography" pp. 244)
    """
    s = 1
    while exponent != 0:
        if exponent & 1:
            s = (s * base) % modulus
        exponent >>= 1
        base = (base * base) % modulus
    return s