And still people believe BSGS would work faster. for whatever reason, with TB of RAM.. I let them continue believing that.
BSGS algorithm applied to secp256k1 curve only need 1.0 sqrt(N) operations (on average) and 1.5 sqrt(N) operations in the worst case:
https://eprint.iacr.org/2015/605.pdfYou only need to store 0.5 sqrt(N) keys (the baby steps) : from 1*G to 0.5*sqrt(N)*G
and compute in the worst case 1.0 * sqrt(N) keys (the giant steps)
Only additions and subtractions, no multiplications.
Conclusion
...
The new algorithms, like the original, have low overhead but high memory.
This means that our algorithms are useful only for discrete logarithm problems
small enough for the lists to fit into fast memory
Kangaroo doesn't need fast memory. Or any memory at all. I'd say it's a good trade-off.
Kangaroo is only probabilistic, don't lose focus, Kangaroo doesn't need much power to play the birthday paradox puzzles. Be careful not to ruin the birthday paradox in the search for more speed.