1def fast_exp(b, e, m): # Calculate b^e mod m
2 init = 2
3 powers = [b]
4 # Calculate b powers until e
5 while init <= e:
6 powers.append((powers[-1]**2) % m)
7 init *= 2
8 binary = bin(e)[2:][::-1]
9 product = 1
10 # We can now multiply the correct powers
11 for i in range(len(binary)):
12 if binary[i] == '1':
13 product *= powers[i]
14 product %= m
15 return product