brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning]

[MrFreeDragon]

Tried v1.3 with 80bit ranges.

The speed increased by 5-7% in v1.3 compared to v1.2. BUt as the range wider, the "luck" is very important thing.
First, i tried 16 keys with the same 80 bit ranges:

Code:

$ ./kangaroo -t 0 -gpu in16_80.txt
Kangaroo v1.3
Start:49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB4800000000000000000000
Stop :49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48FFFFFFFFFFFFFFFFFFFF
Keys :16
Number of CPU thread: 0
Range width: 2^80
Number of random walk: 2^20.81 (Max DP=17)
DP size: 17 [0xffff800000000000]
GPU: GPU #0 GeForce GTX 1080 Ti (28x128 cores) Grid(56x256) (177.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.81 kangaroos in 10229.1ms
[459.82 MKey/s][GPU 459.82 MKey/s][Count 2^42.05][Dead 2][03:00:56][2649.2MB]  
Key# 0 Pub:  0x0259A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC 
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EBB3EF3883C1866D4 
[491.45 MKey/s][GPU 491.45 MKey/s][Count 2^41.13][Dead 1][01:36:21][1408.3MB]  
Key# 1 Pub:  0x02A50FBBB20757CC0E9C41C49DD9DF261646EE7936272F3F68C740C9DA50D42BCD 
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EB5ABC43BEBAD3207 
[464.88 MKey/s][GPU 464.88 MKey/s][Count 2^40.00][Dead 1][43:48][644.8MB]  
Key# 2 Pub:  0x0304A49211C0FE07C9F7C94695996F8826E09545375A3CF9677F2D780A3EB70DE3 
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E5698AAAB6CAC52B3 
[494.19 MKey/s][GPU 494.19 MKey/s][Count 2^41.41][Dead 1][01:56:08][1710.0MB]  
Key# 3 Pub:  0x030B39E3F26AF294502A5BE708BB87AEDD9F895868011E60C1D2ABFCA202CD7A4D 
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E59C839258C2AD7A0 
[494.33 MKey/s][GPU 494.33 MKey/s][Count 2^42.67][Dead 9][04:29:05][4074.8MB]  
Key# 4 Pub:  0x02837A31977A73A630C436E680915934A58B8C76EB9B57A42C3C717689BE8C0493 
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E765FB411E63B92B9

The firt five keys were solved for 706 minutes, i.e 141 min per key (2h20min/key). The total time per key is very different and vary from 43 minutes to 4h29min.

Then I tried the same keys but with adjustment to the range and public keys (deducted start range from everything):

Code:

$ ./kangaroo -t 0 -gpu in16_80adj.txt
Kangaroo v1.3
Start:0
Stop :FFFFFFFFFFFFFFFFFFFF
Keys :16
Number of CPU thread: 0
Range width: 2^80
Number of random walk: 2^20.81 (Max DP=17)
DP size: 17 [0xffff800000000000]
GPU: GPU #0 GeForce GTX 1080 Ti (28x128 cores) Grid(56x256) (177.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.81 kangaroos in 10048.4ms
[487.51 MKey/s][GPU 487.51 MKey/s][Count 2^40.31][Dead 0][52:55][798.6MB]  
Key# 0 Pub:  0x026CF3EC949C28918ED0FDC48980B3339343CEB822ACD9B7B3A0D16D9606AEB139 
       Priv: 0xCB5EBB3EF3883C1866D4 
[489.59 MKey/s][GPU 489.59 MKey/s][Count 2^41.48][Dead 1][01:59:26][1794.4MB]  
Key# 1 Pub:  0x02948282BFA4CC7AAA1722F0F72CE9B3708061960084BA188A2C66713C46070F45 
       Priv: 0xCB5EB5ABC43BEBAD3207 
[506.12 MKey/s][GPU 506.12 MKey/s][Count 2^41.54][Dead 1][02:00:52][1867.0MB]  
Key# 2 Pub:  0x0391A7B757335E7026E83C42B868DD6C4A8F379E7EF059DE9A1FC1B7E4E770749A 
       Priv: 0xCB5E5698AAAB6CAC52B3

I stoped the process after 3 keys were solved. For 3 such keys it needed 292 minutes or 97min per key (1h37min / key). The average time was more predictable like 2 hours per key.

I doubt again if such range/pubkey adjustments could improve the progress. May be the initial kangaroos allocation is more effecient in the adjusted ranges? But more tests are required in order to prove it (3 or 5 key are not enough...)

[COBRAS]

-snip-
Please explain me, why always used this start-stop ranges ?
-snip-

We just use the same public keys and ranges in order to test different devices and help JeanLuc to develop his program. If we use different ranges and keys it will be a little bit difficult to undertand the real improvement of the program performance.

The 16 public keys were generated by odolvlobo just for test purposes earlier in this topic:
https://bitcointalk.org/index.php?topic=5238719.msg54184513#msg54184513

The initial range was only 2^64 width, and now we see that this range is too small for the program (the key is found just for 1 minute or less). So for test purposes Etar decided to make the key range wider up to 2^80 (just change the start and end range).

And at the moment we use that enlarged ranges, together with the same 16 public keys.

If you read that test post by odolvlobo you could find that he made a challenge: "I'll give you a whole day to find the private keys for these 16 public keys. ...  If you can do that, I'll be impressed. I don't think that you can find 4". But, JeanLuc accepted this challenge and developed his own tool on CUDA, and after some days we see that all 16 keys in the range 2^64 could be found just for 10 minutes. There is no need 24 hours for it!

This was the explanation why we use that ranges. However, answering on your question, of course you can use any ranges you want and public keys you want.

Big Thank You Bro.

I caryfuly reading all mesages.

😊

[COBRAS]

Tried v1.3 with 80bit ranges.

The speed increased by 5-7% in v1.3 compared to v1.2. BUt as the range wider, the "luck" is very important thing.
First, i tried 16 keys with the same 80 bit ranges:

Code:

