Quote from: RetiredCoder on Today at 04:57:24 PM

Quote from: kTimesG on Today at 04:20:33 PM

My bad, the page layout was confusing. Page 13, last paragraph, before formula (6) (which looked like a page number instead).

Ok, now I see this funny formula. And I'm still sure that if I have a million kangaroos, best average jump is about sqrt(range) instead of 250000*sqrt(range).
You can confirm it easily even with JLP software which uses millions of kangaroos but correctly calculates jumps table based on the range only, ignoring the number of kangaroos. Try to multiply jump distances by a million and you will get worse results.
Why? Probably because when we have a lot of kangaroos they start using birthday paradox and this formula doesn't work anymore.

The average jump distance is the one that needs to be multiplied by m, not every jump distances!

The average jump distance = sum(jump_distances) / len(jump_distances)

The jump table needs to be created to approximate the optimal average jump distance.

I just did a test on 32 bits range, with DP 4. 512 tame kangaroos + 512 wild kangaroos.

Search interval is [G, 2G, 3G .... 2**32*G) - no symmetry, plain old algo just like JLP.

Random private keys for each solve.

Case 1.
Tame = random between b/2 and b
Wild = random between 1 and b / 2
alpha = sqrt(b) : 21 jump points. Results:

Code:

[360] AVG Ops: 178024 (2.591 * sqrt(b) + (dp_ovh = 2**13.0)) AVG Stored: 11141 AVG k_crt: 1030 AVG Speed: 302632 op/s
Solve for 4192504422
kangaroos (m): 1024
jump distances |A|: 21
avg jumps / kang: 144
expected total jumps: 147456 17.17 bits
avg ideal jump distance: 65536 16.00 bits
avg real jump distance: 65536 16.00 bits

Case 2.
Tame = random between b/2 and b
Wild = random between 1 and b / 2
alpha = m * sqrt(b) / 4 : 29 jump points. Results:

Code:

[360] AVG Ops: 154143 (2.227 * sqrt(b) + (dp_ovh = 2**13.0)) AVG Stored: 9652 AVG k_crt: 1025 AVG Speed: 291626 op/s
Solve for 1225828495
kangaroos (m): 1024
jump distances |A|: 29
avg jumps / kang: 144
expected total jumps: 147456 17.17 bits
avg ideal jump distance: 16777216 24.00 bits
avg real jump distance: 16777216 24.00 bits

Case 3.
Tame = b/2 + i * 37
Wild = i * 37
alpha = sqrt(b) : 21 jump points. Results:

Code:

[3] AVG Ops: 11381760 (173.547 * sqrt(b) + (dp_ovh = 2**13.0)) AVG Stored: 672622 AVG k_crt: 43186 AVG Speed: 386195 op/s
Solve for 3609233275
kangaroos (m): 1024
jump distances |A|: 21
avg jumps / kang: 144
expected total jumps: 147456 17.17 bits
avg ideal jump distance: 65536 16.00 bits
avg real jump distance: 65536 16.00 bits

(I stopped after 3 runs since it was obvious this was an awful test case).

Case 4 (the one I consider the correct one and by the book).
Tame = b/2 + i * 37
Wild = i * 37
alpha = m * sqrt(b) / 4 : 29 jump points. Results:

Code:

[360] AVG Ops: 151573 (2.188 * sqrt(b) + (dp_ovh = 2**13.0)) AVG Stored: 9454 AVG k_crt: 1042 AVG Speed: 323303 op/s
Solve for 479613323
kangaroos (m): 1024
jump distances |A|: 29
avg jumps / kang: 144
expected total jumps: 147456 17.17 bits
avg ideal jump distance: 16777216 24.00 bits
avg real jump distance: 16777216 24.00 bits

So, ranking them by best to worst:

1. alpha = m * sqrt(b) / 4, spread start points evenly
2. alpha = m * sqrt(b) / 4, random start points
3. alpha = sqrt(b), random start points
4. alpha = sqrt(b), evenly spread start points.

So, where did you see that results are "worse"?