I opened a new thread.
https://bitcointalksearch.org/topic/pollards-kangaroo-ecdlp-solver-5244940
Topic: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] (Read 3490 times)
May 01, 2020, 12:45:47 AM
April 30, 2020, 02:50:08 PM
Another idea:
do you use the symetrie?
If you shift the range from [a,b] to [-(b-a)/2, (b-a)/2] and you generate tame in this range, for each point you create actually a couple of opposite points in the same interval (same x), in this way you probably should have more collisions.
The tame points starting from the negative part of the interval create a couple of points that move towards the center of the interval, while the tame points starting from the positive part create a couple of points that move towards the extreme of the interval. In this way, each tame walks across the double of the points in the interval (with the same computational cost). Same for the wild ones.
In other words a tame kangaroo and a wild kangaroo collide if they fall in the same position or if they fall in 2 different positions but symetric respect of the center of the interval.
In other words : an interval of this type has only 2**(n-1) different x coordinates.
do you use the symetrie?
If you shift the range from [a,b] to [-(b-a)/2, (b-a)/2] and you generate tame in this range, for each point you create actually a couple of opposite points in the same interval (same x), in this way you probably should have more collisions.
The tame points starting from the negative part of the interval create a couple of points that move towards the center of the interval, while the tame points starting from the positive part create a couple of points that move towards the extreme of the interval. In this way, each tame walks across the double of the points in the interval (with the same computational cost). Same for the wild ones.
In other words a tame kangaroo and a wild kangaroo collide if they fall in the same position or if they fall in 2 different positions but symetric respect of the center of the interval.
In other words : an interval of this type has only 2**(n-1) different x coordinates.
I am not following the logic here. What is missing is, how will the paths converge after both the tame and the wild reach the same x-coordinate, assuming that it is the symmetry point?
Good point!
It is enough to modify slightly the way we generate the next jump:
+ jP[tamePosi.x % n]*G if y > p/2, - jP[tamePosi.x % n]*G is y
(then I will indicate 'y' if y > p/2, '-y' if y < p/2)
in this way when a tame T reaches a point Q = (x,y) and a wild W reaches a point Q' = -Q = (x,-y), this become a collision
The tame and the wild will go on with 2 specular paths:
Q -> Q + k*G -> Q + k*G -r*G -> ... -> DP
(x,y) (x1,-y1) (x2,y2) (x0, y0)
-Q -> -Q -k*G -> -Q - k*G +r*G -> ... -> DP
(x,-y) (x1,y1) (x2, -y2) (x0, -y0)
until they reach 2 symetric DP, for both of which we know the private key.
May be a brownian motion can be interesting (having positive and negative jump).
I have created a sort of "brownian motion", my kangaroos keep jumping back and forth.
April 30, 2020, 02:03:08 PM
@Jean_Luc
Please start a new thread for your Pollard Kangaroo implementation discussion.
Please start a new thread for your Pollard Kangaroo implementation discussion.
April 30, 2020, 01:55:43 PM
Another idea:
do you use the symetrie?
If you shift the range from [a,b] to [-(b-a)/2, (b-a)/2] and you generate tame in this range, for each point you create actually a couple of opposite points in the same interval (same x), in this way you probably should have more collisions.
The tame points starting from the negative part of the interval create a couple of points that move towards the center of the interval, while the tame points starting from the positive part create a couple of points that move towards the extreme of the interval. In this way, each tame walks across the double of the points in the interval (with the same computational cost). Same for the wild ones.
In other words a tame kangaroo and a wild kangaroo collide if they fall in the same position or if they fall in 2 different positions but symetric respect of the center of the interval.
In other words : an interval of this type has only 2**(n-1) different x coordinates.
do you use the symetrie?
If you shift the range from [a,b] to [-(b-a)/2, (b-a)/2] and you generate tame in this range, for each point you create actually a couple of opposite points in the same interval (same x), in this way you probably should have more collisions.
The tame points starting from the negative part of the interval create a couple of points that move towards the center of the interval, while the tame points starting from the positive part create a couple of points that move towards the extreme of the interval. In this way, each tame walks across the double of the points in the interval (with the same computational cost). Same for the wild ones.
In other words a tame kangaroo and a wild kangaroo collide if they fall in the same position or if they fall in 2 different positions but symetric respect of the center of the interval.
In other words : an interval of this type has only 2**(n-1) different x coordinates.
I am not following the logic here. What is missing is, how will the paths converge after both the tame and the wild reach the same x-coordinate, assuming that it is the symmetry point?
April 30, 2020, 11:46:36 AM
Another idea:
do you use the symetrie?
If you shift the range from [a,b] to [-(b-a)/2, (b-a)/2] and you generate tame in this range, for each point you create actually a couple of opposite points in the same interval (same x), in this way you probably should have more collisions.
The tame points starting from the negative part of the interval create a couple of points that move towards the center of the interval, while the tame points starting from the positive part create a couple of points that move towards the extreme of the interval. In this way, each tame walks across the double of the points in the interval (with the same computational cost). Same for the wild ones.
do you use the symetrie?
If you shift the range from [a,b] to [-(b-a)/2, (b-a)/2] and you generate tame in this range, for each point you create actually a couple of opposite points in the same interval (same x), in this way you probably should have more collisions.
The tame points starting from the negative part of the interval create a couple of points that move towards the center of the interval, while the tame points starting from the positive part create a couple of points that move towards the extreme of the interval. In this way, each tame walks across the double of the points in the interval (with the same computational cost). Same for the wild ones.
Yes i have to investigate, I already tested several things without improving things.
Translating tame is like translating wild in the opposite direction.
No. I meant: translate tame and wild. Not only tame. In a interval with 2^n points but only 2^(n-1) coordinates 'x' (instead of 2^n) to increase the probability to have a collision. If you do the same number of steps in a half space (from coordinates x point of view), the chance should be higher. Half number of x coordinates, half DP, same number of steps, more chance.
Like I said before, a tame kangaroo and a wild kangaroo in this scenario collide not only if they fall in the same position but if they fall in 2 different positions (but symetric respect of the center of the interval) as well.
If you instead translate this interval in any other position of the curve, when a tame kangaroo and a wild kangaroo fall in 2 positions symetric respect of the center of the interval, your current algorithm doesn't detect a collision, simply because it can't know (without more computation) the x coordinate of the symetric point (respect of (a+b)/2 * G) of any DP that lies in the hashtable (and a symetric point of a DP generally is not a DP)
May be a brownian motion can be interesting (having positive and negative jump).
My idea goes a little in that direction too, cause the jumps are always positive but the points generated go in both direction, exploiting the symetrie of the curve.
Example:
when a sequence starts from -k*G (negative part):
-k*G, (-k + 2^17)*G, (-k +2^17 + 2^3)*G, .... forth -->
but in this way you have too (for free) the x coordinates of :
+k*G, (+k - 2^17)*G, (+k- 2^17 - 2^3)*G, .... <-- back
the movement is like this:
zero point
(--> <--) extreme: -k*G, k*G
(--> <--) extreme: (-k+2^17)*G, -(-k+2^17)*G
(--> <--) extreme: (-k+2^17+2^3)*G, -(-k+2^17+2^3)*G
when a sequence starts/arrives in the positive part:
k*G, (k + 2^8)*G, (k +2^8 + 2^31)*G, .... forth -->
-k*G, (-k - 2^8)*G, (-k -2^8 - 2^31)*G, .... <-- back
zero point
<-- ( )--> extreme: -k*G, k*G
<--( )--> extreme: -(k+2^8)*G, (k+2^8)*G
<--( )--> extreme: -(k+2^8+2^31)*G, (k+2^8+2^31)*G
April 30, 2020, 11:35:06 AM
Another idea:
do you use the symetrie?
If you shift the range from [a,b] to [-(b-a)/2, (b-a)/2] and you generate tame in this range, for each point you create actually a couple of opposite points in the same interval (same x), in this way you probably should have more collisions.
The tame points starting from the negative part of the interval create a couple of points that move towards the center of the interval, while the tame points starting from the positive part create a couple of points that move towards the extreme of the interval. In this way, each tame walks across the double of the points in the interval (with the same computational cost). Same for the wild ones.
do you use the symetrie?
If you shift the range from [a,b] to [-(b-a)/2, (b-a)/2] and you generate tame in this range, for each point you create actually a couple of opposite points in the same interval (same x), in this way you probably should have more collisions.
The tame points starting from the negative part of the interval create a couple of points that move towards the center of the interval, while the tame points starting from the positive part create a couple of points that move towards the extreme of the interval. In this way, each tame walks across the double of the points in the interval (with the same computational cost). Same for the wild ones.
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).
Why it was faster with 32 jumps for him? Do you have the exaplanation?
Probably cache usage.
Also nice things you added:
Expected operations: 2^37.15
Expected RAM: 1419.0MB
Expected operations: 2^37.15
Expected RAM: 1419.0MB
Edit:
Formula exposed above and for the memory , expected operation*sizeof(hash entry)/2^dp
April 30, 2020, 11:08:59 AM
Another idea:
do you use the symetrie?
If you shift the range from [a,b] to [-(b-a)/2, (b-a)/2] and you generate tame in this range, for each point you create actually a couple of opposite points in the same interval (same x), in this way you probably should have more collisions.
The tame points starting from the negative part of the interval create a couple of points that move towards the center of the interval, while the tame points starting from the positive part create a couple of points that move towards the extreme of the interval. In this way, each tame walks across the double of the points in the interval (with the same computational cost). Same for the wild ones.
In other words a tame kangaroo and a wild kangaroo collide if they fall in the same position or if they fall in 2 different positions but symetric respect of the center of the interval.
In other words : an interval of this type has only 2**(n-1) different x coordinates.
do you use the symetrie?
If you shift the range from [a,b] to [-(b-a)/2, (b-a)/2] and you generate tame in this range, for each point you create actually a couple of opposite points in the same interval (same x), in this way you probably should have more collisions.
The tame points starting from the negative part of the interval create a couple of points that move towards the center of the interval, while the tame points starting from the positive part create a couple of points that move towards the extreme of the interval. In this way, each tame walks across the double of the points in the interval (with the same computational cost). Same for the wild ones.
In other words a tame kangaroo and a wild kangaroo collide if they fall in the same position or if they fall in 2 different positions but symetric respect of the center of the interval.
In other words : an interval of this type has only 2**(n-1) different x coordinates.
April 30, 2020, 10:23:13 AM
Thanks
So it seems a bit faster with 32 jumps.
I will make tests to see if affects the average number of operation.
So it seems a bit faster with 32 jumps.
I will make tests to see if affects the average number of operation.
Why it was faster with 32 jumps for him? Do you have the exaplanation?
Also nice things you added:
Expected operations: 2^37.15
Expected RAM: 1419.0MB
What is the current formula you use for Expected operations?
April 30, 2020, 10:14:33 AM
Thanks
So it seems a bit faster with 32 jumps.
I will make tests to see if affects the average number of operation.
So it seems a bit faster with 32 jumps.
I will make tests to see if affects the average number of operation.
April 30, 2020, 09:49:48 AM
While using your 72-bit test range on an RTX 2070, out of the box, v1.4beta appears to be slightly slower than v1.3 in terms of group operations per second 770M vs 848M for v1.3. But the average time to solve the 20 ECDLPs was about the same, 1h:23m vs 1h:13m for v1.4beta vs v1.3 respectively
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
With the above recommended changes to v1.4beta:
Code:
./kangaroo -t 0 -d 13 -gpu -gpuId 0 in72.txt
Kangaroo v1.4beta
Start:59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1000000000000000000
Stop :59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1FFFFFFFFFFFFFFFFFF
Keys :20
Number of CPU thread: 0
Range width: 2^72
Jump Avg distance: 2^36.03
Number of kangaroos: 2^20.17
Suggested DP: 14
Expected operations: 2^37.15
Expected RAM: 1419.0MB
DP size: 13 [0xfff8000000000000]
GPU: GPU #0 GeForce RTX 2070 (36x64 cores) Grid(72x128) (117.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.17 kangaroos in 9840.1ms
[860.47 MK/s][GPU 860.47 MK/s][Count 2^37.23][Dead 1][03:32 (Avg 02:56)][1501.4MB]
Key# 0 Pub: 0x038F63B86D8EE91D4B78FF4680F927DCC7754CF734A386ED5FA45E71DE9328F433
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D102F962838A4EE7364E
v1.3 stock with 13-bit distinguished point mask:
Code:
./kangaroo -t 0 -d 13 -gpu -gpuId 0 in72.txt
Kangaroo v1.3
Start:59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1000000000000000000
Stop :59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1FFFFFFFFFFFFFFFFFF
Keys :20
Number of CPU thread: 0
Range width: 2^72
Number of kangaroos: 2^20.17
Suggested DP: 14
Expected operations: 2^37.10
Expected RAM: 1371.0MB
DP size: 13 [0xfff8000000000000]
GPU: GPU #0 GeForce RTX 2070 (36x64 cores) Grid(72x128) (117.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.17 kangaroos in 9829.6ms
[841.66 MK/s][GPU 841.66 MK/s][Count 2^36.81][Dead 0][02:42 (Avg 02:54)][1124.8MB]
Key# 0 Pub: 0x038F63B86D8EE91D4B78FF4680F927DCC7754CF734A386ED5FA45E71DE9328F433
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D102F962838A4EE7364E
[847.09 MK/s][GPU 847.09 MK/s][Count 2^34.48][Dead 0][42s (Avg 02:53)][227.8MB]
Key# 1 Pub: 0x0389044AFFFD381B496D63F8C80CDAAB5E57E40DEE6A56C8AFA5194B1FFD83FEBB
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1F5821BA583622EEE49
[845.55 MK/s][GPU 845.55 MK/s][Count 2^37.67][Dead 2][05:06 (Avg 02:53)][2047.7MB]
Key# 2 Pub: 0x0338E88602F88C3268C68552C4C53987F41BB42335A8E36658A80D2F5BDF63615B
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D110DC466D7E3D293A10
[845.64 MK/s][GPU 845.64 MK/s][Count 2^37.75][Dead 2][05:22 (Avg 02:53)][2159.2MB]
Key# 3 Pub: 0x026776529C6C8932ABF9DCFDCB2DB2784DCE82164914D4C3294FECFE1B48F3BF27
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1DE55BDE3E1B2F36A9B
[842.89 MK/s][GPU 842.89 MK/s][Count 2^36.66][Dead 1][02:36 (Avg 02:54)][1015.0MB]
Key# 4 Pub: 0x03312940E0EE296C23B1E7888A4D23FED01358C1021FE2091D909B0A8D8AA80DE1
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D11B78CA8A9FBCDBDE3E
[845.68 MK/s][GPU 845.68 MK/s][Count 2^37.23][Dead 3][03:48 (Avg 02:53)][1511.0MB]
Key# 5 Pub: 0x020097A3826A7BC1EC5383AE390EEA8C436B2B6D2E3770493F7E993B164C9F233E
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D152477D7EC473A483D4
[840.32 MK/s][GPU 840.32 MK/s][Count 2^36.82][Dead 1][02:54 (Avg 02:55)][1136.9MB]
Key# 6 Pub: 0x03DAE902F3F4E0A62AA7DF422B2BF802CD9ADA747177F853390BEB7F203E4C3F84
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D10D2AB0CDE883E6B3BC
[844.38 MK/s][GPU 844.38 MK/s][Count 2^37.31][Dead 2][04:00 (Avg 02:54)][1593.2MB]
Key# 7 Pub: 0x023C4E51FD6EB029CFD4DDCBD93FAD060C7D026D252EC37923355D1B192C69B9E3
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1B69F2EC54CEEBA50C4
[844.25 MK/s][GPU 844.25 MK/s][Count 2^36.53][Dead 0][02:24 (Avg 02:54)][930.5MB]
Key# 8 Pub: 0x03C3112770BC8455596AF38A2A2E3F556B1F02758945608364C3AFD22FAD806B8D
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D18D06BC6E25E5C7EAEF
[842.89 MK/s][GPU 842.89 MK/s][Count 2^37.37][Dead 3][04:10 (Avg 02:54)][1663.0MB]
Key# 9 Pub: 0x0264AE637A90AA93798E7BA6CCFD57CB077BCCAE49D3AB76F6857CA044A423E3AC
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1C8A4760400224E8C05
[845.50 MK/s][GPU 845.50 MK/s][Count 2^36.55][Dead 0][02:26 (Avg 02:53)][945.1MB]
Key#10 Pub: 0x0359A0CFB0958A2B6FC562B3824D0BE034C7E947780DAF4B8AF403C72D92496BEF
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D197AD08D8E14C058778
[844.35 MK/s][GPU 844.35 MK/s][Count 2^37.88][Dead 2][05:53 (Avg 02:54)][2365.1MB]
Key#11 Pub: 0x020B58A06DC49B931A8B9C08E29306B70FBB56F4F3B8BAB7AEBD409B4DC8086C78
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1C831BC0E9C1450CCCE
[840.41 MK/s][GPU 840.41 MK/s][Count 2^36.25][Dead 1][02:00 (Avg 02:55)][765.7MB]
Key#12 Pub: 0x039E8FE48D08C5465128681D49AE9026240BC612C9BC8A3B6E9D2FA00DBC9021AF
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D17941FCB9F89FAA2C79
[844.44 MK/s][GPU 844.44 MK/s][Count 2^36.02][Dead 0][01:44 (Avg 02:54)][655.9MB]
Key#13 Pub: 0x02131119C5618C26AB5C8DE1B16E60120C918AAC717B06A10ADBCC4BCF44106419
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D166208474EA5CD1D0D9
[845.74 MK/s][GPU 845.74 MK/s][Count 2^34.68][Dead 0][48s (Avg 02:53)][261.3MB]
Key#14 Pub: 0x02487FE068AFA2AAFC96EC2941EC8CF4E2600692F8D4F6E4A389AFEA44221E045D
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1AD9E1D5075941AB176
[818.45 MK/s][GPU 818.45 MK/s][Count 2^33.45][Dead 0][26s (Avg 02:59)][114.5MB]
Key#15 Pub: 0x034B202C91CF7AA1563048AFCED10781666C8344E0A23884977F5F3396E3CDFBFE
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D166550C0FED3225AE1D
[841.62 MK/s][GPU 841.62 MK/s][Count 2^36.33][Dead 1][02:06 (Avg 02:54)][807.3MB]
Key#16 Pub: 0x023510C7370A558126EF057C738A4943021E5FB08B41799AE097190DFC5538DB69
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D16DA62AB9D45017CFF3
[841.51 MK/s][GPU 841.51 MK/s][Count 2^36.22][Dead 0][01:58 (Avg 02:54)][752.1MB]
Key#17 Pub: 0x0336CE6F79E48B6493CF2BC2DE87BFE9504D30CD62B9B5F992E1A5933D69076A76
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1A7F3A8F6001FFF3E8C
[848.25 MK/s][GPU 848.25 MK/s][Count 2^35.73][Dead 0][01:28 (Avg 02:53)][536.4MB]
Key#18 Pub: 0x03292ACD7402F076829CF4DC40B659D24ACCF67F2884DF4CD111847C651F18512A
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1DF6AE20D48B230C23C
[845.62 MK/s][GPU 845.62 MK/s][Count 2^37.06][Dead 0][03:24 (Avg 02:53)][1339.9MB]
Key#19 Pub: 0x036C4AF425D93153FD0593787399A78322699F498C4703E2D1524C15F0137C2D14
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D13B97B84AC3FBEDF0AF
Done: Total time 58:02
April 30, 2020, 08:53:09 AM
While using your 72-bit test range on an RTX 2070, out of the box, v1.4beta appears to be slightly slower than v1.3 in terms of group operations per second 770M vs 848M for v1.3. But the average time to solve the 20 ECDLPs was about the same, 1h:23m vs 1h:13m for v1.4beta vs v1.3 respectively
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
April 30, 2020, 08:01:41 AM
While using your 72-bit test range on an RTX 2070, out of the box, v1.4beta appears to be slightly slower than v1.3 in terms of group operations per second 770M vs 848M for v1.3. But the average time to solve the 20 ECDLPs was about the same, 1h:23m vs 1h:13m for v1.4beta vs v1.3 respectively
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 think that it would be faster if you used a hashtable with precomputed distinguished points (the tame points).
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.
April 30, 2020, 07:27:30 AM
I think that it would be faster if you used a hashtable with precomputed distinguished points (the tame points).
The speed should double.
Yes, it should be significantly faster when solving for multiple instances, since there’s no need to discard the previous distinguished points.
April 30, 2020, 07:16:22 AM
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.
Ok.
I think that it would be faster if you used a hashtable with precomputed distinguished points (the tame points).
The speed should double.
April 30, 2020, 07:14:11 AM
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
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
While using your 72-bit test range on an RTX 2070, out of the box, v1.4beta appears to be slightly slower than v1.3 in terms of group operations per second 770M vs 848M for v1.3. But the average time to solve the 20 ECDLPs was about the same, 1h:23m vs 1h:13m for v1.4beta vs v1.3 respectively
Code:
./kangaroo -t 0 -gpu -gpuId 0 in72.txt
Kangaroo v1.4beta
Start:59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1000000000000000000
Stop :59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1FFFFFFFFFFFFFFFFFF
Keys :20
Number of CPU thread: 0
Range width: 2^72
Jump Avg distance: 2^35.99
Number of kangaroos: 2^20.17
Suggested DP: 14
Expected operations: 2^37.15
Expected RAM: 710.0MB
DP size: 14 [0xfffc000000000000]
GPU: GPU #0 GeForce RTX 2070 (36x64 cores) Grid(72x128) (117.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.17 kangaroos in 9830.1ms
[774.39 MK/s][GPU 774.39 MK/s][Count 2^37.74][Dead 4][05:38 (Avg 03:16)][1075.0MB]
Key# 0 Pub: 0x038F63B86D8EE91D4B78FF4680F927DCC7754CF734A386ED5FA45E71DE9328F433
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D102F962838A4EE7364E
[771.71 MK/s][GPU 771.71 MK/s][Count 2^37.96][Dead 6][06:45 (Avg 03:17)][1247.3MB]
Key# 1 Pub: 0x0389044AFFFD381B496D63F8C80CDAAB5E57E40DEE6A56C8AFA5194B1FFD83FEBB
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1F5821BA583622EEE49
[770.30 MK/s][GPU 770.30 MK/s][Count 2^38.38][Dead 6][08:59 (Avg 03:17)][1668.1MB]
Key# 2 Pub: 0x0338E88602F88C3268C68552C4C53987F41BB42335A8E36658A80D2F5BDF63615B
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D110DC466D7E3D293A10
[771.83 MK/s][GPU 771.83 MK/s][Count 2^35.79][Dead 0][01:38 (Avg 03:17)][282.8MB]
Key# 3 Pub: 0x026776529C6C8932ABF9DCFDCB2DB2784DCE82164914D4C3294FECFE1B48F3BF27
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1DE55BDE3E1B2F36A9B
[771.87 MK/s][GPU 771.87 MK/s][Count 2^36.66][Dead 0][02:50 (Avg 03:17)][509.0MB]
Key# 4 Pub: 0x03312940E0EE296C23B1E7888A4D23FED01358C1021FE2091D909B0A8D8AA80DE1
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D11B78CA8A9FBCDBDE3E
[773.06 MK/s][GPU 773.06 MK/s][Count 2^38.09][Dead 5][07:23 (Avg 03:16)][1364.0MB]
Key# 5 Pub: 0x020097A3826A7BC1EC5383AE390EEA8C436B2B6D2E3770493F7E993B164C9F233E
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D152477D7EC473A483D4
[771.82 MK/s][GPU 771.82 MK/s][Count 2^36.64][Dead 0][02:48 (Avg 03:17)][503.6MB]
Key# 6 Pub: 0x03DAE902F3F4E0A62AA7DF422B2BF802CD9ADA747177F853390BEB7F203E4C3F84
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D10D2AB0CDE883E6B3BC
[770.32 MK/s][GPU 770.32 MK/s][Count 2^37.73][Dead 1][05:48 (Avg 03:17)][1068.4MB]
Key# 7 Pub: 0x023C4E51FD6EB029CFD4DDCBD93FAD060C7D026D252EC37923355D1B192C69B9E3
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1B69F2EC54CEEBA50C4
[770.25 MK/s][GPU 770.25 MK/s][Count 2^37.02][Dead 1][03:36 (Avg 03:17)][655.0MB]
Key# 8 Pub: 0x03C3112770BC8455596AF38A2A2E3F556B1F02758945608364C3AFD22FAD806B8D
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D18D06BC6E25E5C7EAEF
[771.48 MK/s][GPU 771.48 MK/s][Count 2^37.83][Dead 3][06:13 (Avg 03:17)][1142.8MB]
Key# 9 Pub: 0x0264AE637A90AA93798E7BA6CCFD57CB077BCCAE49D3AB76F6857CA044A423E3AC
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1C8A4760400224E8C05
[773.00 MK/s][GPU 773.00 MK/s][Count 2^36.19][Dead 0][02:06 (Avg 03:16)][371.4MB]
Key#10 Pub: 0x0359A0CFB0958A2B6FC562B3824D0BE034C7E947780DAF4B8AF403C72D92496BEF
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D197AD08D8E14C058778
[773.00 MK/s][GPU 773.00 MK/s][Count 2^36.56][Dead 0][02:40 (Avg 03:16)][477.0MB]
Key#11 Pub: 0x020B58A06DC49B931A8B9C08E29306B70FBB56F4F3B8BAB7AEBD409B4DC8086C78
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1C831BC0E9C1450CCCE
[770.41 MK/s][GPU 770.41 MK/s][Count 2^37.58][Dead 2][05:14 (Avg 03:17)][959.8MB]
Key#12 Pub: 0x039E8FE48D08C5465128681D49AE9026240BC612C9BC8A3B6E9D2FA00DBC9021AF
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D17941FCB9F89FAA2C79
[772.81 MK/s][GPU 772.81 MK/s][Count 2^35.69][Dead 0][01:32 (Avg 03:17)][264.3MB]
Key#13 Pub: 0x02131119C5618C26AB5C8DE1B16E60120C918AAC717B06A10ADBCC4BCF44106419
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D166208474EA5CD1D0D9
[773.03 MK/s][GPU 773.03 MK/s][Count 2^35.86][Dead 2][01:42 (Avg 03:16)][295.4MB]
Key#14 Pub: 0x02487FE068AFA2AAFC96EC2941EC8CF4E2600692F8D4F6E4A389AFEA44221E045D
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1AD9E1D5075941AB176
[773.02 MK/s][GPU 773.02 MK/s][Count 2^36.52][Dead 0][02:36 (Avg 03:16)][464.7MB]
Key#15 Pub: 0x034B202C91CF7AA1563048AFCED10781666C8344E0A23884977F5F3396E3CDFBFE
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D166550C0FED3225AE1D
[766.48 MK/s][GPU 766.48 MK/s][Count 2^37.31][Dead 1][04:22 (Avg 03:18)][797.9MB]
Key#16 Pub: 0x023510C7370A558126EF057C738A4943021E5FB08B41799AE097190DFC5538DB69
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D16DA62AB9D45017CFF3
[773.05 MK/s][GPU 773.05 MK/s][Count 2^36.15][Dead 0][02:04 (Avg 03:16)][360.8MB]
Key#17 Pub: 0x0336CE6F79E48B6493CF2BC2DE87BFE9504D30CD62B9B5F992E1A5933D69076A76
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1A7F3A8F6001FFF3E8C
[770.36 MK/s][GPU 770.36 MK/s][Count 2^37.85][Dead 1][06:17 (Avg 03:17)][1157.1MB]
Key#18 Pub: 0x03292ACD7402F076829CF4DC40B659D24ACCF67F2884DF4CD111847C651F18512A
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1DF6AE20D48B230C23C
[771.87 MK/s][GPU 771.87 MK/s][Count 2^35.92][Dead 1][01:46 (Avg 03:17)][307.8MB]
Key#19 Pub: 0x036C4AF425D93153FD0593787399A78322699F498C4703E2D1524C15F0137C2D14
Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D13B97B84AC3FBEDF0AF
Done: Total time 01:23:26
April 30, 2020, 06:29:15 AM
Video with lincks for reading:
"Pollard-Kangaroo GPU CUDA & Quadratic sieve"
https://youtu.be/kMevZQc7774
"Pollard-Kangaroo GPU CUDA & Quadratic sieve"
https://youtu.be/kMevZQc7774
April 30, 2020, 04:29:30 AM
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
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
April 30, 2020, 04:06:37 AM
This is examples from my today tests:
plazmosis.exe - is a renamed kangaroo.exe
plazmosis.exe - is a renamed kangaroo.exe
Quote
The system cannot find the path specified.
C:\Plasmosis>plazmosisdna.exe -t 0 -d 15 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
Keys :13
Number of CPU thread: 0
Range width: 2^160
Number of random walk: 2^20.58 (Max DP=57)
DP size: 15 [0xFFFE000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 10919.1ms
[459.75 MKey/s][GPU 459.75 MKey/s][Count 2^33.49][Dead 0][30s][34.2MB] ^C
C:\Plasmosis>plazmosisdna.exe -t 0 -d 15 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^160
Number of random walk: 2^20.58 (Max DP=57)
DP size: 15 [0xFFFE000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
^C
C:\Plasmosis>
C:\Plasmosis>plazmosisdna.exe -t 0 -d 15 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFFFFFFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^80
Number of random walk: 2^20.58 (Max DP=17)
DP size: 15 [0xFFFE000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
^C
C:\Plasmosis>plazmosisdna.exe -t 0 -d 7 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFFFFFFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^80
Number of random walk: 2^20.58 (Max DP=17)
DP size: 7 [0xFE00000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 7390.7ms
Warning, 66588 items lost
Hint: Search with less threads (-g)
[135.88 MKey/s][GPU 135.88 MKey/s][Count 2^32.10][Dead 0][32s][1832.9MB] ^C
C:\Plasmosis>plazmosisdna.exe -t 0 -d 7 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^52
Number of random walk: 2^20.58 (Max DP=3)
Warning, DP is too large, it may cause significant overload.
Hint: decrease number of threads, gridSize, or decrese dp using -d.
DP size: 7 [0xFE00000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 6336.7ms
Warning, 65695 items lost
Hint: Search with less threads (-g)
[135.05 MKey/s][GPU 135.05 MKey/s][Count 2^31.65][Dead 507][25s][1335.4MB] ^C
C:\Plasmosis>plazmosisdna.exe -t 0 -d 7 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^52
Number of random walk: 2^20.58 (Max DP=3)
Warning, DP is too large, it may cause significant overload.
Hint: decrease number of threads, gridSize, or decrese dp using -d.
DP size: 7 [0xFE00000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 6149.4ms
Warning, 65678 items lost
Hint: Search with less threads (-g)
[332.32 MKey/s][GPU 332.32 MKey/s][Count 2^29.98][Dead 27][04s][417.1MB] ^C
C:\Plasmosis>plazmosisdna.exe -t 0 -d 7 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^52
Number of random walk: 2^20.58 (Max DP=3)
Warning, DP is too large, it may cause significant overload.
Hint: decrease number of threads, gridSize, or decrese dp using -d.
DP size: 7 [0xFE00000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 6128.5ms
Warning, 65678 items lost
Hint: Search with less threads (-g)
[251.78 MKey/s][GPU 251.78 MKey/s][Count 2^30.71][Dead 98][10s][704.4MB] ^C
C:\Plasmosis>plazmosisdna.exe -t 0 -d 15 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^52
Number of random walk: 2^20.58 (Max DP=3)
Warning, DP is too large, it may cause significant overload.
Hint: decrease number of threads, gridSize, or decrese dp using -d.
DP size: 15 [0xFFFE000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 6148.2ms
[460.02 MKey/s][GPU 460.02 MKey/s][Count 2^33.81][Dead 1050][37s][40.6MB] ^C
C:\Plasmosis>
C:\Plasmosis>plazmosisdna.exe -t 0 -d 15 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^60
Number of random walk: 2^20.58 (Max DP=7)
Warning, DP is too large, it may cause significant overload.
Hint: decrease number of threads, gridSize, or decrese dp using -d.
DP size: 15 [0xFFFE000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 6501.1ms
[459.77 MKey/s][GPU 459.77 MKey/s][Count 2^34.30][Dead 11][52s][53.5MB] ^C
C:\Plasmosis>
C:\Plasmosis>plazmosisdna.exe -t 0 -d 15 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFFFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^68
Number of random walk: 2^20.58 (Max DP=11)
Warning, DP is too large, it may cause significant overload.
Hint: decrease number of threads, gridSize, or decrese dp using -d.
DP size: 15 [0xFFFE000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 7050.7ms
[459.78 MKey/s][GPU 459.78 MKey/s][Count 2^38.50][Dead 81][16:02][907.6MB] ^C
C:\Plasmosis>plazmosisdna.exe -t 0 -d 7 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFFFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^68
Number of random walk: 2^20.58 (Max DP=11)
DP size: 7 [0xFE00000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 6794.7ms
Warning, 65975 items lost
Hint: Search with less threads (-g)
[268.25 MKey/s][GPU 268.25 MKey/s][Count 2^30.81][Dead 0][10s][749.8MB] ^C
C:\Plasmosis>plazmosisdna.exe -t 0 -d 9 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFFFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^68
Number of random walk: 2^20.58 (Max DP=11)
DP size: 9 [0xFF80000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 6872.2ms
[183.93 MKey/s][GPU 183.93 MKey/s][Count 2^35.38][Dead 0][03:25][6682.8MB] ^C
C:\Plasmosis>plazmosisdna.exe -t 0 -d 7 -gpu -g 128,256 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFFFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^68
Number of random walk: 2^22.00 (Max DP=10)
DP size: 7 [0xFE00000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(128x256) (393.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^22.00 kangaroos in 17993.3ms
Warning, 393221 items lost
Hint: Search with less threads (-g)
[11.02 MKey/s][GPU 11.02 MKey/s][Count 2^36.33][Dead 0][22:28][12887.4MB]
C:\Plasmosis>plazmosisdna.exe -t 0 -d 15 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
Keys :13
Number of CPU thread: 0
Range width: 2^160
Number of random walk: 2^20.58 (Max DP=57)
DP size: 15 [0xFFFE000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 10919.1ms
[459.75 MKey/s][GPU 459.75 MKey/s][Count 2^33.49][Dead 0][30s][34.2MB] ^C
C:\Plasmosis>plazmosisdna.exe -t 0 -d 15 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^160
Number of random walk: 2^20.58 (Max DP=57)
DP size: 15 [0xFFFE000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
^C
C:\Plasmosis>
C:\Plasmosis>plazmosisdna.exe -t 0 -d 15 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFFFFFFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^80
Number of random walk: 2^20.58 (Max DP=17)
DP size: 15 [0xFFFE000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
^C
C:\Plasmosis>plazmosisdna.exe -t 0 -d 7 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFFFFFFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^80
Number of random walk: 2^20.58 (Max DP=17)
DP size: 7 [0xFE00000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 7390.7ms
Warning, 66588 items lost
Hint: Search with less threads (-g)
[135.88 MKey/s][GPU 135.88 MKey/s][Count 2^32.10][Dead 0][32s][1832.9MB] ^C
C:\Plasmosis>plazmosisdna.exe -t 0 -d 7 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^52
Number of random walk: 2^20.58 (Max DP=3)
Warning, DP is too large, it may cause significant overload.
Hint: decrease number of threads, gridSize, or decrese dp using -d.
DP size: 7 [0xFE00000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 6336.7ms
Warning, 65695 items lost
Hint: Search with less threads (-g)
[135.05 MKey/s][GPU 135.05 MKey/s][Count 2^31.65][Dead 507][25s][1335.4MB] ^C
C:\Plasmosis>plazmosisdna.exe -t 0 -d 7 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^52
Number of random walk: 2^20.58 (Max DP=3)
Warning, DP is too large, it may cause significant overload.
Hint: decrease number of threads, gridSize, or decrese dp using -d.
DP size: 7 [0xFE00000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 6149.4ms
Warning, 65678 items lost
Hint: Search with less threads (-g)
[332.32 MKey/s][GPU 332.32 MKey/s][Count 2^29.98][Dead 27][04s][417.1MB] ^C
C:\Plasmosis>plazmosisdna.exe -t 0 -d 7 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^52
Number of random walk: 2^20.58 (Max DP=3)
Warning, DP is too large, it may cause significant overload.
Hint: decrease number of threads, gridSize, or decrese dp using -d.
DP size: 7 [0xFE00000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 6128.5ms
Warning, 65678 items lost
Hint: Search with less threads (-g)
[251.78 MKey/s][GPU 251.78 MKey/s][Count 2^30.71][Dead 98][10s][704.4MB] ^C
C:\Plasmosis>plazmosisdna.exe -t 0 -d 15 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^52
Number of random walk: 2^20.58 (Max DP=3)
Warning, DP is too large, it may cause significant overload.
Hint: decrease number of threads, gridSize, or decrese dp using -d.
DP size: 15 [0xFFFE000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 6148.2ms
[460.02 MKey/s][GPU 460.02 MKey/s][Count 2^33.81][Dead 1050][37s][40.6MB] ^C
C:\Plasmosis>
C:\Plasmosis>plazmosisdna.exe -t 0 -d 15 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^60
Number of random walk: 2^20.58 (Max DP=7)
Warning, DP is too large, it may cause significant overload.
Hint: decrease number of threads, gridSize, or decrese dp using -d.
DP size: 15 [0xFFFE000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 6501.1ms
[459.77 MKey/s][GPU 459.77 MKey/s][Count 2^34.30][Dead 11][52s][53.5MB] ^C
C:\Plasmosis>
C:\Plasmosis>plazmosisdna.exe -t 0 -d 15 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFFFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^68
Number of random walk: 2^20.58 (Max DP=11)
Warning, DP is too large, it may cause significant overload.
Hint: decrease number of threads, gridSize, or decrese dp using -d.
DP size: 15 [0xFFFE000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 7050.7ms
[459.78 MKey/s][GPU 459.78 MKey/s][Count 2^38.50][Dead 81][16:02][907.6MB] ^C
C:\Plasmosis>plazmosisdna.exe -t 0 -d 7 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFFFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^68
Number of random walk: 2^20.58 (Max DP=11)
DP size: 7 [0xFE00000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 6794.7ms
Warning, 65975 items lost
Hint: Search with less threads (-g)
[268.25 MKey/s][GPU 268.25 MKey/s][Count 2^30.81][Dead 0][10s][749.8MB] ^C
C:\Plasmosis>plazmosisdna.exe -t 0 -d 9 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFFFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^68
Number of random walk: 2^20.58 (Max DP=11)
DP size: 9 [0xFF80000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 6872.2ms
[183.93 MKey/s][GPU 183.93 MKey/s][Count 2^35.38][Dead 0][03:25][6682.8MB] ^C
C:\Plasmosis>plazmosisdna.exe -t 0 -d 7 -gpu -g 128,256 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFFFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^68
Number of random walk: 2^22.00 (Max DP=10)
DP size: 7 [0xFE00000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(128x256) (393.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^22.00 kangaroos in 17993.3ms
Warning, 393221 items lost
Hint: Search with less threads (-g)
[11.02 MKey/s][GPU 11.02 MKey/s][Count 2^36.33][Dead 0][22:28][12887.4MB]
April 30, 2020, 04:00:33 AM
Hello everybodey !!!
Please help me.
I have access to hiend Tesla GPU what I will end in a same day later.
I try to test Kangaroo on real pubkeys but unsoccesfull. Then I use DP=9 computation speed down from 500MKeys to 11MKeys/second (!!!!) I try use 68 Byte ranges etc. ALL THIS UNSUCCESFULL FOR ME.
Please someone tall me what settings I will nedd for starting Kangarok( -d, greed size, etc) and what renges I need to use
?I veryh need help ASAP.
Big thanks !!!
April 30, 2020, 12:04:43 AM
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:
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:
Jump to: