I use a random jump table with a controlled average.
I store as before, no inforamtion on symetry is needed, the key is solved later.
void Kangaroo::CreateJumpTable() {
int jumpBit = rangePower 2;
if(jumpBit > 128) jumpBit = 128;
int maxRetry = 100;
bool ok = false;
double maxAvg = pow(2.0,(double)jumpBit - 0.95);
double minAvg = pow(2.0,(double)jumpBit - 1.05);
double distAvg;
//::printf("Jump Avg distance min: 2^%.2f\n",log2(minAvg));
//::printf("Jump Avg distance max: 2^%.2f\n",log2(maxAvg));
// Kangaroo jumps
// Positive only
while(!ok && maxRetry>0 ) {
Int totalDist;
totalDist.SetInt32(0);
for(int i = 0; i < NB_JUMP; ++i) {
jumpDistance[i].Rand(jumpBit);
if(jumpDistance[i].IsZero())
jumpDistance[i].SetInt32(1);
totalDist.Add(&jumpDistance[i]);
}
distAvg = totalDist.ToDouble() (double)(NB_JUMP);
ok = distAvg>minAvg && distAvg<maxAvg;
maxRetry--;
}
for(int i = 0; i < NB_JUMP; ++i) {
Point J = secp->ComputePublicKey(&jumpDistance[i]);
jumpPointx[i].Set(&J.x);
jumpPointy[i].Set(&J.y);
}
if(!ok) {
::printf("Warning, jump Avg distance out of bounds: 2^%.2f (restart the program)\n",log2(distAvg));
} else {
::printf("Jump Avg distance: 2^%.2f\n",log2(distAvg));
}
}
I simulated many walks with your CreateJumpTable (I did a porting in python).
I found a very interesting thing: finally I know how are these loops!!
I started 2000 walks (not together, I was interested in 'selfcollisions' only) from a position '0', and using only integer numbers I found out that:
almost all cycles have length exactly = 2!I generated 32 positive jumps (and the 32 negative, don't worry, it is like you did but I prefer to write them)
jumpBit = 20
[b]Jump Avg distance[/b]:
minAvg, [b]distAvg[/b], maxAvg
506428.82601934916 [b]530326.5625[/b] 542776.9763909484
[907868, -907868, 716251, -716251, 1007711, -1007711, 720977, -720977, 901512, -901512, 835718, -835718, 363381, -363381, 475363, -475363, 770732, -770732, 217555, -217555, 67168, -67168, 615504, -615504, 584908, -584908, 768134, -768134, 450427, -450427, 926634, -926634, 458021, -458021, 854265, -854265, 589522, -589522, 280841, -280841, 172112, -172112, 32886, -32886, 279644, -279644, 525179, -525179, 200017, -200017, 372430, -372430, 66448, -66448, 905754, -905754, 1000160, -1000160, 331424, -331424, 170629, -170629, 401275, -401275]
and these are the results:
I got 787 (39,35%) collisions (only cycles!!) over 2000 walks (I stopped each walk after 32 steps)
but the most important thing is that I understood why.
783 over 787 has length 2!! Only 2 loops have length 4 and other 2 loops have length 6.
This is logic: what is the chance that a point Q produces a loop of length 2?
Q -> R -> Q The probability is 1/64 (1/(number of effectively different jumps), if the jumps from R and Q is opposite to the jumps from Q and R.
Then when you produce a sequence of points, each point you generate has the probability 1/(number of effectively different jumps)) to create a loop of length 2 with the next point!
Some basic computation:
probability to meet a 1 point that create a loop of length 2 with the next point: 1/NUM_JUMPS
probability to generate 32 (or 2^DP) consecutive points that not produce a 2-loop : (1 - 1/NUM_JUMPS)^32
probability to generate 32 consecutive points with at least one that produces a 2-loop: 1 - (1-NUM_JUMPS)^32
in my case: 1 - (1 - 1/64)^32 =
0.39586 probability of collision in a walk
The bad news is that I had to put a large number of random jump (65536) to avoid cycles and this will decrease GPU performance
I will investigate on choosing these jumps in order to reduce probability of cycle and having the smallest possible jump table.
This explain perfectly why you have to use 65536 jumps instead of 32, because in this way you got:
1 - (1 - 1/65536)^32 =
0.000488The simplest way to avoid to use a large number of jumps and to avoid almost all loops is to modify the condition of the jump, you have to store the last movement (jump):
you have: P -> Q -> R
when you have to decide how to do the next jump (from Q to R), do it normally unless the random jump is the opposite of the previous, in that case instead of doing -k*G do +k*G (in this way you avoid the loop and mantain the symmetry).
EDIT: the probability to have a loop of length 3 is instead very low, because you should have 3 numbers (jump) a,b,c such that a + b + c = 0 and that is not frequent (a,b,c are 3 random numbers between 32(64) generated in a 2^20 space!)
Second test:
20000 walks:
7610 loops of length 2, 101 loops of length 4, 5 loops of length 6, ....
this is the sequence of lenght of each loop:
-> 7610, 0, 101, 0, 5, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 3, 0, 9, 0
38,05 % of walk fall in a 2-loop!
38,66 % of loops in walks limited to 32 steps ...
