Fast Powering Algorithm

153 days ago by bsbblk75

g = 14; A = 33887; N = 33889; print "g =", g print "A =",A print "N =",N aa = A.digits(2) bb = [] sum = 1 c = 0 d = 0 e=0 print A ,"=", for i in range(len(aa)): c += 1 if aa[i] == 1: print "2^",i, if c == len(aa): print " ", else: print "+", print "\n",g,"^",A ,"=", for j in range(len(aa)): d += 1 if aa[j] == 1: print "(",g,"^2^",j,")", if d == len(aa): print " ", else: print "x", z = (g^(2^j))%N sum = sum * z print "\n",g,"^",A ,"=", for h in range(len(aa)): e += 1 if aa[h] == 1: z = (g^(2^h))%N print z, if e == len(aa): print "(mod", N ,")", else: print "x", print "\nAns",g,"^",A,"=",sum%N, "( mod",N,")" 
        
g = 14
A = 33887
N = 33889
33887 = 2^ 0 + 2^ 1 + 2^ 2 + 2^ 3 + 2^ 4 + 2^ 6 + 2^ 10 + 2^ 15   
14 ^ 33887 = ( 14 ^2^ 0 ) x ( 14 ^2^ 1 ) x ( 14 ^2^ 2 ) x ( 14 ^2^ 3 ) x
( 14 ^2^ 4 ) x ( 14 ^2^ 6 ) x ( 14 ^2^ 10 ) x ( 14 ^2^ 15 )   
14 ^ 33887 = 14 x 196 x 4527 x 24773 x 5628 x 10991 x 32957 x 12615 (mod
33889 ) 
Ans 14 ^ 33887 = 7262 ( mod 33889 )
g = 14
A = 33887
N = 33889
33887 = 2^ 0 + 2^ 1 + 2^ 2 + 2^ 3 + 2^ 4 + 2^ 6 + 2^ 10 + 2^ 15   
14 ^ 33887 = ( 14 ^2^ 0 ) x ( 14 ^2^ 1 ) x ( 14 ^2^ 2 ) x ( 14 ^2^ 3 ) x ( 14 ^2^ 4 ) x ( 14 ^2^ 6 ) x ( 14 ^2^ 10 ) x ( 14 ^2^ 15 )   
14 ^ 33887 = 14 x 196 x 4527 x 24773 x 5628 x 10991 x 32957 x 12615 (mod 33889 ) 
Ans 14 ^ 33887 = 7262 ( mod 33889 )
print (2^(2^ 0))%100000000000000000039 print (2^(2^ 6))%100000000000000000039 print (2^(2^ 7))%100000000000000000039 print (2^(2^ 8))%100000000000000000039 print (2^(2^ 11))%100000000000000000039 print (2^(2^ 12))%100000000000000000039 print (2^(2^ 15))%100000000000000000039 print (2^(2^ 16))%100000000000000000039 print (2^(2^ 19))%100000000000000000039 print (2^(2^ 22))%100000000000000000039 print (2^(2^ 23))%100000000000000000039 print (2^(2^ 29))%100000000000000000039 
        
2
18446744073709551616
30664484332602210769
38765866666381055393
13078627891682156039
10114606423200458779
71176776724138243818
34745613330462426253
47602120380226781882
70469453233933238243
93824015611291273246
30757741903835186386
2
18446744073709551616
30664484332602210769
38765866666381055393
13078627891682156039
10114606423200458779
71176776724138243818
34745613330462426253
47602120380226781882
70469453233933238243
93824015611291273246
30757741903835186386
print (2^(2^ 35))%100000000000000000039 print (2^(2^ 38))%100000000000000000039 print (2^(2^ 40))%100000000000000000039 print (2^(2^ 42))%100000000000000000039 print (2^(2^ 47))%100000000000000000039 print (2^(2^ 48))%100000000000000000039 print (2^(2^ 49))%100000000000000000039 print (2^(2^ 50))%100000000000000000039 print (2^(2^ 52))%100000000000000000039 print (2^(2^ 53))%100000000000000000039 print (2^(2^ 55))%100000000000000000039 print (2^(2^ 57))%100000000000000000039 print (2^(2^ 58))%100000000000000000039 print (2^(2^ 62))%100000000000000000039 (2^(2^ 66))%100000000000000000039 
        
Traceback (click to the left of this block for traceback)
...
RuntimeError: Segmentation fault
Traceback (most recent call last):    print (2^(2^ 49))%100000000000000000039  
  File "", line 1, in <module>
    
  File "/tmp/tmpb3m7jV/___code___.py", line 3, in <module>
    print (_sage_const_2 **(_sage_const_2 ** _sage_const_35 ))%_sage_const_100000000000000000039   
  File "integer.pyx", line 1846, in sage.rings.integer.Integer.__pow__ (sage/rings/integer.c:13194)
RuntimeError: Segmentation fault
(2^2^66)%100000000000000000039 
        
Traceback (click to the left of this block for traceback)
...
RuntimeError: exponent must be at most 9223372036854775807
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_29.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("KDJeMl42NiklMTAwMDAwMDAwMDAwMDAwMDAwMDM5"),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))
  File "", line 1, in <module>
    
  File "/tmp/tmpECfKXt/___code___.py", line 3, in <module>
    exec compile(u'(_sage_const_2 **_sage_const_2 **_sage_const_66 )%_sage_const_100000000000000000039 
  File "", line 1, in <module>
    
  File "integer.pyx", line 1839, in sage.rings.integer.Integer.__pow__ (sage/rings/integer.c:13120)
RuntimeError: exponent must be at most 9223372036854775807