Post
Topic
Board Development & Technical Discussion
Re: Solving ECDLP with Kangaroos: Part 1 + 2 + RCKangaroo
by
kTimesG
on 30/12/2024, 15:09:05 UTC
Cheap point does not cost 0.5 op, practically it costs max 15-20% of op (it's just additional 1 MUL + 1 SQR and these additional calculations happen only in 50% of jumps), but if you don't use groups in inversions (or group size is small), it costs much less, so it's not a good idea to count cheap point as 1 op. That's why in some cases using cheap point makes the whole algorithm faster. For example, you can compile my "Kang1" project and press "SOTA" button and then "SOTA+" button to see about 8% speedup.

I can't follow up on your logic. A key is still a key, no matter what optimizations are used to compute it or whether it was 90% easier to compute it or not. By your logic, in order to compare efficiency, we should also reduce ((divide by 1.5) the reported complexity of any other implementations that use this "trick", but count the number of computed keys (not the number of iterations). For example BSGS where this trick does wonders. Or maybe a kangaroo with weak DPs. Is it fair?

But it's your software so do as you wish, but please try to not be misleading at the abstract level. The number of iterations where you do whatever you want is not at all the same thing as the number of computed X & Y.