Questions regarding Pollard's Kangaroo/Lambda

[WanderingPhilospher]

(I didn't want to clutter up specific programs' threads.)

First, I understand how the methods work. I have probably ran over 500 different tests at different bits.

I have also used 4 different versions of the programs and maybe that's where my questions spawns from.

To keep it simple, I am going to just use integer numbers.

Let's say I am searching for pubkey 100 in a range of 0 to 1000.  Let's also say that the tame and wild that solved the key are:

tame
pubkeyx1  940

wild
pubkeyx2  840

(940 - 840 = 100)

My tames were randomly set out in the middle of the range, say in the range of 400 to 600.

My wilds were randomly set out in the beginning of the range, say in the range of 0 to 200.

Now, here is the question:

Let's say tame pubkeyx1 originally started at 500 and worked its way up and past pubkeyx1 940 (the tame/point that helped solve the key). And wild pubkeyx2 originally started at 20...

Did the wild pubkeyx2 have to make it all the way up to tame pubkeyx1 940 to solve the key OR did it just have to make it to wild pubkeyx2 840, in order to solve the key??

With one version of the kangaroo program that I have used, if I know the key is in a 32 bit range, 80000000:FFFFFFFF, I know that my tames have to at least be in that range and the wilds have to be under that range.  Because it merely subtracts the two, example (tame) 9A82D6AB - (wild) 10000000 = private key 8A82D6AB. If the wilds are in the 80000000 thru FFFFFFFF range, the key will never be found because even FFFFFFFF - 80000000 = 7FFFFFFF, which is in the 31 bit range, not the 32 bit range.

Seems like some programs focus on a "path" and others focus on maybe hitting "random" points to solve?

[NotATether]

Seems like some programs focus on a "path" and others focus on maybe hitting "random" points to solve?

Yep, you pretty much nailed it. The reason why Kangaroo solvers all have different ways of making hops is because the algorithm intentionally leaves the jump term, the "pseudorandom map f: G -> S" blank, so different implementations need to fill it in with whatever they think is efficient.

This function is used to compute the next kangaroo hop (just insert the current kangaroo in it and you're done). It would be interesting to see if any research has been done to find the optimal hop function!

[j2002ba2]

This function is used to compute the next kangaroo hop (just insert the current kangaroo in it and you're done). It would be interesting to see if any research has been done to find the optimal hop function!

For Pollard Distributed Kangaroo (close enough to) the optimal is powers of two plus the last one making the mean jump value correct.