Quote from: Etar on Today at 10:42:38 AM

Quote from: kTimesG on Today at 10:24:43 AM

What trick is that?

https://bitcointalk.org/index.php?topic=5244940.msg54629413#msg54629413

Quote from: Etar on November 06, 2024, 07:14:40 PM

But today I changed the jump table (as you hinted) and here is the result: on the first attempt the key in the 85-bit range was found in 6 minutes, and the second in 14 minutes.

So the trick is to spread out existing DPs into the higher interval, by changing the perspective on the generator..

But because jump rules need to be identical, this means the jumps are also multiplied as well, to make the same jumps, like this:

Code:

Old jump dist New jump dist
1 M
2 2M
...

where M = 2, 4, 8, 16, 32, etc.

I think this doesn't scale because the smaller jumps are lost and the average jump distance doubles, each time the interval doubles.

If we have some optimal average jump distance = m * sqrt(b) / 4 where m = number of kangaroos

then when the interval doubles, this becomes m * sqrt(2*b) / 4 (the optimal average grows by 1.4142 not by 2)

For 5 interval doublings this becomes m * sqrt(32*b) / 4 (it should increase 5.7 times, not 32 times)

Let's try to compensate by changing the number of kangaroos such that the average is optimal:

We want m * s * sqrt(32*b) / 4 == m * 32 * sqrt(b) / 4

s = m * 32 / sqrt(32) = m * sqrt(32)

And lo and behold - we now need sqrt(32) more kangaroos, to have the same expected number of group operations to solve.

Which is exactly as much as we'd need by not bothering with rearranging jump points, changing G, etc.