But with both signs (+-) or not?
Could you try with an average of 2^21 - 2^22 instead?
u try with an average of 2^21 - 2^22 instead?
Yes at the beginning I used the y sign to select positive or negative jump then I tried an otehr set of random negative jumps without success.
It seems that this "bownian motion" is rather tricky to tune.
Tomorrow, I'll try other things...
Only negative jumps? I would try with positive/negative jumps and
a greater average (my sensation)
To me it looks promising. 1.50sqrt(N) would be amazing!
Another thing to pay attention to is: when we translate our interval, we have only 2^(n-1) x-coordinates, and then half DP. For the tuning it's like we worked in a 2^(n-1) space.
I was thinking another thing,
if you want to overcome/avoid the brownian-motion tuning problem,
go back and put together
1)
the linearity (and therefore the simplicity) of the classic approach (that you used in the release 1.3)
2)
the power of the symmetryExploiting the symmetry means that we use equivalence classes to increase the probability of a collision (same number of tries, half 'points'); in our case, given a point P(x,y), 'x' decides the width of the jump and 'y' only the direction.
In the secp256k1 there are 2 points that share the same 'x', (x,y) and (x,-y).
In a interval of consecutive points, all x-coordinates are different, but if we move the interval like we did it becomes symmetric.
The drawback of our approach is that the kangaroo, instead of going in only one direction, keep going back and forth, creating many loops. Besides, not only we don't know where a wild kangaroo is (obviously we don't know its position-private key), but we don't control even the direction of its motion (and often it comes out from the interval)
But
this curve has another symmetry that respects the linearity (unlike the negative map that overturns the interval and the kangaroo algorithm): endomorphism.
There are 3 points with the same 'y' , that means that this curve has about 2^256 points and
1) 2^256 / 2 different x-coordinates
2) 2^256 / 3 different y-coordinates
Why don't we use the symmetry that mantains the linearity of the interval?
We can work on the y-coordinates, and a jump should be depend on 'y' and not on 'x'.
We set equivalence classes where [P] = {P, Q, R} if and only if yP = yQ = yR
What is the relation between the private key of these points P, Q, R?
If P=k*G, then Q=k*lambda*G and R =k*lambda^2*G (endomorphism)
and P=(x,y) -> Q=(beta*x, y) -> R=(beta^2*x,y)
observation:
if P=k*G, i.e. k is the private key of P respect of the generator G, then
lambda*P = k*lambda*G, i.e. the private key of P'=lambda*P respect of the generator G'=lambda*G is always k.
In other words, if we know that k lies in [a,b], resolving the problem P=k*G is equivalent to resolve the problem P'=k*G'
The interval is the same (from the scalar's point of view) but there are actually 3 different intervals of points. They are all consecutive from a different generator's point of view:
point scalar
[a*G, (a+1)*G, ...., b*G] <-> [a,b] interval 1
[a*G', (a+1)*G', ...., b*G'] <-> [a,b] interval 2 where G'=lambda*G
[a*G'', (a+1)*G'', ...., b*G''] <-> [a,b] interval 3 where G''=lambda*G
We could work on 3 "spaces" simultaneously :
P=k*G, with all points with generator G -> interval 1 jumps (1*G, 2*G, ,,,2^(n-1)*G)
P'=k*G' with all points with generator G' -> interval 2 jumps(lambda*G, lambda*2*G, .... lambda*2^(n-1)*G)
P''=k*G'' with all points with generator G'' -> interval 3 jumps(lambda^2*G, lambda^2*2*G, .... lambda^2*2^(n-1)*G)
if the movements of a kangaroo depends only by the y-coordinates, that means that if a kangaroo reach a point T in the first interval and another kangaroo reachs a point W in the second interval with the same y, we will have a collision!
From that point they will walk together along the same path (across the same equivalence classes) until they reach a DP (in this case a y-coordinate with some zero bits), we detect this collision.
EDIT:
We work in this way in a space of 3*2^n points (3 intervals), but with only 2^n y-coordinates, then we should have a collision with a higher probability. WRONG
