Quote from: Veliquant on Today at 04:52:25 PM

Quote from: kTimesG on Today at 01:27:55 PM

You know, this thread is a POC about something called SOTA+ method, not 3-kang.

Thanks for your answer. Yes, I am trying to understand SOTA+, but I believe I have to learn all the methods in order to understand SOTA+. This means in order to understand SOTA+, I should understand 2 kangaroos, then 3-4 kangaroos, then Mirror, and then SOTA, and SOTA+. Is this correct?

Quote from: kTimesG on Today at 01:27:55 PM

Usually in literature this is actually a Gaudry-Schost variant, because there cannot be a Kangaroo algorithm that actually goes side-ways, since cycles cannot be part of a Kangaroo algorithm, by definition.

This means the 2-3-4 kangaroo algorithm makes 2-3-4 long paths, while Gaudry-Schost variant makes many smaller paths until a distinguished point is found. I see your point, a normal kangaroo method can't go sideways, as the "maximum excursion" would not allow for the kangaroo to travel very far before going in to a loop?

But in general terms:

Mirror is faster than 3 kangaroos because it calculates 2 "cheap" points in every jump instead of 1, and SOTA is faster than mirror because it computes 4 "cheap" points instead of 1?

The trick in SOTA+ is how to detect and then get out of the cycles in a way that the overhead is not to big?

Mirror = takes advantage of group symmetry - you have both P and -P with the same X. If DP is on X and a DP is found, then you basically have two DPs found instead of one. Also this helps with more collisions.

What I'm trying to say, this is just something that's part of the group, it has nothing to do with any 2-kang or 3-kang algorithm itself, it works the same even for a brute-force algorithm (to halve the key space).

The cheap points have nothing to do with mirroring, or with 2-kang, 3-kang. It's simply reusing the (x1 - x2) field inverse to compute both P + Q and P - Q, where P can be anywhere on the curve.

RetiredCoder uses cheap points to selectively pick the next landing point, since somehow this helps - probably because it increases collision chances if visited points have a heavy bias on the lowest bit.