I coded the stuff as it is described in the paper using this:
And a of translation of -N/2.G of the public key to solve in order to have as specified:
It found as expected from time to time the symmetric point.
It is slower than the classic version (~2^21.2 on 40bit search) and far from 1.46sqrt(n)
But, they are not very clear on the jumps and especially the average distance of the jumps.
As the wild are on a shorter range, may be steps have to be different than tame's one (not yet tested).
I also didn't coded a stop and retry after a certain number of jump (sqrt(n) ?), i let the algorithm continue outside the range, so it may loose the symmetry...
To be continued...
Code:
T={{a,−a}:a∈[−N/2,N/2]},
W={{n+a,−(n+a)}:a∈[−N/4,N/4]
W={{n+a,−(n+a)}:a∈[−N/4,N/4]
And a of translation of -N/2.G of the public key to solve in order to have as specified:
Quote
Each experiment involved choosing uniformly at random−N/2≤n≤N/2 and solving the DLP for Q= [n]P.
It found as expected from time to time the symmetric point.
It is slower than the classic version (~2^21.2 on 40bit search) and far from 1.46sqrt(n)
But, they are not very clear on the jumps and especially the average distance of the jumps.
As the wild are on a shorter range, may be steps have to be different than tame's one (not yet tested).
I also didn't coded a stop and retry after a certain number of jump (sqrt(n) ?), i let the algorithm continue outside the range, so it may loose the symmetry...
To be continued...
Did you also re-randomize the point after distinguished point was found (they are using gaudry schost method in the paper)?
Edit:
Another way to optimize memory access and speed:
Don't save jumped distances. When a collision between wild and tame was found you know T and W starting offsets and replay the walk for this pair only but this time with jump distances saved (replay of single pair on CPU should be sufficient).
I got this idea from another paper which I can't remember right now.
This is straightforward with Pollard Kangaroo but you have to account for the re-randomization when using Gaudry Schost method (remember new offsets).
