Exponentiation and GCD

94 days ago by bcr49

Define an element in the group of integers modulo n:

n = 1000124 k = 10^3 Zn = Integers(n) a = Zn(7) print a 
       

Sage automatically uses fast exponentiation:

time a^k 
       

The naive algorithm:

b = a k = 10^3 import time t = time.time() for i in range(1,k) : b = b*a s = time.time() print b print "took", s-t, "seconds" 
       
k = 10193059130590139501351 time a^k 
       

Fast exponentiation worked out by hand...

k = 135 k2 = k.digits(2) pows_a = [a] b = a ak = 1 for i in range(1,len(k2)) : ak = ak*b^(k2[i-1]) b = b*b pows_a.append(b) ak = ak*(b^k2[len(k2)-1]) print k2 print pows_a print ak print a^k 
       

Below are examples computing XGCD:

time M = fibonacci(1000) time N = fibonacci(1001) print floor(log(M,2)) + 1 time d = GCD(M,N) 
       
d,s,t = sage.arith.misc.XGCD(M,N) print s*M + N*t == d 
       
(s*M).mod(N) 
       
print s.mod(N) print M.mod(N)