$ ./kangaroo -t 0 -gpu in16_80.txt
Kangaroo v1.3
Start:49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB4800000000000000000000
Stop :49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48FFFFFFFFFFFFFFFFFFFF
Keys :16
Number of CPU thread: 0
Range width: 2^80
Number of random walk: 2^20.81 (Max DP=17)
DP size: 17 [0xffff800000000000]
GPU: GPU #0 GeForce GTX 1080 Ti (28x128 cores) Grid(56x256) (177.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.81 kangaroos in 10229.1ms
[459.82 MKey/s][GPU 459.82 MKey/s][Count 2^42.05][Dead 2][03:00:56][2649.2MB]  
Key# 0 Pub:  0x0259A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC 
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EBB3EF3883C1866D4 
[491.45 MKey/s][GPU 491.45 MKey/s][Count 2^41.13][Dead 1][01:36:21][1408.3MB]  
Key# 1 Pub:  0x02A50FBBB20757CC0E9C41C49DD9DF261646EE7936272F3F68C740C9DA50D42BCD 
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EB5ABC43BEBAD3207 
[464.88 MKey/s][GPU 464.88 MKey/s][Count 2^40.00][Dead 1][43:48][644.8MB]  
Key# 2 Pub:  0x0304A49211C0FE07C9F7C94695996F8826E09545375A3CF9677F2D780A3EB70DE3 
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E5698AAAB6CAC52B3 
[494.19 MKey/s][GPU 494.19 MKey/s][Count 2^41.41][Dead 1][01:56:08][1710.0MB]  
Key# 3 Pub:  0x030B39E3F26AF294502A5BE708BB87AEDD9F895868011E60C1D2ABFCA202CD7A4D 
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E59C839258C2AD7A0 
[494.33 MKey/s][GPU 494.33 MKey/s][Count 2^42.67][Dead 9][04:29:05][4074.8MB]  
Key# 4 Pub:  0x02837A31977A73A630C436E680915934A58B8C76EB9B57A42C3C717689BE8C0493 
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E765FB411E63B92B9

The firt five keys were solved for 706 minutes, i.e 141 min per key (2h20min/key). The total time per key is very different and vary from 43 minutes to 4h29min.

Then I tried the same keys but with adjustment to the range and public keys (deducted start range from everything):

Code:

$ ./kangaroo -t 0 -gpu in16_80adj.txt
Kangaroo v1.3
Start:0
Stop :FFFFFFFFFFFFFFFFFFFF
Keys :16
Number of CPU thread: 0
Range width: 2^80
Number of random walk: 2^20.81 (Max DP=17)
DP size: 17 [0xffff800000000000]
GPU: GPU #0 GeForce GTX 1080 Ti (28x128 cores) Grid(56x256) (177.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.81 kangaroos in 10048.4ms
[487.51 MKey/s][GPU 487.51 MKey/s][Count 2^40.31][Dead 0][52:55][798.6MB]  
Key# 0 Pub:  0x026CF3EC949C28918ED0FDC48980B3339343CEB822ACD9B7B3A0D16D9606AEB139 
       Priv: 0xCB5EBB3EF3883C1866D4 
[489.59 MKey/s][GPU 489.59 MKey/s][Count 2^41.48][Dead 1][01:59:26][1794.4MB]  
Key# 1 Pub:  0x02948282BFA4CC7AAA1722F0F72CE9B3708061960084BA188A2C66713C46070F45 
       Priv: 0xCB5EB5ABC43BEBAD3207 
[506.12 MKey/s][GPU 506.12 MKey/s][Count 2^41.54][Dead 1][02:00:52][1867.0MB]  
Key# 2 Pub:  0x0391A7B757335E7026E83C42B868DD6C4A8F379E7EF059DE9A1FC1B7E4E770749A 
       Priv: 0xCB5E5698AAAB6CAC52B3

I stoped the process after 3 keys were solved. For 3 such keys it needed 292 minutes or 97min per key (1h37min / key). The average time was more predictable like 2 hours per key.

I doubt again if such range/pubkey adjustments could improve the progress. May be the initial kangaroos allocation is more effecient in the adjusted ranges? But more tests are required in order to prove it (3 or 5 key are not enough...)

Bro, can you explain more detailed how to modyfy publick key ? I was readyng all your messages but not understand, but I think this is very interesting method to -delet all not neede info from keys for improve calculation....

[MrFreeDragon]

Bro, can you explain more detailed how to modyfy publick key ? I was readyng all your messages but not understand, but I think this is very interesting method to -delet all not neede info from keys for improve calculation....

This is just due basic ECC calculations. But I am not sure it could be important here.

Let's say that the public key Q is within the range [a, b] where a is minimum and b is maximum. I can adjust the range to [a-a, b-a] which is actually [0, b-a] and also adjust the Q in order "to solve the same problem", so the Qadj = Q - a*G where G is the basis Point.

In other words I find the public key for the number a which is a*G and make the ECC substraction Q - a*G which is the Qadj.

Now we try to solve adjusted public key Qadj within the range [0, b-a] and as soon as we find the key, we can easily retrieve the real target private key just adding a to the found one.

If you are not familiar with ECC calculation, try to play with java made ECC calculator. It is not quick, but can make basic ECC calcualtions: point additions, point substraction, point multiplcation by a number, point division.

That ECC calcualtor is here: https://bitcointalk.org/index.php?topic=5202064.0

[Jean_Luc]

I doubt again if such range/pubkey adjustments could improve the progress. May be the initial kangaroos allocation is more effecient in the adjusted ranges? But more tests are required in order to prove it (3 or 5 key are not enough...)

Many thanks for the tests They looks very good !
The translation you did is equivalent to what the code do so the result should be equal.

The new spreading of kangaroos gives more chance to a key in the middle of the range to be found.
At first, a key close to the end of range was harder to find and a key near to the beginning was easier.
It more logical to have a spreading from the middle.

By expending the range of the odolvlobo's test to 80bit, all the 16 keys are very close to each others and near the end of the range (0xCB5E.....)
We should make tests of uniformly distributed key in the range.

[PietCoin97]

i let the new 72 bit test file run this is result (newest version of all kangaroo files)

Code:

