Thanks for the readings
I will try to see if this can be implemented on ECDLP.

OK i will try this.
But if you don't have a translation of -(k2-k1)/2 on the wilds (or (k2-k1)/2 on the tames), you get a worst case when the private key of P is at the end of the range.

I opened a new thread.
https://bitcointalk.org/index.php?topic=5244940.0

I'm not sure to fully understand your idea.
You want to add a condition on the y parity to determine the jump ?
You let the starting positions as they are or you translate them ?

Hello,

I would like to present an interval ECDLP solver based on the Pollard's kangaroo method.
This program is fully open source and available on GitHub: https://github.com/JeanLucPons/Kangaroo
It has GPU support (CUDA Only) and works on both Linux and Windows.
This program is currently under development.

Thanks to test it and to share ideas of improvements here

Yes i have to investigate, I already tested several things without improving things.
Translating tame is like translating wild in the opposite direction.
May be a brownian motion can be interesting (having positive and negative jump).


Probably cache usage.


Edit:
Formula exposed above and for the memory , expected operation*sizeof(hash entry)/2^dp

Thanks
So it seems a bit faster with 32 jumps.
I will make tests to see if affects the average number of operation.

As you compile by yourself, could you try to change

In GPU/GPUEngine.h:24

#define NB_JUMP 64

to

#define NB_JUMP 32

and tell me what is your key rate, thanks

Manu thanks for the test
Bad news for the lower speed . On my low cost GPU it is 10% faster. Will try to understand why ?


I don't think it will change something (at least on single key search). You can may be win memory.

In the above readings, a guy announced a speed slightly lower than 1.77sqrt(n) [1.73qrt(n)] but I must say that it is hard to believe his method can beat the birthday paradox. I didn't enter in details in its analysis and it is done on DLP not ECDLP.
In any case, to beat the birthday paradox, you have to find a way to maximize the probability of natural random collision.

I published a pre-release with the new calculation for expected operation.
I also changed the jump Table size to make it multiple of power of 2 in order to avoid the modulo, this should brings little improvement on GPU.
Thanks to test it
https://github.com/JeanLucPons/Kangaroo/releases/tag/1.4beta

@COBRAS: do not use a Tesla on small range and if you don't know where is the private key (in a range) you have to specify the full range:
0
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140
but in that case, your tesla will end its calculation when the earth will collapse on the sun

Yes the random walk with kangaroo is particular as the path cannot be truncated easily modulo n (n=range size). So the kangaroos can go outside of the range. This is not a problem as the 2 herds travel at the same average speed. The jumpDistane table has an average of sqrt(n) so after sqrt(n) jumps the kangaroos reach the end of the range. The points in the hastable 'older' than ~2.sqrt(n) jumps can be cleared (this is not done, but the collision should happen more or less at the same time).

As we don't know where is the private key, there is a worst case when this key is near the begining or the end of the range.

The worst case correspond to 3sqrt(PI)/2.sqrt(n) and the best case to sqrt(pi).sqrt(n), so the average is 5.sqrt(pi)/4 which give an average time complexity of ~2.21.sqrt(n) (green curve) but the difficulty is to find the complexity according to the number of kangaroo and DP. I found an approximation of the asymptote when nbKangaroo goes to infinity which is ~ cubicroot( nbKangaroo.16.n.2^dp ) (blue curves)
Red curve are experimental points each averaged on 1000 40bits searches with key uniformly distributed in the range.




Edit: A zoom near the average:

Yes I agree to open an other topic, I'm still fighting to get the average running time in function of dp and nbKangaroo, this is quite complex and I got unexpected results but interesting
I'll open the new thread when I ends my statistics.

Yes, do you remenber this ?
We have fighting with a f.ck.ng bug when you have implemented the ModSqr function, i had to add a volatile to prevent gcc to perform optimization !
This volatile is not necessary for gcc > 7.3

I presume the main differences between your ModMul function (if it is still the same you give me) and mine are in:
imm_umul() where I use intrinsic functions and where you have used inline assembly.
On windows it is not possible to do inline assembly, gcc support intrinsic functions so it should generate a good code.
I really don't want to fight with inline assembly on Linux and this horrible AT&T syntax, i did few ones where no intrinsic exists, this was a nightmare...

Hi arulbero

The key you tested are
  ...7F2F1A1DDF3E9FF8 so near the worst case if you run with 8 thread.
or ...BB3EF3883C1866D4 idem

I didn't optimized this program up to the ninja level, I spend time on the Kangaroo one

The test i did was a simple calculation on a classical birthday paradox on 2 tables instead of one. I draw alternatively a random number in [0..N[ in each table and look for collision between the 2 tables. This converges to sqrt(PI.N). sqrt(PI/2.N) on a single table.

Now, I'm doing tests a in real situation, 1024 kangaroos, 10000 40 bit keys informally distributed, for the moment it seems to converge to 2.sqrt(N) + nbKangaroo.2^dp as expected, with dp=7 on 40bit search. In this situation (1024 << sqrt(N) - 2^dp), the approximation using the asymptote is good.


Thanks for the reading.
No I don't think it will be faster

Example for Np=2, you have 2 ranges of w/2 so you perform a total of operation:

2.sqrt(w/2) + 2.sqrt(w/2) = 4/sqrt(2).sqrt(w) which is more than 2.sqrt(w)

I did a test, wanting to know the average time of the birthday paradox when searching collision between 2 tables (like the kangaroo problem).

The kangaroo method is announced to be 2.sqrt(n) but this is for a simple 2 stages algorithm where:
 - you first travel a single tame kangaroo sqrt(n) steps to setup a trap
 - then you make steps with the wild until a collision occurs (it falls in the trap), this second stage is expected to end in sqrt(n) steps.
The factor 2 comes from that. There no need of a hashtable there.


I did a test on 1.000.000 searches (24bits) using a table:

[ 999999] (2^12.825836) (Theoretical 2^12.825748)

It ends in sqrt(PI).sqrt(n) ~= 1.772.sqrt(n)

Note that the precision afer 1.000.000 trials is about 1/sqrt(1.000.000)=0.001 so 3 digits are expected to be good.

2^0.825836 = 1.77256  , sqrt(PI) = 1.77245

I would like first to finalize the calculation of estimated memory and operation (important to tune the dp) and the save/load/merge work.
Then I will implement multiple key. The basic idea for multiple keys is to start wild kangaroos with different keys.

Yes you're right but I have no conversion routine from int256 to double.
And the precision should be enough for the floor function, it is important that the program runs with the good range as it is use for the jump table. I will try to improve things. Still fighting with the memory and operation estimation...

May thanks again for all these tests


This result is for a "3 kangaroos non parallel method". 2 Wilds, one starting at (k2+k1)/2 and one starting at k1 - (k2-k1)/2 and a Tame stating at k1 + 3(k2-k1)/10, 10 divide k2-k1.
Here we have a large number of Tames and Wilds, Tames start between k1 and k2 and wild starts between  k1 - (k2-k1)/2 and  (k2+k1)/2.
I must says that I don't know the exact factor of sqrt(N), I assume it was 2 but it may be a bit less.


Yes, the range is [Start,Stop] , so Start and Stop included, 2^75 + 1 will be rounded to 2^76.
So for 0..8000000000000000000, you should specify 0..7FFFFFFFFFFFFFFFFFF