Quote from: Lugh1Man on Today at 11:42:58 AM

Hi All,

I've been reading this and other related topics for a few weeks and I'm trying to understand the complexity of the different algorithms and approaches.

For Pollard's Kangaroo algorithm, someone gave an estimate of 2^66.05 operations needed for solving #130 ( https://bitcointalk.org/index.php?topic=5244940.2740 not sure how they reached this conclusion, but from reading about the algorithm it has a similar complexity to BSGS). This equals ~7.6x10¹⁹ operations needed.
For BSGS, from reading about it, is has a complexity of O(n^1/2). Taking the square root of the range (2¹³⁰ - 2¹²⁹ - 1) equals ~2.6x10¹⁹ operations needed.

Is this correct? Is BSGS more efficient, or is it just a wrong way of calculating the efficiency?
I think I'm missing something in estimating the total "operations needed" for these algorithms. Is there a better/correct way of doing this?
Edit: -> Reading keyhunt's documentation, it says it can easily reach the speed of several peta-keys per second (10¹⁸), so I'm definitely missing something...

Considering HW limitations, I am still not familiar with how different Kangaroo implementations work, I see that the JeanLucPons' based on VanitySearch requires GPU power (I assume more cores means better, but not sure what is the requirement for VRAM, CPU, RAM).
For BSGS, seems like keyhunt is the best, and works better with more RAM and more CPU cores.
Am I missing anything? Are there any other/better tools available for searching the ranges with known public keys?

If you read Jean Luc’s kangaroo GitHub, you would see how I estimated the number of ops needed. Here is a link to it:

https://github.com/JeanLucPons/Kangaroo#how-it-works

It has links to academia papers on the algo.

The quick way to calculate is to take the bit range, 130, divide by 2, add 1.05.
130/2 + 1.05 = 2^66.05

While Kangaroo and BSGS are similar, they are different. Probabilistic versus deterministic.

Choose a mid range and run both programs, with your hardware/equipment, and compare results.