@parallel Parallel Pollard-Rho

savecancel

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]
            counter = 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!