Quote from: arulbero on Today at 08:02:09 PM

Quote from: MrFreeDragon on Today at 07:23:27 PM

Quote from: arulbero on Today at 06:59:34 PM

-snip-
But can you treat these points like if they were random? Can you apply in this case the birthday paradox?

The DP method (distinguished points) with a hashtable is used. That means that every subsequent jump is dependent from the x-coordinate of the current location. That means that pseudorandom walks are used for the kangaroos. No need to store all the visited points for this case.

Yes, this is clear, but these points seem to me not to be really (pseudo)random. There is a order. You can move only forward (from private key's point of view). Therefor many collisions are just impossible to get (instead in the birthday paradox, each new distinguished point has the chance to produce a collision with any previous distinguished point, for example that happens in BTCCollider, because in that case you can jump in any position, you go back and forth across the entire space)

Example with only 2 sequences:

If we suppose that W_100 is = (2^37)*G and T_100 is (2^38)*G, than between T_101, T_102, .... , T_2**32 it is no longer possible to find a single distinguished point with the same coordinate of any distinguished point that lies in W_0, W_1, W_2, ....., W_100. For sure.

Then how do you apply in this case birthday paradox?

It is impossible to get a collision in the path of the same tame kangaroo too, because the same kangaroo cannot turn back, then this is a pseudorandom sequence very particular ...

I think that's why the papers you find don't use the birthday paradox to analyze pollard kangaroo. Birthday paradox is used for the very similar gaudry schost algorithm. Gaudry schost algorithm sets the point to a new random location in the interval as soon as a distinguished point is found and saved.