|
Many thanks.
Note that here you have an expected of 2^21 because it take in consideration the overload due dp and the number of kangaroos.
I see that it over estimate a bit.
These results are very interesting to adapt the calculation of expected memory and operations.
To answer a bit in details to HardwareCollector, these calculations are dependent on the range size, the number of kangaroo (so the number of thread, grid size, number of GPU,... ) and dp (number of distinguished point bits) so it is normal that you get different results on different configurations.
The calculation of suggested DP is a poor approximation , it need some works to improve it.
|
|
|
|
Yes, these estimations are trickly to calculate, i will try improve things... Impressive result with the 8 RTX 2080 Ti  |
|
|
|
Thanks for the benchmark  I committed on github. GPU is not yet ready but CPU works (at least for 40bits) R pons@linpons:~/Kangaroo$ ./kangaroo -d 5 VC_CUDA8/in40_1000.txt
It runs in stat mode. If you want to make test. |
|
|
|
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));
}
}
Here is the code of the random walk: void Kangaroo::SolveKeyCPU(TH_PARAM *ph) {
// Global init
int thId = ph->threadId;
counters[thId] = 0;
// Create Kangaroos
KANGAROO *herd = new KANGAROO[CPU_GRP_SIZE];
IntGroup *grp = new IntGroup(CPU_GRP_SIZE);
Int *dx = new Int[CPU_GRP_SIZE];
if(keyIdx==0) {
::printf("SolveKeyCPU Thread %d: %d kangaroos\n",ph->threadId,CPU_GRP_SIZE);
}
ph->hasStarted = true;
// Using Affine coord
Int dy;
Int rx;
Int ry;
Int _s;
Int _p;
uint64_t minW = 0;
uint64_t maxW = 0;
uint64_t minT = 0;
uint64_t maxT = 0;
while(!endOfSearch) {
for(int j = 0; j<CPU_GRP_SIZE; j++)
Create(&herd[j],j%2);
uint64_t cnt = 0;
while(!endOfSearch && cnt<maxStep) {
for(int g = 0; g < CPU_GRP_SIZE; g++) {
uint64_t jmp = herd[g].pos.x.bits64[0] % NB_JUMP;
Int *p1x = &jumpPointx[jmp];
Int *p2x = &herd[g].pos.x;
dx[g].ModSub(p2x,p1x);
}
grp->Set(dx);
grp->ModInv();
for(int g = 0; g < CPU_GRP_SIZE; g++) {
uint64_t jmp = herd[g].pos.x.bits64[0] % NB_JUMP;
Int *p1x = &jumpPointx[jmp];
Int *p1y = &jumpPointy[jmp];
Int *p2x = &herd[g].pos.x;
Int *p2y = &herd[g].pos.y;
dy.ModSub(p2y,p1y);
_s.ModMulK1(&dy,&dx[g]);
_p.ModSquareK1(&_s);
rx.ModSub(&_p,p1x);
rx.ModSub(p2x);
ry.ModSub(p2x,&rx);
ry.ModMulK1(&_s);
ry.ModSub(p2y);
herd[g].distance.ModAddK1order(&jumpDistance[jmp]);
// Equivalence symmetry class switch
if(ry.ModPositiveK1())
herd[g].distance.ModNegK1order();
herd[g].pos.x.Set(&rx);
herd[g].pos.y.Set(&ry);
}
for(int g = 0; g < CPU_GRP_SIZE && !endOfSearch; g++) {
if(IsDP(herd[g].pos.x.bits64[3])) {
LOCK(ghMutex);
if(!endOfSearch) {
if( !AddToTable(&herd[g].pos.x,&herd[g].distance,herd[g].type) ) {
// Collision inside the same herd
// We need to reset the kangaroo
Create(&herd[g],herd[g].type,false);
collisionInSameHerd++;
}
}
UNLOCK(ghMutex);
}
if(!endOfSearch) counters[thId] ++;
cnt++;
}
}
}
// Free
delete grp;
delete dx;
delete[] herd;
ph->isRunning = false;
}
Edit: And kangaroo creation: void Kangaroo::Create(KANGAROO *k,int type,bool lock) {
k->type = type;
if(lock) LOCK(ghMutex);
k->distance.Rand(rangePower - 1);
if(lock) UNLOCK(ghMutex);
if( type == TAME ) {
// Tame in [0..N/2]
k->pos = secp->ComputePublicKey(&k->distance);
} else {
// Wild in [-N/4..N/4]
k->distance.ModSubK1order(&rangeWidthDiv4);
Point O = secp->ComputePublicKey(&k->distance);
k->pos = secp->AddDirect(keyToSearch,O);
}
// Equivalence symmetry class switch
if(k->pos.y.ModPositiveK1())
k->distance.ModNegK1order();
}
|
|
|
|
Hi, Many thanks MrFreeDragon the tests Many thanks to arulbero for helping me solving the issue  I found the bugs, these was 2 ! The jump table size, I already checked that but the combination of the 2 bugs make this hard to find. The split of equivalence class in the random walk. There are only positive jumps in this table. Loop are still possible because of the equivalence class switch "(xP,min{yP,q−yP})". 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. The gain I get by spreading to [-N/8,N/8] was due to the fact that it optimize the overlap between Tame and Wild. If we can compress the Wild to a very small range, we can reach 1.25 sqrt(N) but this a limit and it has dramatic effects on the border and on wild collisions. Using dp 5 (500 trials, Wild in [-N/4 N/4]) [500] 2^17.581 Dead:0 Avg:2^20.608 (2^20.556) => 1.52sqrt(N) Using dp 5 (500 trials, Wild in [-N/8 N/8]) [500] 2^21.693 Dead:103 Avg:2^20.480 (2^20.556) => 1.39sqrt(N) I will now code the GPU and I publish it ASAP |
|
|
|
|
It works with dp=0 because random walk are not really important, they just generate random sequence, and you don't care about the path, so it correctly solve the key (the distance is also stored in the hastable) but with dp>0 paths are of course important.
You're right there is probably a bug with my storage of symmetric point.
|
|
|
|
|
You still exploit the symmetry. Instead of searching between [0,N] you search between [0,N/2] and there is few calculation to make when a collision on a tame.x and wild.x is reached in order to get the good key. I did test and it works as expected.
I think the trick may be that after sqrt(N) total steps the kangaroos starts to overlap each other, still investigating...
|
|
|
|
|
In fact i have removed the negative jump.
There is no need to do complex thing in order to take benefit of symmetry, the main trick is just to translate the public key by -N/2.G and you search a priv key between [0,N/2]. The symmetry is 100% free.
Si I spread my tame between [0,N/2.G] and the wild between [P-N/4.G,P+N/4.G] and it converges to expected average of 1.47sqrt(N) using dp=0.
As I have a large number of kangaroo, each kangaroo does not move a lot. The average distance for sqrt(N/2) steps in (N/2)/numberOfKangaroo.
with dp=0 there is not much bad collisions, no more than expected.
Strangely when using dp > 0, lots of dead kangaroos appear and probably cycle, even with a small number of kangaroo. I have to understand why may be bug somewhere...
|
|
|
|
Hi, I must say I'm a bit lost, they announced an algorithm in 1.36√N and they measured 1.47√N. They say that the complexity is actually (1.36 + epsilon)√N and they estimate this epsilon to ~0.1 without being clear on it. https://www.iacr.org/archive/pkc2010/60560372/60560372.pdfIf we compute the complexity of a symmetric set, we have well : (2(2−√2)PI)/√2 √N = 1.468√N ! So i would rather say that the complexity is (1.47+epsilon)√N with an epsilon which depend on number of kangaroo, dp and N as for the standard version. I'm still fighting with collision, when using dp > 0, it seems that the symmetry generates a lot of wrong collisions. |
|
|
|
|
Yes GPU is not good on 40bit range, this 40bit file is for making stats on CPU.
To make accurate statistics you need to do it on CPU, the granularity of the counting on GPU is too large but I will try to find something in order to make tests on GPU.
Anyway i did a test with dp 3 and it also converge to 2^21 (same algorithm, no change on the range in function of dp).
This is tricky, there is something I need to understand with those random walks...
I have the feeling that this algorithm win in average complexity by favoriting keys on the middle of the range as the density of wild is increased in the center. It has a worse 'worst case' and a much better 'best case' than the classic algorithm.
|
|
|
|
With these data:
N = 2^40
m = 2^11
θ = 2^−5
still 2^21?
I have to try, I let you know... @COBRAS I release the code ASAP |
|
|
|
|
I did a test using dp 0 (much slower):
The algorithm runs in 2^20.554 = ~1.47 sqrt(N) (1000 trials) as announced on the paper so it seems ok but I have to figure out why it is not the case for dp > 0. There is a relationship betwen dp and range size (m√2/3πθ) that I missed.
Will try to undersand, how to choose this m.
|
|
|
|
|
Yes
The above test was done with a stop&retry at 2^21.
I removed it and got 2^21.008 on 500 trials, so very similar.
As it is, it seems to converge to 2.sqrt(N) with a jump table of 16 positive random jumps and 16 negative random jumps.
The number of bad collision is also link to the kangaroo density.
|
|
|
|
Yes, i think this might be due to the average jump size which is too large for wild. I will try other things and what you suggest. I let you informed. Thanks |
|
|
|
|
Good news !
By changing the spreading of wild kangaroo to -N/8 N/8 the it seems to improve things. (using the Steven D. Galbraith?and Raminder S. method).
I got an average of 2^20.997 ~ 2.sqrt(n) on 1000 trials.
|
|
|
|
Many thanks to all of you for your interest I'm sorry but I didn't manage to make the algorithm in the paper working. I always get (at best) similar result than the classic version. I tried to increase the random jump table size up 65536 (32768 positive random jumps and 32768 negative random jumps) but still have lots of collision in same herd (using -d 0, it disable the distinguished point, so all collision and cycle are detected). The size of this table seems to no impact the bad collision number. I will read the ref[8] asap. I tried several averages, sqrt(N) seems the best one. I didn't tried yet to have different average length for Tame and Wild. Try to implement endomorphism optimizations ASAP... @MrFreeDragon You need a large number of tests on key uniformly distributed in the range to get a correct estimation, at least 1000 trials. Did you try with a jump table size of 32 or 64 ? NB_JUMP in GPUEngine.h:24 ? I added the file I use for stats, it contains 1000 40 bits key uniformly distributed. https://github.com/JeanLucPons/Kangaroo/blob/master/VC_CUDA8/in40_1000.txt |
|
|
|
They also showed in practice that the total number of operations was not 1.36sqrt(N), but 1.46-1.49sqrt(N).
Yes this small epsilon of ~0.1 (as they call it) is again a strange thing without lots of explanation. They say that it is an overload due the the "failure of random walks" where again we do not have lots of clear informations, I have to read the reference [8]. Last but not least they make test on a very small number of experiments so the error is large... I have some doubt on few on their calculations too... 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... |
|
|
|
|
Not in this release, I use a random set of jump [32 jumps] with an average of 2^20.
|
|
|
|
Yes From time to time it fails and go out the range. The number of dead kangaroo (collision in same herd) increase. The idea of replaying walk is good, I do like this in my BTCCollider. Here is an output on 30 trials. The final private key is not reconstructed here, you need to add (mod n) start range + N/2 Kangaroo v1.3
Start:62CE27C8FED90758A834C2CB6E3F19BC8A0B5E7D92C0FC0F57004A0000000000
Stop :62CE27C8FED90758A834C2CB6E3F19BC8A0B5E7D92C0FC0F57004AFFFFFFFFFF
Keys :1000
Number of CPU thread: 2
Range width: 2^40
Jump Avg distance: 2^20.00
Number of kangaroos: 2^11.00
Suggested DP: 8
Expected operations: 2^21.15
Expected RAM: 6.5MB
DP size: 5 [0xF800000000000000]
SolveKeyCPU Thread 0: 1024 kangaroos
SolveKeyCPU Thread 1: 1024 kangaroos
Key# 0 S3Pub: 0x03C88A1817454E1B49AEEF4D22DB60CD1FFF0513DECC2AFC52219C28C99CFE36A1
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E3E9F06D632
[ 0] 2^21.709 Dead:4 Avg:2^21.709 (2^21.148)
Key# 1 S3Pub: 0x03CB4F9578029F67C76438379DBA854BB9AE6F8EFB219614404A3B4F9FE8D50DC6
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E3EA329D8F1
[ 1] 2^21.520 Dead:4 Avg:2^21.618 (2^21.148)
Key# 2 S0Pub: 0x021CCEE21580FFDCFB8DD18A21B9931E1A585E6A381F3BFAC8B84FC57152FD706F
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E0D7752C567
[ 2] 2^19.253 Dead:0 Avg:2^21.166 (2^21.148)
Key# 3 S3Pub: 0x027CAEB7E334C27E5881F37317FC16E220D425E11DC3ABB6E1D4FEC8651F9672F7
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8012448821
[ 3] 2^20.289 Dead:1 Avg:2^20.992 (2^21.148)
Key# 4 S3Pub: 0x0266556C83D982677B2BD1BFA996828A1F4F7004E92BBE5AA4B393B46999C3B3B5
Priv: 0x4EF20EBCFE
[ 4] 2^20.205 Dead:0 Avg:2^20.865 (2^21.148)
Key# 5 S0Pub: 0x03A20F2F01ED2C30EEFDDA39369ECA064B42784C1828B64EA07B350A9B1E989264
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E4F6D1E4921
[ 5] 2^21.066 Dead:1 Avg:2^20.901 (2^21.148)
Key# 6 S0Pub: 0x02AC1FC88FB9AFF706E26C61D0B35491BD0F6F515A4307D46E183991C87DF530C3
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E2ED6F15717
[ 6] 2^20.659 Dead:1 Avg:2^20.869 (2^21.148)
Key# 7 S3Pub: 0x03753BFF59D2EA1A5DC79BE76279EF6E4B2714043A8DBB747F0147AF566C8D537A
Priv: 0x636F05D644
[ 7] 2^22.343 Dead:8 Avg:2^21.158 (2^21.148)
Key# 8 S0Pub: 0x03A57000087A7CF565318CDD11F379C329A0DA2A28F3D251EAF6D8B29A7DAC799D
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E410D2DB133
[ 8] 2^19.576 Dead:0 Avg:2^21.047 (2^21.148)
Key# 9 S3Pub: 0x035C394D4E9654206CA0A894FB95D76840BB728673403A41101C02E13A8C2DA78A
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8B56E16E5A
[ 9] 2^20.700 Dead:1 Avg:2^21.016 (2^21.148)
Key#10 S3Pub: 0x02E7C093503548B3E41C4912913FD0601FDCE26BBEE94740812931737B663C90CB
Priv: 0x6F1F0B5EF4
[ 10] 2^21.156 Dead:0 Avg:2^21.029 (2^21.148)
Key#11 S0Pub: 0x03FDFC12CCD11AA5113A12DE3DA7F75A74F57B9D2C9E163A6502C69997373CFA5B
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E3EC4A94243
[ 11] 2^19.762 Dead:1 Avg:2^20.957 (2^21.148)
Key#12 S3Pub: 0x029942527E4DE7EA2DD931C284A71FCD2C6F86988C3BCC343CF25639599D183958
Priv: 0x61625FF76D
[ 12] 2^22.054 Dead:4 Avg:2^21.078 (2^21.148)
Key#13 S3Pub: 0x03EDE29C2AA47726E75B9FF565A97907671BD2255DE2AE9C639F5E57B2ED64B509
Priv: 0x70A6A72B9C
[ 13] 2^22.660 Dead:8 Avg:2^21.270 (2^21.148)
Key#14 S0Pub: 0x0361354FA9C10998E21B18BF911CF85C9CC9CC7314ECFFE2F2FE62DBBAC7528462
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E234F90C389
[ 14] 2^19.719 Dead:1 Avg:2^21.206 (2^21.148)
Key#15 S3Pub: 0x03EE26BFC9AC228D6313797F11C0ED0D57BC2AA2909AA4CB938825EC571685A104
Priv: 0xD513ABE3E
[ 15] 2^21.614 Dead:2 Avg:2^21.235 (2^21.148)
Key#16 S3Pub: 0x023D8A5B0DFDDAF4974CBCA698C11A7CFF77C3432E0A528CDB00B39DFA94F35CE1
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E1875ED6231
[ 16] 2^21.401 Dead:1 Avg:2^21.245 (2^21.148)
Key#17 S3Pub: 0x032BD888A2DD0ED92A1E938F4546565CFD35172D502B36CA51CD3094C68B5A8F99
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8629B915FA
[ 17] 2^20.966 Dead:1 Avg:2^21.231 (2^21.148)
Key#18 S3Pub: 0x02BC1AA451042525998B3EB746F90F33B04CC87D525F0C576AD133FB60BD390635
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E84E933A860
[ 18] 2^22.359 Dead:6 Avg:2^21.318 (2^21.148)
Key#19 S0Pub: 0x02C379FD7FF86C5F5EDA2EA7EC2A17E629A6C5E550CFD1480F942224C96ADB29B4
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E16BAA606C7
[ 19] 2^19.383 Dead:0 Avg:2^21.264 (2^21.148)
Key#20 S0Pub: 0x03BB6EE07839B4652D2E5E542E1D566756908C92A325212BF77C47F986CA49E50C
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E1894FE660B
[ 20] 2^20.533 Dead:0 Avg:2^21.236 (2^21.148)
Key#21 S3Pub: 0x0365D82BF4021C9BDA3F3518368D92E2D5B5B31A74F656DA795F945CF3452B388E
Priv: 0x18C8633EB7
[ 21] 2^20.180 Dead:1 Avg:2^21.202 (2^21.148)
Key#22 S3Pub: 0x02F68338FAB7DFB6B826B0B516671EA9744BF87A9105EEF57CB04B8262C246197C
Priv: 0x54698374C2
[ 22] 2^21.979 Dead:5 Avg:2^21.246 (2^21.148)
Key#23 S3Pub: 0x026B0539B338B11BC3BF89CAB51182D8AA9EFA27C40CAAC90CA30B1184548D7380
Priv: 0x1EC240D56C
[ 23] 2^20.536 Dead:0 Avg:2^21.222 (2^21.148)
Key#24 S3Pub: 0x0296F8ECE1DD51B1B15E6A9D0A2545C8AAC9C4CFA72BBBE1DCD6C03D1D51E21C42
Priv: 0x11274B7F03
[ 24] 2^20.651 Dead:0 Avg:2^21.203 (2^21.148)
Key#25 S3Pub: 0x03D013A7A59A42D1EB6333EFBE1DA208586DD3940BCFB381ADEA98F76C4D26B2B5
Priv: 0x414A6EFD99
[ 25] 2^20.480 Dead:0 Avg:2^21.181 (2^21.148)
Key#26 S0Pub: 0x02D5FEDD123EF2BDCC3FE37C4D79DD1E5B2EC95AD9B2C7452907391A1CCC5EF9C0
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E137A8D7A6F
[ 26] 2^21.945 Dead:7 Avg:2^21.218 (2^21.148)
Key#27 S0Pub: 0x02B227090548A1497FCDCAFB0DB7900851872CF7E0AD2A0B7EC832DAA7BA30637C
Priv: 0xE2511D7A
[ 27] 2^21.535 Dead:1 Avg:2^21.231 (2^21.148)
Key#28 S1Pub: 0x024A4FCE4455879E9CB6806DB6367D7287A28A2C59CF29B156EDF016EDB377BDB4
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E1E87F79995
[ 28] 2^21.683 Dead:2 Avg:2^21.249 (2^21.148)
Key#29 S2Pub: 0x02F81D6B0179834773E92F8FCB23014727E8B78BDD30C605F50BBCC205EEB1C386
Priv: 0x7F0B60C903
[ 29] 2^21.590 Dead:3 Avg:2^21.262 (2^21.148)
Key#30 S2Pub: 0x034848FA03EC2FA52ACAE70BE58720A5621CF90565BBC925D624BFB31CDC1ACB66
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8016BDBA3D
[ 30] 2^19.910 Dead:1 Avg:2^21.233 (2^21.148)
|
|
|
|
I coded the stuff as it is described in the paper using this: T={{a,−a}:a∈[−N/2,N/2]},
W={{n+a,−(n+a)}:a∈[−N/4,N/4]
And a of translation of -N/2.G of the public key to solve in order to have as specified: Each experiment involved choosing uniformly at random−N/2≤n≤N/2 and solving the DLP for Q= [n]P.
It found as expected from time to time the symmetric point. It is slower than the classic version (~2^21.2 on 40bit search) and far from 1.46sqrt(n) But, they are not very clear on the jumps and especially the average distance of the jumps. As the wild are on a shorter range, may be steps have to be different than tame's one (not yet tested). I also didn't coded a stop and retry after a certain number of jump (sqrt(n) ?), i let the algorithm continue outside the range, so it may loose the symmetry... To be continued... |
|
|
|
|
Show Posts
