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