# initialization
# Step 1
# p=modulus, g=base
p=41723027
g=1069
x=24122008
time=cputime()
# q=order of Zp
q=p-1
# create factorbase
B=97
factorbase = []
for l in prime_range(1,B+1):
factorbase.append(l)
print "factorbase B: ", factorbase
print ""
last_element = factorbase[len(factorbase)-1]
# B-Smooth Checker
def is_B_smooth2(i):
factors = []
counter = 0
factorization = factor(i)
for i in range (len(factorization)) :
factors.append(factorization[i][0])
for i in range (len(factorization)) :
if factorization[i][0]>last_element:
counter = counter+1
else:
counter = counter
if counter >0:
return false;
else:
return true;
# Find Position in Factorbase
def get_position(zahl):
for position, item in enumerate(factorbase):
if item == zahl:
return position
equations = []
temp_vector = []
temp_row=[]
temp_matrix= []
# first random e
e=1;
# Create empty Matrix Row
def clear_temp_row():
del temp_row[0:len(temp_row)]
for z in range(len(factorbase)):
temp_row.append(0);
while len(equations)<len(factorbase):
to_check=power_mod(g,e,p)
if is_B_smooth2(to_check):
counter=0;
for equal_check in range(len(equations)):
if equations[equal_check]==to_check:
counter=counter+1;
else:
counter=counter
if counter==0:
equations.append(to_check)
temp_vector.append(e)
to_check_factor=factor(to_check)
clear_temp_row()
for l in range(len(to_check_factor)):
pos=get_position(to_check_factor[l][0])
temp_row[pos]=to_check_factor[l][1]
temp_matrix.append(list(temp_row))
e=e+1;
# Step2
# Some converting stuff which finally made it work :)
sol_vector1=vector(temp_vector).Mod(2)
sol_matrix1=matrix(list(temp_matrix)).mod(2)
sol_X = sol_matrix1.solve_right(sol_vector1)
sol_vector2=vector(temp_vector).Mod(1987)
sol_matrix2=matrix(list(temp_matrix)).mod(1987)
sol_X2 = sol_matrix2.solve_right(sol_vector2)
sol_vector3=vector(temp_vector).Mod(10499)
sol_matrix3=matrix(list(temp_matrix)).mod(10499)
sol_X3 = sol_matrix3.solve_right(sol_vector3)
sol_X = vector(ZZ, sol_X)
sol_X2 = vector(ZZ, sol_X2)
sol_X3 = vector(ZZ, sol_X3)
A=list(sol_X)
B=list(sol_X2)
C=list(sol_X3)
ABC=[A,B,C]
# mod is hardcoded here, because of some problems with CRT_vectors
sol_Xfin = CRT_vectors(ABC,[2,1987,10499])
print ""
print "dLogs:",sol_Xfin
print ""
done=0
while done==0:
random_e = ZZ.random_element(2,1337)
xge = Mod(x*g^random_e,p)
if is_B_smooth2(int(xge)):
done=1
print "random e: ", random_e
print "X*g^e: ", xge
xge_factor = factor(int(xge))
print "Faktorisierung von X*g^e: ",xge_factor
sum = 0;
for i in range (0,len(xge_factor)):
curr_pos = xge_factor[i][0]
addition = Mod(int(xge_factor[i][1])*int(sol_Xfin[get_position(curr_pos)]),p-1)
sum = Mod(sum + addition,p-1)
sum=sum-random_e;
dLog = Mod(sum,p-1)
print "Solution: ", dLog
print "Time: "
cputime(time)