Hi

I already think about this method of searching for a collision between a temporary key (for example every intermediate wild kangaroo jump) and a lookup in a  hashtable of precomputed  random key in the range of puzzle 120.

Let-s do some math to show if it is realistic or not...

Imagine that you will precompute an huge hashtable (or a bloom filter) of 256 Gigas entries (or 256Giga  keys picked up at random in the puzzle 120 interval)

Forget the fact that this table will occupe several TerraBytes of RAM and that the lookup time will increases with the size of the hashtable (less true for a bloom filter look up).

The formula which defines the probability of finding a particular piece among N pieces at the end of n draw without replacement, is as follows:

P=1-(1-1/N)^n

we can replace 1/N by (number_entries_in_hashtable/interval_of_puzzle_120) =  256*10^9/(2^120-2^119) = 3.85e-25


We fixed  for example P=0.5 (means a probability of having an hit of 50%)

Let's calculate n for such P=0.5

0.5=(1-1/N)^n

a=b^n => n=ln(a)/ln(b)

n=ln(0.5)/ln(1-3.85e-25) = 1.8e24
if your GPU can do 1 billion  jumps (and lookup at the same time) per second (typically the speed of Jean-Luc pons program with a good GPU)

You will have to wait 1.8e24/1e9 = 1.8e15 seconds or  57 Millions of years before having 50% of having an hit...

Hopeless..., even if you uses a bigger hashtable or a powerfull GPU cloud.


The main problem of this approach is that you don't  profite of the birthday paradox used in the kangaroo solver because you look for in a predefined list.

Regards

Fanch