Re: Solving ECDLP with Kangaroos: Part 1 + 2 + RCKangaroo
Can you explain how that is, without having to be a C++ expert? Once you have P - Q you are at a point that is basically the end of a line, how does that help you further (unless maybe you save it and walk further, but this grows your herd size by 2x of course at each step). The cheap point is still one extra semi-addition (sort of), are you sure you're counting it correctly? 
In my tests, as DP grows, K grows as well, but less than double, so overall it's an improvement. But then again, it depends what you are counting.
In my tests, as DP grows, K grows as well, but less than double, so overall it's an improvement. 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.
Here is the code, since it's open-source you can easily compile and check everything by yourself:
Code:
if ((kangs[i].p.x.data[0] & 1) != 0)
{
AddP.y.NegModP();
EcPoint p2 = ec.AddPointsHaveInv(Saved, AddP, inversion);
if ((p2.x.data[0] & 1) == 0)
{
kangs[i].p = p2;
kangs[i].dist = SavedD;
if (!inv)
kangs[i].dist.Sub(EcJumps[jmp_ind].dist);
else
kangs[i].dist.Add(EcJumps[jmp_ind].dist);
}
}
{
AddP.y.NegModP();
EcPoint p2 = ec.AddPointsHaveInv(Saved, AddP, inversion);
if ((p2.x.data[0] & 1) == 0)
{
kangs[i].p = p2;
kangs[i].dist = SavedD;
if (!inv)
kangs[i].dist.Sub(EcJumps[jmp_ind].dist);
else
kangs[i].dist.Add(EcJumps[jmp_ind].dist);
}
}
You can use this trick only for methods that use symmetry.
It works, I know why it works, and I never saw this trick before.