Post
Topic
Board Development & Technical Discussion
Re: Pollard's kangaroo ECDLP solver
by
brainless
on 03/07/2021, 05:05:54 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.
Guys fyi 1024 is not div point in ecc, posting here, divideable magic digits for ecc, these will help you to decide bitrange to divide, use these magic ecc div numbers, for pollard kanagroo or other manual div

2   447   7572   564114
3   596   9536   752152
4   631   10096   1128228
6   894   14304   1504304
8   1192   15144   2256456
12   1262   20192   3008608
16   1788   28608   4512912
24   1893   30288   6017216
32   2384   40384   9025824
48   2524   60576   18051648
64   3576   94019   
96   3786   121152   
149   4768   188038   
192   5048   282057   
298   7152   376076