New version of Python Kangaroo!
Using gmpy2 to accelerate a little bit the field math yields around 400k ops/s so please do not use this to search for high-bit puzzles.
I added some different strategies for sampling tames and wilds from the search interval which affects the theoretical complexity. My goal was to validate the following strategies:
- interval [0, b) using van Oorschot parameters for parallel collision should average 2* sqrt(b) ops
- interval [-b/2, b/2] using equivalence classes and birthday paradox should average 1.36 * sqrt(b) ops
- the 3-kangaroo method using negation symmetry should have resulted in 1.72 ... 1.81 * sqrt(b) ops
So what's the catch? After doing around 1000 test runs using random private keys with misc. strategies the average solving complexity (the sqrt(b) factor excluding the DP overhead) doesn't really match expectations:
- when DP = 0 (all points are DP) and we use the negation symmetry we can converge to almost 1.36 * sqrt(b) ops on average, which I think it is close to the minimal possible complexity conjectured by Pollard, e.g. 1.25 sqrt(b)
- when DP > 0, if we only jump forward, symmetry fails for walks, and complexity seems to go back to 2.0 sqrt(b) or worse.
How to fix? Jump side-by-side in deterministic way, so use Y sign to determine if jump goes forward or backward. Now we can end up with cycles in the jump travel. Most of them are 2-cycles (next jump goes to the same element as previous jump) which can easily be detected, and if so, jump again with the previous distance instead of jumping back to the previous point...
THREE kangaroos!The papers analyse how we can use a third walk and solve the key whenever ANY two of the three walks collide, when only traveling forward. The trick is that we also start with a wild kangaroo that starts from -P plus some offset. Then we have three types of collision:
T / W1: solve for k = tameDist - wildDist
T / W2: solve for k = tameDist + wildDist (e.g. P traveled "backward" since -P walked forward)
W1/W2: if offsets don't sum up to 0, then k = (w1 - w2) * 2**-1
Because we hash DP by X we can easily solve the 4 different cases of each type of collision and check if it's the solution.
Tames should start at around -b/2 + b*8/10 == b*3/10 -this makes average distance to P or -P less than 0.2*b and means we would have to travel shorter walks on average.
Pollard's paper for 3 and 4 kangaroos suggest that the complexity should be 1.81 sqrt(b) or even 1.71 sqrt(b) for 4 kangaroos. I wasn't able to reach this complexity by using the suggested mean jump size (0.375*sqrt(b)). This strategy should in theory keep the same complexity when using DP > 0 and be parallelizable with same van Oorschot methodology. Both of these statements are in the paper, but I didn't manage to have success with them. So if anyone knows more about this 3 or 4 kangaroos, please explain:
- what is the maximum expected/allowed walk distance for a tame and for a wild_1 and wild_2?
- does the parallelization using van Oorschot (e.g. start = idx * v + z) apply or not? has anyone ever actually studied this?
Again - do not search for puzzles using this script. It is 100% just of theoretical interest.
CODE:
https://pastebin.com/8Z69sRcUCouldn't embed in post as it was too long...
