Post
Topic
Board Development & Technical Discussion
Re: Pollard's kangaroo ECDLP solver
by
arulbero
on 17/06/2020, 13:23:58 UTC
Tomorrow I will also investigate how long would it take with the VanitySearch engine optimized for V100 to solve #64.
Then we will make our choice on attacking #64 or #120.

In the search of #64 you will find several points with x-coordinate with the leading 60 bits = 0. You could use them here as jumps to save space (or to use more jumps in the same space). 


Unfortunately I don't see how to reuse the work file on a different range.
This work file is for [2^114,2^115-1].

If you translate the kangaroos, the paths will differ so you have to redo all the job.

There was an interesting question in a previous message of this topic:
Why paths are important and why not adding DP without computing paths ?

Using only DP:
It is like drawing a random number in a reduced space N/2^dpbit so time to solve will be O( sqrt(N/2^dpbit) )
However, it is true, that you can reach a DP faster in this way by computing consecutive points.

Using paths:
It is like drawing a bunch of 2^dpbit random points at each DP, so time to solve is O( sqrt(N)/2^dpbit )
The "gain" using path is 2^dpbit while without paths, the "gain" is only sqrt(2^dpbit)

So even if reaching a DP without path is faster, the gain is not enough to beat path.

I think that a DP worth is equal to the length of the path you computed to find it.
 
If you find a DP with 25 bits = 0 after 2^27 steps, that point should be worth like 4 points, each with 25 bits = 0 and found after 2^25 steps. It is like a DP with 25 bits = 0 is equal to a DP with 27 bits = 0.

If you reuse only the DPs you found after 2^27 steps, you will have a better ratio "space occupied / chance to find a collision"