CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutSign UpSign In

CoCalc Runs Your Jupyter Notebooks and Linux Terminals using Powerful CPUs and GPUs!

| Download

Simple index calculus algorithm for computing discrete logarithms, as presented in Lecture 10 of 18.783

Views: 280
License: AGPL3
Image: ubuntu2004
Kernel: SageMath 9.2
# generates a random Sophie-Germaine prime (p=2*q+1 with q prime) # we use these to make Fp^times as close to a cyclic group of prime order as possible # this means a Pohlig-Hellman attack on Fp^* will have very little benefit def random_sg_prime(bits): while true: p=random_prime(2^bits,2^(bits-1)) if is_prime(2*p+1): break return p def L(a,c,N): z = ceil(exp(c*log(N)^a*log(log(N))^(1-a))) if z%2: z+=1 return ceil(z) def trial_factor(x,B): f=[] lastp=0 while x > 1: p=x.trial_division(B) if p > B: return [] if p == lastp: f[-1][1] += 1 else: f.append([p,1]) x = x.divide_knowing_divisible_by(p) lastp = p return f def dlog(a,b,p): B=ceil(2*L(1/2,1/2,p)) print("smoothness bound is %d" % B) pi=[q for q in primes(B)] pimap=[0 for i in range(0,B)] i=0 for q in primes(B): pimap[q] = i i += 1 n=len(pi) print("factor base has %d elements, searching for relations..."%n) M=matrix(ZZ,n+2,n+2,sparse=true) t = cputime() bi = 1/b i = 0 while i < M.nrows(): e = randint(1,p-1) f=trial_factor(ZZ(a^e*bi),B) if f and f[-1][0] < B: for q in f: M[i,pimap[q[0]]]=q[1] M[i,n]=1; M[i,n+1]=e i += 1 print("Found %d relations in %.2f s, attempting to solve system"%(i,cputime()-t)) q = ZZ((p-1)/2) print(M) Mq=M.change_ring(GF(q)).echelon_form() M2=M.change_ring(GF(2)).echelon_form() print(Mq) print(M2) i = n; j = n while not Mq[i,n]: i-=1 while not M2[j,n]: j-=1 print(i,j,n) return ((q+1)*ZZ(Mq[i,n+1])+q*ZZ(M2[j,n+1]))%(2*q)
p=2*random_sg_prime(50)+1 print(p) F=GF(p) a=F.random_element() while a.multiplicative_order() != p-1: a=F.random_element() x=randint(1,p-1) b=a^x print("%d=%d^%d"%(b,a,x)) %time y=dlog(a,b,p) print("log_%d(%d) = %d"%(a,b,y)) assert x==y
2020931110946843 245756035897727=352172288978223^559351120578638 smoothness bound is 544 factor base has 100 elements, searching for relations...
WARNING: Some output was deleted.