-snip-
It ends in sqrt(PI).sqrt(n) ~= 1.772.sqrt(n)
Note that the precision afer 1.000.000 trials is about 1/sqrt(1.000.000)=0.001 so 3 digits are expected to be good.
2^0.825836 = 1.77256 , sqrt(PI) = 1.77245
Your empirical tests actually showed the results very closed to benchmark for Kangaroo known algorithm.
Yes, the 2*sqrt(n) was for simple Kangaroo method.
This is a very nice reading as well:
https://www.math.auckland.ac.nz/~sgal018/crypto-book/ch14.pdfFor three-kangaroo it is 1.818*sqrt(n) - Excercise 14.5.11 in reading above
For four-kkangaroo it is 1.714*sqrt(n) - Excercise 14.5.12 in reading above
You are using herds of kangaroos, so it is not simple one.
Can you please also have a look at the 14.6 section of the reading above? There is a Distributed Kanagroo Algorithm: let
Np is the number of processors;
[0, w] is the range. They divide the interval into
Np sub-intervals of size
w/Np and then run the kangaroo algorithm in parallel on each sub-interval.
The solution is to use a herd of
Np/2 tame kangaroos and a herd of
Np/2 wild kangaroos. This gives an algorithm with running time
O(sqrt(w/Np)).
How do you tink, will it be faster?