# Initialization
g = 1069
p = 41723027
x = 24122008
d = p-1
#Used to calculate the time to execute
time=cputime()
# Factorization of d
factors = []
factorization = factor(p-1)
for i in range (len(factorization)) :
factors.append(factorization[i][0])
print "Factors: "
print factors
# we use CRT_list afterwards, that's why we collect data in a list
dloglist = ([],[])
# step 2 and 3 of the algorithm
for i in factors :
g_i = power_mod(g,int(d/i),p)
x_i = power_mod(x,int(d/i),p)
a = Mod(g_i,p)
b = Mod(x_i,p)
a_i = discrete_log_rho(b,a)
dloglist[0].append(a_i)
dloglist[1].append(i)
print "dloglist: "
print dloglist
# compute the dLog with the CRT
dlog = CRT(dloglist[0],dloglist[1])
print "dlog: "
print dlog
print "Time: "
cputime(time)