Kangaroo.exe -t 0 -d 20 -gpu -gpuId 0,1,2,3,4,5 in72_20.txt
Kangaroo v1.3
Start:59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1000000000000000000
Stop :59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1FFFFFFFFFFFFFFFFFF
Keys :20
Number of CPU thread: 0
Range width: 2^72
Number of random walk: 2^22.49 (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: 20 [0xFFFFF00000000000]
GPU: GPU #2 P104-100 (15x128 cores) Grid(30x256) (99.0 MB used)
SolveKeyGPU Thread GPU#2: creating kangaroos...
GPU: GPU #1 P104-100 (15x128 cores) Grid(30x256) (99.0 MB used)
SolveKeyGPU Thread GPU#1: creating kangaroos...
GPU: GPU #0 P104-100 (15x128 cores) Grid(30x256) (99.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
GPU: GPU #4 GeForce GTX 1070 (15x128 cores) Grid(30x256) (99.0 MB used)
SolveKeyGPU Thread GPU#4: creating kangaroos...
GPU: GPU #5 GeForce GTX 1070 (15x128 cores) Grid(30x256) (99.0 MB used)
SolveKeyGPU Thread GPU#5: creating kangaroos...
GPU: GPU #3 GeForce GTX 1070 (15x128 cores) Grid(30x256) (99.0 MB used)
SolveKeyGPU Thread GPU#3: creating kangaroos...
SolveKeyGPU Thread GPU#1: 2^19.91 kangaroos in 9586.8ms
SolveKeyGPU Thread GPU#0: 2^19.91 kangaroos in 9628.9ms
SolveKeyGPU Thread GPU#2: 2^19.91 kangaroos in 10063.4ms
SolveKeyGPU Thread GPU#4: 2^19.91 kangaroos in 9362.8ms
SolveKeyGPU Thread GPU#5: 2^19.91 kangaroos in 9342.9ms
SolveKeyGPU Thread GPU#3: 2^19.91 kangaroos in 9434.1ms
[1773.35 MKey/s][GPU 1773.35 MKey/s][Count 2^40.41][Dead 5][15:35][111.6MB]
Key# 0 Pub:  0x038F63B86D8EE91D4B78FF4680F927DCC7754CF734A386ED5FA45E71DE9328F433
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D102F962838A4EE7364E
[1765.57 MKey/s][GPU 1765.57 MKey/s][Count 2^39.49][Dead 1][08:31][60.3MB]
Key# 1 Pub:  0x0389044AFFFD381B496D63F8C80CDAAB5E57E40DEE6A56C8AFA5194B1FFD83FEBB
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1F5821BA583622EEE49
[1765.22 MKey/s][GPU 1765.22 MKey/s][Count 2^39.25][Dead 0][07:16][52.0MB]
Key# 2 Pub:  0x0338E88602F88C3268C68552C4C53987F41BB42335A8E36658A80D2F5BDF63615B
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D110DC466D7E3D293A10
[1767.37 MKey/s][GPU 1767.37 MKey/s][Count 2^38.93][Dead 2][05:51][43.3MB]
Key# 3 Pub:  0x026776529C6C8932ABF9DCFDCB2DB2784DCE82164914D4C3294FECFE1B48F3BF27
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1DE55BDE3E1B2F36A9B
[1766.53 MKey/s][GPU 1766.53 MKey/s][Count 2^40.11][Dead 7][13:01][92.1MB]
Key# 4 Pub:  0x03312940E0EE296C23B1E7888A4D23FED01358C1021FE2091D909B0A8D8AA80DE1
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D11B78CA8A9FBCDBDE3E
[1770.19 MKey/s][GPU 1770.19 MKey/s][Count 2^39.92][Dead 5][11:28][80.9MB]
Key# 5 Pub:  0x020097A3826A7BC1EC5383AE390EEA8C436B2B6D2E3770493F7E993B164C9F233E
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D152477D7EC473A483D4
[1767.15 MKey/s][GPU 1767.15 MKey/s][Count 2^39.42][Dead 0][08:10][58.0MB]
Key# 6 Pub:  0x03DAE902F3F4E0A62AA7DF422B2BF802CD9ADA747177F853390BEB7F203E4C3F84
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D10D2AB0CDE883E6B3BC
[1772.77 MKey/s][GPU 1772.77 MKey/s][Count 2^40.01][Dead 2][12:09][85.7MB]
Key# 7 Pub:  0x023C4E51FD6EB029CFD4DDCBD93FAD060C7D026D252EC37923355D1B192C69B9E3
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1B69F2EC54CEEBA50C4
[1772.42 MKey/s][GPU 1772.42 MKey/s][Count 2^38.99][Dead 1][06:06][44.7MB]
Key# 8 Pub:  0x03C3112770BC8455596AF38A2A2E3F556B1F02758945608364C3AFD22FAD806B8D
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D18D06BC6E25E5C7EAEF
[1767.38 MKey/s][GPU 1767.38 MKey/s][Count 2^38.52][Dead 0][04:28][34.8MB]
Key# 9 Pub:  0x0264AE637A90AA93798E7BA6CCFD57CB077BCCAE49D3AB76F6857CA044A423E3AC
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1C8A4760400224E8C05
[1772.54 MKey/s][GPU 1772.54 MKey/s][Count 2^35.83][Dead 0][53s][9.6MB]
Key#10 Pub:  0x0359A0CFB0958A2B6FC562B3824D0BE034C7E947780DAF4B8AF403C72D92496BEF
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D197AD08D8E14C058778
[1769.09 MKey/s][GPU 1769.09 MKey/s][Count 2^38.73][Dead 0][05:08][38.9MB]
Key#11 Pub:  0x020B58A06DC49B931A8B9C08E29306B70FBB56F4F3B8BAB7AEBD409B4DC8086C78
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1C831BC0E9C1450CCCE
[1769.04 MKey/s][GPU 1769.04 MKey/s][Count 2^39.23][Dead 0][07:11][51.7MB]
Key#12 Pub:  0x039E8FE48D08C5465128681D49AE9026240BC612C9BC8A3B6E9D2FA00DBC9021AF
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D17941FCB9F89FAA2C79
[1770.27 MKey/s][GPU 1770.27 MKey/s][Count 2^40.05][Dead 1][12:26][87.9MB]
Key#13 Pub:  0x02131119C5618C26AB5C8DE1B16E60120C918AAC717B06A10ADBCC4BCF44106419
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D166208474EA5CD1D0D9
[1773.82 MKey/s][GPU 1773.82 MKey/s][Count 2^38.51][Dead 0][04:26][34.5MB]
Key#14 Pub:  0x02487FE068AFA2AAFC96EC2941EC8CF4E2600692F8D4F6E4A389AFEA44221E045D
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1AD9E1D5075941AB176
[1772.40 MKey/s][GPU 1772.40 MKey/s][Count 2^39.17][Dead 2][06:53][49.7MB]
Key#15 Pub:  0x034B202C91CF7AA1563048AFCED10781666C8344E0A23884977F5F3396E3CDFBFE
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D166550C0FED3225AE1D
[1771.68 MKey/s][GPU 1771.68 MKey/s][Count 2^38.15][Dead 0][03:31][29.0MB]

[Jean_Luc]

Many thanks for testing
I added some information on expected number of operation and needed memory.

On my test it gives:
Avg Mem=188.0 MB (Theoretical 191.0MB)
Avg Count=37.19 (Theoretical 2^37.25)

Theoretical results are not so bad here, but when you increase the dp, theoretical values become too large because calculation are here done using the asymptotic 2.sqrt(n) + nbKangaroo.2^dp which becomes bad when dp increase. n is the range size.

For instance of the test done by  PietCoin97 (with dp=20), it gives:
Expected operations: 2^42.52 (Measured 2^39.42)
Expected RAM: 460.4MB (Measured 58.5MB)

It is difficult to get the analytical expression of the theoretical values. If anyone can help to find the analytical expression, it would be great.

To find the analytical expression , you have to consider that the extra operation due to dp (nbKangaroo.2^dp) also increase the number of points and increase the probability to find a collision due to the birthday paradox.

So the analytical expression should be something like:

2.sqrt(n) + f(nbKangaroo,dp) where f(nbKangaroo,dp) is a function with an asymptotic equal to nbKangaroo.2^dp.
Calculation of probability on the birthday paradox are rather complex

Here are 2 loglog plots showing the asymptotic (in blue) for some dp and 40 bit search on a classical birthday paradox with a theoretical average of sqrt(PI/2)*sqrt(n) (instead of 2.sqrt(n) in the kangaroo case):

Red plots are experimental plots (averaged on 1000 searches)

Code:

Kangaroo v1.3
Start:59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1000000000000000000
Stop :59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1FFFFFFFFFFFFFFFFFF
Keys :20
Number of CPU thread: 0
Range width: 2^72
Number of kangaroos: 2^18.58
Suggested DP: 16
Expected operations: 2^37.25
Expected RAM: 191.0MB
DP size: 16 [0xFFFF000000000000]
GPU: GPU #0 GeForce GTX 1050 Ti (6x128 cores) Grid(12x256) (45.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^18.58 kangaroos in 1953.4ms
[115.21 MK/s][GPU 115.21 MK/s][Count 2^37.83][Dead 1][40:28 (Avg 23:36)][290.1MB]
Key# 0 Pub:  0x038F63B86D8EE91D4B78FF4680F927DCC7754CF734A386ED5FA45E71DE9328F433
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D102F962838A4EE7364E
[115.23 MK/s][GPU 115.23 MK/s][Count 2^37.29][Dead 1][27:44 (Avg 23:36)][200.6MB]
Key# 1 Pub:  0x0389044AFFFD381B496D63F8C80CDAAB5E57E40DEE6A56C8AFA5194B1FFD83FEBB
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1F5821BA583622EEE49
[115.22 MK/s][GPU 115.22 MK/s][Count 2^37.72][Dead 3][37:26 (Avg 23:36)][268.8MB]
Key# 2 Pub:  0x0338E88602F88C3268C68552C4C53987F41BB42335A8E36658A80D2F5BDF63615B
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D110DC466D7E3D293A10
[115.21 MK/s][GPU 115.21 MK/s][Count 2^37.20][Dead 0][26:02 (Avg 23:36)][188.6MB]
Key# 3 Pub:  0x026776529C6C8932ABF9DCFDCB2DB2784DCE82164914D4C3294FECFE1B48F3BF27
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1DE55BDE3E1B2F36A9B
[115.22 MK/s][GPU 115.22 MK/s][Count 2^37.47][Dead 0][31:24 (Avg 23:36)][226.4MB]
Key# 4 Pub:  0x03312940E0EE296C23B1E7888A4D23FED01358C1021FE2091D909B0A8D8AA80DE1
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D11B78CA8A9FBCDBDE3E
[115.22 MK/s][GPU 115.22 MK/s][Count 2^36.81][Dead 0][20:00 (Avg 23:36)][145.6MB]
Key# 5 Pub:  0x020097A3826A7BC1EC5383AE390EEA8C436B2B6D2E3770493F7E993B164C9F233E
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D152477D7EC473A483D4
[115.21 MK/s][GPU 115.21 MK/s][Count 2^37.74][Dead 1][37:54 (Avg 23:36)][272.0MB]
Key# 6 Pub:  0x03DAE902F3F4E0A62AA7DF422B2BF802CD9ADA747177F853390BEB7F203E4C3F84
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D10D2AB0CDE883E6B3BC
[115.22 MK/s][GPU 115.22 MK/s][Count 2^36.52][Dead 1][16:18 (Avg 23:36)][120.1MB]
Key# 7 Pub:  0x023C4E51FD6EB029CFD4DDCBD93FAD060C7D026D252EC37923355D1B192C69B9E3
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1B69F2EC54CEEBA50C4
[115.22 MK/s][GPU 115.22 MK/s][Count 2^37.54][Dead 2][33:09 (Avg 23:36)][238.4MB]
Key# 8 Pub:  0x03C3112770BC8455596AF38A2A2E3F556B1F02758945608364C3AFD22FAD806B8D
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D18D06BC6E25E5C7EAEF
[115.21 MK/s][GPU 115.21 MK/s][Count 2^37.15][Dead 0][25:10 (Avg 23:36)][182.5MB]
Key# 9 Pub:  0x0264AE637A90AA93798E7BA6CCFD57CB077BCCAE49D3AB76F6857CA044A423E3AC
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1C8A4760400224E8C05
[115.22 MK/s][GPU 115.22 MK/s][Count 2^36.17][Dead 0][12:48 (Avg 23:36)][95.9MB]
Key#10 Pub:  0x0359A0CFB0958A2B6FC562B3824D0BE034C7E947780DAF4B8AF403C72D92496BEF
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D197AD08D8E14C058778
[115.22 MK/s][GPU 115.22 MK/s][Count 2^35.52][Dead 0][08:11 (Avg 23:36)][61.8MB]
Key#11 Pub:  0x020B58A06DC49B931A8B9C08E29306B70FBB56F4F3B8BAB7AEBD409B4DC8086C78
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1C831BC0E9C1450CCCE
[115.22 MK/s][GPU 115.22 MK/s][Count 2^37.26][Dead 1][27:09 (Avg 23:36)][196.5MB]
Key#12 Pub:  0x039E8FE48D08C5465128681D49AE9026240BC612C9BC8A3B6E9D2FA00DBC9021AF
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D17941FCB9F89FAA2C79
[115.22 MK/s][GPU 115.22 MK/s][Count 2^36.50][Dead 0][16:03 (Avg 23:36)][118.4MB]
Key#13 Pub:  0x02131119C5618C26AB5C8DE1B16E60120C918AAC717B06A10ADBCC4BCF44106419
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D166208474EA5CD1D0D9
[115.21 MK/s][GPU 115.21 MK/s][Count 2^36.25][Dead 2][13:33 (Avg 23:36)][101.1MB]
Key#14 Pub:  0x02487FE068AFA2AAFC96EC2941EC8CF4E2600692F8D4F6E4A389AFEA44221E045D
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1AD9E1D5075941AB176
[115.22 MK/s][GPU 115.22 MK/s][Count 2^37.66][Dead 0][35:54 (Avg 23:36)][258.2MB]
Key#15 Pub:  0x034B202C91CF7AA1563048AFCED10781666C8344E0A23884977F5F3396E3CDFBFE
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D166550C0FED3225AE1D
[115.22 MK/s][GPU 115.22 MK/s][Count 2^37.71][Dead 2][37:14 (Avg 23:36)][267.2MB]
Key#16 Pub:  0x023510C7370A558126EF057C738A4943021E5FB08B41799AE097190DFC5538DB69
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D16DA62AB9D45017CFF3
[115.22 MK/s][GPU 115.22 MK/s][Count 2^35.87][Dead 0][10:26 (Avg 23:36)][78.1MB]
Key#17 Pub:  0x0336CE6F79E48B6493CF2BC2DE87BFE9504D30CD62B9B5F992E1A5933D69076A76
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1A7F3A8F6001FFF3E8C
[115.21 MK/s][GPU 115.21 MK/s][Count 2^37.62][Dead 3][34:51 (Avg 23:36)][250.4MB]
Key#18 Pub:  0x03292ACD7402F076829CF4DC40B659D24ACCF67F2884DF4CD111847C651F18512A
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1DF6AE20D48B230C23C
[115.21 MK/s][GPU 115.21 MK/s][Count 2^37.27][Dead 1][27:30 (Avg 23:36)][198.8MB]
Key#19 Pub:  0x036C4AF425D93153FD0593787399A78322699F498C4703E2D1524C15F0137C2D14
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D13B97B84AC3FBEDF0AF

Done: Total time 08:39:58

[PietCoin97]

Jean Luc i made a new test run with 72 bit file with db 16 !

here is result

Code:

Kangaroo.exe -t 0 -d 16 -gpu -gpuId 0,1,2,3,4,5 in72_20.txt
Kangaroo v1.3
Start:59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1000000000000000000
Stop :59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1FFFFFFFFFFFFFFFFFF
Keys :20
Number of CPU thread: 0
Range width: 2^72
Number of random walk: 2^22.49 (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: 16 [0xFFFF000000000000]
GPU: GPU #1 P104-100 (15x128 cores) Grid(30x256) (99.0 MB used)
SolveKeyGPU Thread GPU#1: creating kangaroos...
GPU: GPU #0 P104-100 (15x128 cores) Grid(30x256) (99.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
GPU: GPU #2 P104-100 (15x128 cores) Grid(30x256) (99.0 MB used)
SolveKeyGPU Thread GPU#2: creating kangaroos...
GPU: GPU #3 GeForce GTX 1070 (15x128 cores) Grid(30x256) (99.0 MB used)
SolveKeyGPU Thread GPU#3: creating kangaroos...
GPU: GPU #5 GeForce GTX 1070 (15x128 cores) Grid(30x256) (99.0 MB used)
SolveKeyGPU Thread GPU#5: creating kangaroos...
GPU: GPU #4 GeForce GTX 1070 (15x128 cores) Grid(30x256) (99.0 MB used)
SolveKeyGPU Thread GPU#4: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^19.91 kangaroos in 11607.8ms
SolveKeyGPU Thread GPU#1: 2^19.91 kangaroos in 12139.8ms
SolveKeyGPU Thread GPU#2: 2^19.91 kangaroos in 11884.6ms
SolveKeyGPU Thread GPU#3: 2^19.91 kangaroos in 11618.0ms
SolveKeyGPU Thread GPU#5: 2^19.91 kangaroos in 11629.0ms
SolveKeyGPU Thread GPU#4: 2^19.91 kangaroos in 11339.5ms
[1994.54 MKey/s][GPU 1994.54 MKey/s][Count 2^37.60][Dead 0][01:57][248.5MB]
Key# 0 Pub:  0x038F63B86D8EE91D4B78FF4680F927DCC7754CF734A386ED5FA45E71DE9328F433
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D102F962838A4EE7364E
[1977.51 MKey/s][GPU 1977.51 MKey/s][Count 2^38.61][Dead 2][04:16][491.9MB]
Key# 1 Pub:  0x0389044AFFFD381B496D63F8C80CDAAB5E57E40DEE6A56C8AFA5194B1FFD83FEBB
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1F5821BA583622EEE49
[1978.09 MKey/s][GPU 1978.09 MKey/s][Count 2^38.17][Dead 3][03:15][364.6MB]
Key# 2 Pub:  0x0338E88602F88C3268C68552C4C53987F41BB42335A8E36658A80D2F5BDF63615B
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D110DC466D7E3D293A10
[1981.14 MKey/s][GPU 1981.14 MKey/s][Count 2^38.79][Dead 4][04:51][559.2MB]
Key# 3 Pub:  0x026776529C6C8932ABF9DCFDCB2DB2784DCE82164914D4C3294FECFE1B48F3BF27
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1DE55BDE3E1B2F36A9B
[1754.92 MKey/s][GPU 1754.92 MKey/s][Count 2^39.34][Dead 7][07:39][814.4MB]
Key# 4 Pub:  0x03312940E0EE296C23B1E7888A4D23FED01358C1021FE2091D909B0A8D8AA80DE1
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D11B78CA8A9FBCDBDE3E
[1759.01 MKey/s][GPU 1759.01 MKey/s][Count 2^38.73][Dead 1][05:11][535.3MB]
Key# 5 Pub:  0x020097A3826A7BC1EC5383AE390EEA8C436B2B6D2E3770493F7E993B164C9F233E
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D152477D7EC473A483D4
[1776.69 MKey/s][GPU 1776.69 MKey/s][Count 2^37.08][Dead 0][01:47][174.5MB]
Key# 6 Pub:  0x03DAE902F3F4E0A62AA7DF422B2BF802CD9ADA747177F853390BEB7F203E4C3F84
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D10D2AB0CDE883E6B3BC
[1778.60 MKey/s][GPU 1778.60 MKey/s][Count 2^37.97][Dead 0][03:09][318.9MB]
Key# 7 Pub:  0x023C4E51FD6EB029CFD4DDCBD93FAD060C7D026D252EC37923355D1B192C69B9E3
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1B69F2EC54CEEBA50C4
[1758.84 MKey/s][GPU 1758.84 MKey/s][Count 2^38.01][Dead 0][03:13][327.3MB]
Key# 8 Pub:  0x03C3112770BC8455596AF38A2A2E3F556B1F02758945608364C3AFD22FAD806B8D
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D18D06BC6E25E5C7EAEF
[1774.05 MKey/s][GPU 1774.05 MKey/s][Count 2^38.19][Dead 0][03:37][370.9MB]
Key# 9 Pub:  0x0264AE637A90AA93798E7BA6CCFD57CB077BCCAE49D3AB76F6857CA044A423E3AC
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1C8A4760400224E8C05
[1756.48 MKey/s][GPU 1756.48 MKey/s][Count 2^38.25][Dead 1][03:46][386.4MB]
Key#10 Pub:  0x0359A0CFB0958A2B6FC562B3824D0BE034C7E947780DAF4B8AF403C72D92496BEF
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D197AD08D8E14C058778
[1774.29 MKey/s][GPU 1774.29 MKey/s][Count 2^37.31][Dead 0][02:03][203.4MB]
Key#11 Pub:  0x020B58A06DC49B931A8B9C08E29306B70FBB56F4F3B8BAB7AEBD409B4DC8086C78
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1C831BC0E9C1450CCCE
[1757.65 MKey/s][GPU 1757.65 MKey/s][Count 2^37.67][Dead 0][02:35][260.1MB]
Key#12 Pub:  0x039E8FE48D08C5465128681D49AE9026240BC612C9BC8A3B6E9D2FA00DBC9021AF
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D17941FCB9F89FAA2C79
[1758.93 MKey/s][GPU 1758.93 MKey/s][Count 2^37.20][Dead 1][01:56][189.2MB]
Key#13 Pub:  0x02131119C5618C26AB5C8DE1B16E60120C918AAC717B06A10ADBCC4BCF44106419
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D166208474EA5CD1D0D9
[1755.93 MKey/s][GPU 1755.93 MKey/s][Count 2^38.61][Dead 4][04:45][493.3MB]
Key#14 Pub:  0x02487FE068AFA2AAFC96EC2941EC8CF4E2600692F8D4F6E4A389AFEA44221E045D
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1AD9E1D5075941AB176
[1761.87 MKey/s][GPU 1761.87 MKey/s][Count 2^37.83][Dead 1][02:53][290.5MB]
Key#15 Pub:  0x034B202C91CF7AA1563048AFCED10781666C8344E0A23884977F5F3396E3CDFBFE
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D166550C0FED3225AE1D
[1753.91 MKey/s][GPU 1753.91 MKey/s][Count 2^38.36][Dead 0][04:03][417.0MB]
Key#16 Pub:  0x023510C7370A558126EF057C738A4943021E5FB08B41799AE097190DFC5538DB69
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D16DA62AB9D45017CFF3
[1751.52 MKey/s][GPU 1751.52 MKey/s][Count 2^38.36][Dead 3][04:03][416.6MB]
Key#17 Pub:  0x0336CE6F79E48B6493CF2BC2DE87BFE9504D30CD62B9B5F992E1A5933D69076A76
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1A7F3A8F6001FFF3E8C
[1752.90 MKey/s][GPU 1752.90 MKey/s][Count 2^38.22][Dead 0][03:41][376.7MB]
Key#18 Pub:  0x03292ACD7402F076829CF4DC40B659D24ACCF67F2884DF4CD111847C651F18512A
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1DF6AE20D48B230C23C
[1752.40 MKey/s][GPU 1752.40 MKey/s][Count 2^38.23][Dead 1][03:43][380.5MB]
Key#19 Pub:  0x036C4AF425D93153FD0593787399A78322699F498C4703E2D1524C15F0137C2D14
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D13B97B84AC3FBEDF0AF

Done: Total time 01:13:46

I also try it with standard settings with no change and it was terrible (system use db 11 as standard )

Ram usage goes up really fast and speed decrease really fast

[MrFreeDragon]

-snip-
The translation you did is equivalent to what the code do so the result should be equal.
-snip-

It late to read it, I have alreade compared initial ranges and the adjusted ranges for 16 keys in 75bit ranges. And yes, the result is more or less the same. See below.

-snip-
By expending the range of the odolvlobo's test to 80bit, all the 16 keys are very close to each others and near the end of the range (0xCB5E.....)
We should make tests of uniformly distributed key in the range.
-snip-

Actually where is the key should not be important, we just should know the range. But for better test purposes I generated the 16 keys equally distributed within the range 2^75 width:
- generated random 256bit number as the Start Range
- generated 16 random 75bit numbers in the range [0, 2^75]
- added the received 16 random numbers to the start range and received 16 numbers in the range [Start Range; Start Range + 2^75]
- generated the corresponding public keys and made the tests with Kangaroo v1.3

For 16 keys in 75bit range I needed 5h43min, i.e. 21:27min per key.

Code:

$ ./kangaroo -t 0 -gpu in16_75.txt
Kangaroo v1.3
Start:C4BB0AEC5FEE2E663935C981FBD08E9A7C95771BA3FA9FDBB2F47043B3A804B9
Stop :C4BB0AEC5FEE2E663935C981FBD08E9A7C95771BA3FAA7DBB2F47043B3A804B9
Keys :16
Number of CPU thread: 0
Range width: 2^76
Number of random walk: 2^20.81 (Max DP=15)
DP size: 15 [0xfffe000000000000]
GPU: GPU #0 GeForce GTX 1080 Ti (28x128 cores) Grid(56x256) (177.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.81 kangaroos in 8404.3ms
[474.95 MKey/s][GPU 474.95 MKey/s][Count 2^39.23][Dead 1][25:29][1502.9MB]  
Key# 0 Pub:  0x02E455C698A70DE4D6E6D99A327EEC8F86712129F787FA2BBCD2B72493194653DC 
       Priv: 0xC4BB0AEC5FEE2E663935C981FBD08E9A7C95771BA3FAA3553D90877FB5FB85DF 
[481.22 MKey/s][GPU 481.22 MKey/s][Count 2^39.34][Dead 1][27:41][1625.8MB]  
Key# 1 Pub:  0x0207B4E4CC149E0B21E5219B241EDEEC6A24A6CC4AF2621D126F9F3641D2AC4D97 
       Priv: 0xC4BB0AEC5FEE2E663935C981FBD08E9A7C95771BA3FAA152AB6B2EA884C0CFCF 
[481.27 MKey/s][GPU 481.27 MKey/s][Count 2^37.71][Dead 0][09:01][528.9MB]  
Key# 2 Pub:  0x03CE262B34FFEE8A2F356E63A631FCED9190BB08FF2E637ADFCBC092E14C8F322D 
       Priv: 0xC4BB0AEC5FEE2E663935C981FBD08E9A7C95771BA3FAA129564F22C45991003E 
[483.26 MKey/s][GPU 483.26 MKey/s][Count 2^38.93][Dead 0][20:50][1224.4MB]  
Key# 3 Pub:  0x03D95CB162E79B60C7B5B7EDE09AD80296D1035351D3A84724E28A25820A560597 
       Priv: 0xC4BB0AEC5FEE2E663935C981FBD08E9A7C95771BA3FAA306AE0732C491F4A2CE 
[481.47 MKey/s][GPU 481.47 MKey/s][Count 2^38.95][Dead 0][21:02][1238.1MB]  
Key# 4 Pub:  0x0366660CEB41280F2C84568E4721E035ADC7BDDEB04DE35F4E2B0197DF0C2B4668 
       Priv: 0xC4BB0AEC5FEE2E663935C981FBD08E9A7C95771BA3FAA6CF172CE1D5F66D074D 
[481.01 MKey/s][GPU 481.01 MKey/s][Count 2^38.32][Dead 0][13:41][804.9MB]  
Key# 5 Pub:  0x034323240C672EB76DB78C293F04531D6EF54B2F54EEDB5AC7225D792AF618C7F8 
       Priv: 0xC4BB0AEC5FEE2E663935C981FBD08E9A7C95771BA3FAA430894953B59C248F8E 
[483.26 MKey/s][GPU 483.26 MKey/s][Count 2^39.11][Dead 0][23:33][1384.1MB]  
Key# 6 Pub:  0x02C3B807E622C89012FF76A4AA7C8AE15CDD981AA5A840F7697386BE81F9B7BDBA 
       Priv: 0xC4BB0AEC5FEE2E663935C981FBD08E9A7C95771BA3FAA0668081B3432C46D5E3 
[481.24 MKey/s][GPU 481.24 MKey/s][Count 2^37.58][Dead 0][08:17][484.4MB]  
Key# 7 Pub:  0x03F53C72BB2AB0551B475C48495C1F6B558C6C6C3D2931F622B710AA0D639DFB74 
       Priv: 0xC4BB0AEC5FEE2E663935C981FBD08E9A7C95771BA3FAA64B7FD0324E1142307D 
[480.95 MKey/s][GPU 480.95 MKey/s][Count 2^38.35][Dead 0][14:03][822.3MB]  
Key# 8 Pub:  0x033DD4E0E7DF773652B5BCC41534DA0AD6061C0078DB4E2626171427D82A5B5920 
       Priv: 0xC4BB0AEC5FEE2E663935C981FBD08E9A7C95771BA3FAA67568DBA900EA7CC2E3 
[483.86 MKey/s][GPU 483.86 MKey/s][Count 2^40.25][Dead 5][51:50][3053.0MB]  
Key# 9 Pub:  0x02235A5FF164B4019B4915CF853462E350C11AEC015A1C42A502314932F5FD1CE9 
       Priv: 0xC4BB0AEC5FEE2E663935C981FBD08E9A7C95771BA3FAA45833682E554A2194CB 
[496.45 MKey/s][GPU 496.45 MKey/s][Count 2^40.04][Dead 4][43:21][2629.5MB]  
Key#10 Pub:  0x025B2052FFD106CD589E4370FA4C43AB9353563F8B6728E06A0E3B80E2D82ED456 
       Priv: 0xC4BB0AEC5FEE2E663935C981FBD08E9A7C95771BA3FAA13F95D4DCFE14B5C883 
[498.49 MKey/s][GPU 498.49 MKey/s][Count 2^38.67][Dead 1][16:55][1023.8MB]  
Key#11 Pub:  0x03B76634AF13859DBDA5F3A0247DB6BEFFC7B6EA01C837D647E425B232B6AF2B2B 
       Priv: 0xC4BB0AEC5FEE2E663935C981FBD08E9A7C95771BA3FAA7C2134716881D369205 
[496.66 MKey/s][GPU 496.66 MKey/s][Count 2^38.68][Dead 1][17:03][1032.5MB]  
Key#12 Pub:  0x028D491EC623B9A8FFE0D5EF895AF712CD48AB5D002DE553767332B0485BCC2486 
       Priv: 0xC4BB0AEC5FEE2E663935C981FBD08E9A7C95771BA3FAA704E0D7A7D584E9B296 
[475.70 MKey/s][GPU 475.70 MKey/s][Count 2^39.39][Dead 1][28:00][1682.0MB]  
Key#13 Pub:  0x031269A54AC1527326322E17DBA9438F9C3BA478408C8116B786C4A34EE89D05B5 
       Priv: 0xC4BB0AEC5FEE2E663935C981FBD08E9A7C95771BA3FAA2C500CE4F2B11396030 
[473.44 MKey/s][GPU 473.44 MKey/s][Count 2^37.83][Dead 0][09:54][572.4MB]  
Key#14 Pub:  0x026892472C7136380FA13050F081FBCC9636DCF7D1DED54D51E73BBC1FCAC76A1C 
       Priv: 0xC4BB0AEC5FEE2E663935C981FBD08E9A7C95771BA3FAA0F1BD85AFDE65C75FAB 
[473.39 MKey/s][GPU 473.39 MKey/s][Count 2^37.76][Dead 0][09:30][546.4MB]  
Key#15 Pub:  0x028EA28FACAE81D62174ED3D7C2ABCBB8889E03744F925E2DC98474A799F10DF37 
       Priv: 0xC4BB0AEC5FEE2E663935C981FBD08E9A7C95771BA3FAA0C88C19E63DD1275411 

Done: Total time 05:42:36

Then I made the adjustments and deducted Start Range from every key and the range as well, so now the range to search become [0, 2^75].
The total time to search for the adjusted keys was 5h23min, i.e. 20:10min per key.

So the total time is more or less the same. The reason the 1st test was longer because 2 keys were found for 43 and 51 min (2 times longer than average) with 4-5 dead kangaroos comapred to average 0-1 dead kangaroos. So, just not lucky ones

I think these are good results. The main thing here is the Count value for every key.
All my keys were within the range 2^75 width, so the direct brutforce needed 2^75 operations. The expected average for pollard kangaroo method is (1.818 + o(1))SquareRoot(2^75) = 2^38.36
/* Why 1.818 square root? - see here https://arxiv.org/pdf/1501.07019.pdf */

Among the 32 total tests 24 keys were found for longer than 2^38.36 and 8 keys were found for less than 2^38.36. This results is very good I think. I did not expect 50%/50% for 32 tests. 8 keys found for less than the expected theoretical average number of operations is quite good.

PS. The program says Range width: 2^76 for my range Start:0 - Stop :8000000000000000000, however it is exactly 2^75. The same shows for the 1st tests - 2^76 howver the range width is 2^75 only. I mention for the pruposes of direct brute force determination. For my ranges it is 2^75, and not 2^76.

[Jean_Luc]

May thanks again for all these tests

I think these are good results. The main thing here is the Count value for every key.
All my keys were within the range 2^75 width, so the direct brutforce needed 2^75 operations. The expected average for pollard kangaroo method is (1.818 + o(1))SquareRoot(2^75) = 2^38.36
/* Why 1.818 square root? - see here https://arxiv.org/pdf/1501.07019.pdf */

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.

PS. The program says Range width: 2^76 for my range Start:0 - Stop :8000000000000000000, however it is exactly 2^75. The same shows for the 1st tests - 2^76 howver the range width is 2^75 only. I mention for the pruposes of direct brute force determination. For my ranges it is 2^75, and not 2^76.

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

[MrFreeDragon]

-snip-
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

Ok, noted. For large numbers (2^75+1) rounded to 2^76 makes very big difference (2 factor). This dos not affect the program speed, however there is no need to show the width range in integer power of 2. I guess that the range width lets say 2^75.01 also applicable.

If take log2(Stop-Start) the width 2^75+1 will not be rounded to 2^76 but will be showed as 2^75

[Jean_Luc]

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...

[PietCoin97]

Jean luc when do you add multi pub key search and how would it be work?

[Jean_Luc]

Jean luc when do you add multi pub key search and how would it be work?

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.

[PietCoin97]

OK but can you maybe add first multi pub key search and after that you can optimize all together?

[dextronomous]

hi Jean_Luc.

was wondering if it was possible to have a verbose method available, to see a bit more details. about wich range or space it is at.

thanks a lot great software very fast. especially 1.3

[COBRAS]

OK but can you maybe add first multi pub key search and after that you can optimize all together?

Helli. You have multi GPU balid. You can work from one to next target fine. Other members in this thread have only one GPU !!! I think this thread for no brain-less people with single GPU bitcoin miners Have a nice day.

P.s. Luc, please do not share code for multy key finder. In future year, after we are making all test s ;-)share sach code will be  fine I thinck.

[COBRAS]

OK but can you maybe add first multi pub key search and after that you can optimize all together?

What pubkey you interested ? Mining pubkey in very hard task I think, and very needed first.

[COBRAS]

Jean luc when do you add multi pub key search and how would it be work?

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.

Beeeeeegest thank you Jean_Luc.  I think your relise will be great again )) like all your previous relises.

[Jean_Luc]

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