-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 pseudorandom.
Example with only 2 sequences:
We suppose that W100 is = 2^80*G and T100 is 2^90*G, than between T101, T102, .... is not possible to find a distinguished points with the same coordinate of W0, W1, W2, ....., W100.
Then how could you apply in this case birthday paradox?