Modular Exponentiation .sagews

23.digits(2)
list(reversed(23.digits(2)))

[1, 1, 1, 0, 1] [1, 0, 1, 1, 1]

def ModExp(b,n,m):
    """
    This function returns b^n mod m with the built in Digits Command.
    Note - Digits returns a list of the form [a_0 a_1 ... a_k]
    """
    e = n.digits(2);
    l = len(e)-1;
    x = 1;
    power = mod(b,m)
    for i in [0..l]:
        #print 'i =',i, 'x =', x, 'pow =', power #Print Out of Values i,x, and power
        if e[i] == 1: x = mod(x*power,m)
        power = mod(power^2,m)
    return x

ModExp(3,23,25)

i = 0 x = 1 pow = 3 i = 1 x = 3 pow = 9 i = 2 x = 2 pow = 6 i = 3 x = 12 pow = 11 i = 4 x = 12 pow = 21 2

mod(3^23,25)

2

ModExp(3,98,25)

i = 0 x = 1 pow = 3 i = 1 x = 1 pow = 9 i = 2 x = 9 pow = 6 i = 3 x = 9 pow = 11 i = 4 x = 9 pow = 21 i = 5 x = 9 pow = 16 i = 6 x = 19 pow = 6 14

ModExp(3,613,25)

i = 0 x = 1 pow = 3 i = 1 x = 3 pow = 9 i = 2 x = 3 pow = 6 i = 3 x = 18 pow = 11 i = 4 x = 18 pow = 21 i = 5 x = 18 pow = 16 i = 6 x = 13 pow = 6 i = 7 x = 3 pow = 11 i = 8 x = 3 pow = 21 i = 9 x = 3 pow = 16 23

import time
a = 87035158
n = 141897117
m = 251583961

t= time.time()
ModExp(a,n,m)
print time.time()-t

t= time.time()
mod(a^n,m)
print time.time()-t

1234567 0.00758504867554 1234567 42.6682598591

import time
a=323555;
n=12532777;
m=223532111


t= time.time()
ModExp(a,n,m)
print time.time()-t

t= time.time()
mod(a^n,m)
print time.time()-t

130889551 0.00142598152161