Fast Modular Exponentiation algorithm in Python.

By the way, in python at the command-line loop you can simply do

>>>pow(x,e,m)   
answer
>>>

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