Post
Topic
Board Development & Technical Discussion
Re: Pollard's kangaroo ECDLP solver
by
NotATether
on 02/07/2021, 07:24:10 UTC
I don't understand how the search is calculated in this particular range.
Explain in a nutshell.

Start range is subtracted from End range to make a new range between 0 and end-start, which is searched instead.

Then we make a batch, or herd, of 1024 starting points, with tames and wild points overlapping each other like this: Tame Wild Tame Wild Tame... The tame random points between 0 and end-start=range, and the wild points will have them between -range/2 and range/2. These are the starting points


We take some random numbers, the same amount as herd points, between 0 and range/2 as "jump points" and subtract them from our herd points. Resulting numbers are then placed in an Group (which in Kangaroo is just defined as a collection of numbers) and ModInv is applied to all of them.

For iteration we compute:

Rx = (Py - JumpPointY [mod n]
    * Group [mod n])
  ^2 [mod n]
  - JumpPointX [mod n]
  - Py [mod n]

Ry = Px - Rx [mod n]
  * (Py - JumpPointY [mod n]
    * Group [mod n])
  - Py [mod n]

For each g in CPU_GRP_SIZE (2014)


And the search points P are replaced with the ones in R.