Post
Topic
Board Development & Technical Discussion
Re: Solving ECDLP with Kangaroos: Part 1 + 2 + RCKangaroo
by
RetiredCoder
on 30/12/2024, 09:59:26 UTC
But then again, it depends what you are counting.

I don't check cheap points for DP, it's senseless. Instead, I choose cheap point as next point if it has even X. So I use it for kang walking and prefer even X when possible, it helps kangs to collide faster.

Code:
// rec->iters++; point (PreviousPoint - JumpPoint) is cheap so we don't count it

Can you explain what you are referring to as "K"? Because any algorithmician can tell you that once you do 1.5 times more operations / loop (such as your "cheap point" even X preference with a 50% increase in ops count) and you ignore the extra .5 steps, then this "K" of yours is not really useful for anything, no one should care about how many iterations your algorithm does, but the number of group (or field) operations.

Cheap point does not cost 0.5 op, practically it costs max 15-20% of op (it's just additional 1 MUL + 1 SQR), but if you don't use groups in inversions, 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.