I am currently working on the implementation of a parallelized Pollard-Rho algorithm. I want to use the @parallel command to
D = {}
@parallel(4)
def dist_points(P,Q,dist_prop,r):
ord = P.order()
seed = randint(1,ord)
X = [seed*P,seed, 0]
counter = 0
counter4 = 0
m = [randrange(0,ord) for i in range(r)]
n = [randrange(0,ord) for k in range(r)]
T = [(m[j]*P + n[j]*Q) for j in range(r)]
while(True):
#step function (linear walk)
X = step_linear(T,m,n,ord,X,r)
counter += 1
counter4 += 1
(Pi, ai, bi) = X
x_coord = Pi[0]
global D
if ZZ(x_coord)%dist_prop==0:
if Pi in D:
(a,b) = D[Pi]
if gcd((b-bi),ord)==1:
log = ((ai-a)/(b-bi))%ord
return log, counter4
else:
D[Pi] = (ai,bi)
seed = randint(1,P.order())
X = [seed*P, seed, 0]
counter = 0
elif counter > 100*dist_prop:
seed = randint(1,P.order())
X = [seed*P,seed, 0]
The result of the function works. But I have the feeling that the parallelization does not work. I want my 4 CPU's to work parallel on a same list D looking for points until they find a match. But when I change the 6th line to
X = [P,1,0]
so that all the CPU's do the same walk (since my step_linear function is deterministic), I get the same timing. So it seems that the parallization does not work...
Also this program should work faster for a dist_prop>1. Since we put otherwise all points in the list, and then there is no need for a parallelization right? But my program gets slower the bigger the 'dist_prop' is.
So I thought that might be due to a wrong use of the @parallel command.
I hope someone can help me with the parallel problem!
Does anyone see my mistake? counter = 0
