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.
The test i did was a simple calculation on a classical birthday paradox on 2 tables instead of one. I draw alternatively a random number in [0..N[ in each table and look for collision between the 2 tables. This converges to sqrt(PI.N). sqrt(PI/2.N) on a single table.
Now, I'm doing tests a in real situation, 1024 kangaroos, 10000 40 bit keys informally distributed, for the moment it seems to converge to 2.sqrt(N) + nbKangaroo.2^dp as expected, with dp=7 on 40bit search. In this situation (1024 << sqrt(N) - 2^dp), the approximation using the asymptote is good.
How do you tink, will it be faster?
Thanks for the reading.
No I don't think it will be faster
Example for Np=2, you have 2 ranges of w/2 so you perform a total of operation:
2.sqrt(w/2) + 2.sqrt(w/2) = 4/sqrt(2).sqrt(w) which is more than 2.sqrt(w)