babygiant

621 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 "", line 1, in File "_sage_input_8.py", line 10, in 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 File "/tmp/tmpGh3tKS/___code___.py", line 4, in 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 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