fast exponentiation in python
def fast_exp(b, e, m): # Calculate b^e mod m init = 2 powers = [b] # Calculate b powers until e while init <= e: powers.append((powers[-1]**2) % m) init *= 2 binary = bin(e)[2:][::-1] product = 1 # We can now multiply the correct powers for i in range(len(binary)): if binary[i] == '1': product *= powers[i] product %= m return product
