we need 2.sqrt(N) steps to get a collision in a N-space,
we need 2.sqrt(2N) = sqrt(2).2.sqrt(N) steps to get a collision in a 2N-space,
we need 2.sqrt(3N) = sqrt(3).2.sqrt(N) steps to get a collision in a 3N-space.
If we find a way to generate sqrt(3).2.sqrt(N) points faster than 2.sqrt(N), we get a collision in less time, even if we triple our searching space.
If we use the endomorphism, we can triple our interval, from
[1,2,3, ..., n-1,n]
to
[1,2,3,....., n-1,n] + [lambda, 2*lambda, 3*lambda, ....., n*lambda] + [lambda^2, 2*lambda^2, 3*lambda^2, ....., n*lambda^2]
We have 3 types of jumps (always positive): 10 small steps (in first interval) + 10 big steps (in second interval) + 10 bigbig steps (in third interval)
For example:
(1G, 2G, 4G, 8G, 24G, 37G,....., 512G) + (lambda*18G, lambda*72G, ..., lambda*816G) + (lambda^2*41G, lambda^2*10G, ..., lambda^2*653G)
+ 1 jump from range1 to range2 or from range1 to range2: P -> lambda*P
We set the probability to perform a jump between 2 different ranges = 50%, the other 50% is for normal jupms.
For a single step we compute the normal jump +k*G
(3 multiplications for the inverse + 1M + 1S for the x-coordinate + 1M for the y-coordinate = about 6M + some additions)
or a single multiplication: beta*x
You cannot have loops, you have only avoid 3 consecutive steps like: P -> lambda*P -> lambda*(lambda*P) -> lambda*(lambda^2*P = P), in this case you do a normal step P+kG instead of lambda*P.
If we look at a triple of consecutive jumps, we will have:
probability
normal jump + normal jump + normal jump = (1/2)^3
normal jump + normal jump + lambda jump = (1/2)^3 * 3
normal jump + lambda jump + lambda jump = (1/2)^3 * 3
lambda jump + lambda jump + lambda jump= (1/2)^3 but -> loop, it is forbidden
-> it becomes: lambda jump + lambda jump +
On average for each 3 points we need to perform (1/2)^3*18M + (1/2)^3*3*13M + (1/2)^3*3*8M + (1/2)^3*8M = 11.125M, 3.71M for each point.
In this way you perform sqrt(3).2.sqrt(N) steps in the same time you are performing now sqrt(3).2.(3,71/6).sqrt(N)= 2.14*sqrt(N)
If you double the interval:
[1,2,3,....., n-1,n] + [lambda, 2*lambda, 3*lambda, ....., n*lambda]
you perform sqrt(2).2.sqrt(N) steps in the same time you are performing now sqrt(2).2.(4,125/6).sqrt(N)= 1.945*sqrt(N)
