babygiant

382 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(5,2,10037) 
       
4861
4861
#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(5,2,10037) 
       
4861
4861
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
7275720
8184810
9093900
2719201
3000
912090
1821180
2730270
3639360
4548450
5457540
6366630
7275720
8184810
9093900