SharedModular Exponentiation .sagewsOpen in CoCalc
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