Fast Modular Exponentiation algorithm in Python.
By the way, in python at the command-line loop you can simply do
>>>pow(x,e,m)to get x^e % m evaluated. This also works with "long integers". Nevertheless, we might also want to see what this algorithm is :
We define a function f(x,e,m) whose return value is x^e % m def f(x,e,m): X = x E = e Y = 1 while E > 0: if E % 2 == 0: X = (X * X) % m E = E/2 else: Y = (X * Y) % m E = E - 1 return Y