babygiant

64 days ago by voloch

#It works only when g is prim root mod p def dlog(h,g,p): return log( Mod(h,p), Mod(g,p)) dlog(7,2,10037) 
       
5585
5585
#Borrowed from lecture notes by F. Chamizo #https://www.uam.es/personal_pdi/ciencias/fchamizo/asignaturas/cripto1011/discretelog.pdf def baby_giant (h ,g , p ): baby = [1] giant = [h] n = 1 + floor(sqrt(p -1)) for i in range(1 , n ): baby.append( Mod( baby[i -1]*g , p ) ) gn = Mod(g , p )^(- n) for j in range (1 , n ): giant.append ( Mod(giant[j -1]*gn , p ) ) for inters in set( baby ).intersection( set( giant ) ): # print ’i = ’ , baby.index ( inters ) # print ’j = ’ , giant.index ( inters ) print baby.index( inters )+ n*giant.index ( inters ) baby_giant(7,2,10037) 
       
5585
5585
print Mod(2,10000001)^3000 for n in range(0,10000000): if Mod(2,10000001)^n == Mod(2719201,10000001): print n 
       
2719201
3000
912090
1821180
2730270
3639360
4548450
5457540
6366630
^C
Traceback (click to the left of this block for traceback)
...
__SAGE__
2719201
3000
912090
1821180
2730270
3639360
4548450
5457540
6366630
^C
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_8.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("cHJpbnQgTW9kKDIsMTAwMDAwMDEpXjMwMDAKZm9yIG4gaW4gcmFuZ2UoMCwxMDAwMDAwMCk6CiAgICBpZiBNb2QoMiwxMDAwMDAwMSlebiA9PSBNb2QoMjcxOTIwMSwxMDAwMDAwMSk6CiAgICAgICAgcHJpbnQgbg=="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))
  File "", line 1, in <module>
    
  File "/tmp/tmpGh3tKS/___code___.py", line 4, in <module>
    exec compile(u'for n in range(_sage_const_0 ,_sage_const_10000000 ):\n    if Mod(_sage_const_2 ,_sage_const_10000001 )**n == Mod(_sage_const_2719201 ,_sage_const_10000001 ):\n        print n
  File "", line 2, in <module>
    
  File "sage/rings/finite_rings/integer_mod.pyx", line 148, in sage.rings.finite_rings.integer_mod.Mod (/home/sage-build/sage-7.0/src/build/cythonized/sage/rings/finite_rings/integer_mod.c:3796)
  File "sage/structure/factory.pyx", line 361, in sage.structure.factory.UniqueFactory.__call__ (/home/sage-build/sage-7.0/src/build/cythonized/sage/structure/factory.c:1566)
  File "/home/sage-build/sage-7.0/local/lib/python2.7/site-packages/sage/rings/finite_rings/integer_mod_ring.py", line 195, in create_key_and_extra_args
    def create_key_and_extra_args(self, order=0, is_field=False):
  File "src/cysignals/signals.pyx", line 225, in cysignals.signals.python_check_interrupt (build/src/cysignals/signals.c:2429)
  File "src/cysignals/signals.pyx", line 96, in cysignals.signals.sig_raise_exception (build/src/cysignals/signals.c:1116)
KeyboardInterrupt
__SAGE__
is_prime(100000001) 
       
False
False
baby_giant(2719201,2,10000001) 
       
9093900
6366630
8184810
10002990
3000
1821180
2730270
5457540
3639360
912090
7275720
4548450
9093900
6366630
8184810
10002990
3000
1821180
2730270
5457540
3639360
912090
7275720
4548450
baby_giant(2719201,2,100000000003) 
       
22445090186
22445090186
Mod(2,100000000003).multiplicative_order() 
       
100000000002
100000000002
for n in range(1,20): p = 10^n +3 if is_prime(p): print p, n 
       
13 1
103 2
100003 5
1000003 6
100000000003 11
100000000000000003 17
1000000000000000003 18
13 1
103 2
100003 5
1000003 6
100000000003 11
100000000000000003 17
1000000000000000003 18
#crt(a,b,m,n) finds x with x=a mod m and x = b mod n crt(1,2,5,7) 
       
16
16