...
So a total of 6 multiplications for each jump of each kangaroo.
Problematic lines are these ones reducing the 256x256 product back to mod N:
https://github.com/JeanLucPons/Kangaroo/blob/37576c82d198c20fca65b14da74138ae6153a446/GPU/GPUMath.h#L856
https://github.com/JeanLucPons/Kangaroo/blob/37576c82d198c20fca65b14da74138ae6153a446/GPU/GPUMath.h#L905
https://github.com/JeanLucPons/Kangaroo/blob/37576c82d198c20fca65b14da74138ae6153a446/GPU/GPUMath.h#L1017
2-step reduction is only guaranteed to be correct for Mersenne primes where r = 1
For secp256k1 r is 2**32 + 977, not 1. So 2 steps are not enough.
So since there's an error ratio of only using 2-steps folding: r(r - 1) / 2N
and you have 6 multiplications / jump
and you do a lot of jumps deterministically
at some point, that error will exhibit itself and all future computations get screwed up.
So a total of 6 multiplications for each jump of each kangaroo.
Problematic lines are these ones reducing the 256x256 product back to mod N:
https://github.com/JeanLucPons/Kangaroo/blob/37576c82d198c20fca65b14da74138ae6153a446/GPU/GPUMath.h#L856
https://github.com/JeanLucPons/Kangaroo/blob/37576c82d198c20fca65b14da74138ae6153a446/GPU/GPUMath.h#L905
https://github.com/JeanLucPons/Kangaroo/blob/37576c82d198c20fca65b14da74138ae6153a446/GPU/GPUMath.h#L1017
2-step reduction is only guaranteed to be correct for Mersenne primes where r = 1
For secp256k1 r is 2**32 + 977, not 1. So 2 steps are not enough.
So since there's an error ratio of only using 2-steps folding: r(r - 1) / 2N
and you have 6 multiplications / jump
and you do a lot of jumps deterministically
at some point, that error will exhibit itself and all future computations get screwed up.
That error rate would be approximately 2**32 squared, i.e. 2**64, divided by 2**256 so 2**-192 per kangaroo.
If we want to be pragmatic, then approximately 2**-190 something per kangaroo or a 1/2**190 chance it messes up, when we account the 6 multiplications per kangaroo.
But it's still a really small number.
Almost as infrequent as generating a specific 192-bit elliptic private key. Not that anyone would do that, though.
The specific condition that would happen, I found in the paper you linked
We can make a lot of pairs for which they are equal to the un-reduced product. But it is much harder to satisfy the second condition, and I don't know if anyone has generated any counter-examples.