But for our problem it is not suitable, we have to maximize the chance to get a collision inside an interval.
In a small interval [a*G, ..., b*G] (80 bit) probably you won't find 2 points with the same x or the same y, we don't work in the entire space.
We tried to move [a*G, ..., b*G] to [-(b-a)/2*G, +(b-a)/2*G] because it is precisely the way to have all points with the opposite in the same subgroup. Then for each 'x' we have 2 points for sure.
I think you are missing the point I am making.
You will find a collision if the solution is in one of the additional ranges opened up by the endomorphism.
First what is "our problem"? Finding a that some point Q = kP has a discrete log with respect to some point P in a specific compact range of k -- [0, 2^80]. But why? Instead you can solve a related problem: Find k for Q = kP where k's value is [+/-]1*[0, 2^78]*lambda^[0,2] in less time, even though that 'sparse' range has 1.5x the possible values.
If the reason you are interested in DL is because someone has embedded a puzzle in a [0,2^80] range or something, then the ability to find solutions in the other range isn't interesting.
If, instead, the reason you are interested is because you have a cryptosystem that needs small range DL solving to recover data-- for example decrypting an elgammal encryption or recovering data from a covert nonce side-channel, or from a puzzle-maker that was aware of the endomorphism and used it in their puzle... then it is potentially very interesting.
I think also if the interest is just in DL solving bragging rights or just the intellectual challenge in exploiting all the struture, the endomorphism is also interesting-- for that there isn't a particular problem structure so why not use the one that results in the fastest solver.
In the prime order group essentially all k values are equivalent, which is why you're able to shift the search around to look for that range wherever you want it in the 2^256 interval.
It looks the same if you put 3 times more angaroos at the same range (with G), but for this method you need less jump tables (only one jump table)
You do not need any extra tables to search the additional ranges opened up by the endomorphisms. That's why I pointed out point invariants that hold for all three--- x^3 or (is_even(y)?-1:1)*y. If you do all your lookups using one of these canonicalized forms the table for six of the ranges is the same (and you'd have to check after finding a hit to determine which of the ranges the solution was actually in).
?
