Quote from: kTimesG on Today at 05:04:22 PM

Quote from: arulbero on Today at 01:47:53 PM

Quote from: kTimesG on October 08, 2024, 07:16:49 PM

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.pdf

You 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.

Quote

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.