Pages:
Author

Topic: Pollard's kangaroo ECDLP solver - page 143. (Read 57532 times)

sr. member
Activity: 462
Merit: 696
May 01, 2020, 01:44:43 AM
#2
It is enough to modify slightly the way we generate the next jump:

+ jP[tamePosi.x % n]*G if y > p/2,  - jP[tamePosi.x % n]*G is y


(then I will indicate 'y' if y > p/2, '-y' if y < p/2)


in this way when a tame T reaches a point Q = (x,y) and a wild W reaches a point Q' = -Q = (x,-y), this become a collision

The tame and the wild will go on with 2 specular paths:

Q -> Q + k*G -> Q + k*G -r*G ->  ... -> DP
(x,y)    (x1,-y1)          (x2,y2)              (x0, y0)

-Q -> -Q -k*G -> -Q - k*G +r*G -> ... -> DP
(x,-y)   (x1,y1)         (x2, -y2)              (x0, -y0)

until they reach 2 symetric DP, for both of which we know the private key.


May be a brownian motion can be interesting (having positive and negative jump).

I have created a sort of "brownian motion", my kangaroos keep jumping back and forth.


I'm not sure to fully understand your idea.
You want to add a condition on the y parity to determine the jump ?
You let the starting positions as they are or you translate them ?

sr. member
Activity: 462
Merit: 696
May 01, 2020, 01:22:44 AM
#1
Hello,

I would like to present an interval ECDLP solver based on the Pollard's kangaroo method.
This program is fully open source and available on GitHub: https://github.com/JeanLucPons/Kangaroo
It has GPU support (CUDA Only) and works on both Linux and Windows.
This program is currently under development.

Thanks to test it and to share ideas of improvements here Wink
Pages:
Jump to: