Pollard's kangaroo ECDLP solver

[Jean_Luc]

Hi,

I published a new release 2.2:
https://github.com/JeanLucPons/Kangaroo/releases/tag/2.2

Slight performance increase:
    ModInv performance increase (Thanks to Peter Dettman)
    GPU kernel performance increase

Thanks to gmaxwell for pointing me out this interesting PR of bitcoin core

[1715683953]

1715683953

[1715683953]

1715683953

[1715683953]

1715683953

[1715683953]

1715683953

[1715683953]

1715683953

[1715683953]

1715683953

[PawGo]

Could someone tell me how to set the parameter -m ? And what does 'expected operations' number mean?
On the plot in github I see that there is chance like +- 99% when the number of group operations is 6*sqrt(n).
If for example program shows 'Expected operations: 2^44.10', when may I assume there is no result? 2^44.10? 2^45? Sooner, later?

[Marynarz]

Could someone explain to me why this happened?

Code:

 Unexpected wrong collision, reset kangaroo !
Found: Td 26B501C33D35DA
Found: Wd 26B501C33D35DA

 Unexpected wrong collision, reset kangaroo !
Found: Td 631129815BBDF2
Found: Wd 631129815BBDF2

 Unexpected wrong collision, reset kangaroo !
Found: Td 62F22824B6E91
Found: Wd 62F22824B6E91

 Unexpected wrong collision, reset kangaroo !
Found: Td 508A6055322AF9
Found: Wd 508A6055322AF9

 Unexpected wrong collision, reset kangaroo !
Found: Td 2D3A2764183555
Found: Wd 2D3A2764183555

 Unexpected wrong collision, reset kangaroo !
Found: Td 66A2632596D7A6
Found: Wd 66A2632596D7A6

[Jean_Luc]

Could someone explain to me why this happened?

This should not happen. Which release is producing wrong collisions and in which cases (merging work file, basic usage, ..) ?

Could someone tell me how to set the parameter -m ? And what does 'expected operations' number mean?
On the plot in github I see that there is chance like +- 99% when the number of group operations is 6*sqrt(n).
If for example program shows 'Expected operations: 2^44.10', when may I assume there is no result? 2^44.10? 2^45? Sooner, later?

The expected number of operation is the average number of group operations needed to solve the key (including the DP overhead). It correspond to ~50% probability.
If you use -m 3 and if the search is aborted, you are sure at ~99.7% that the key is not in the given range.

[Marynarz]

Could someone explain to me why this happened?

This should not happen. Which release is producing wrong collisions and in which cases (merging work file, basic usage, ..) ?

It happened when solving the problem with DP 13, I also wanted to add with over 6 million kangaroos dead.

The problem occurred in v2.1

[Jean_Luc]

It happened when solving the problem with DP 13, I also wanted to add with over 6 million kangaroos dead.

The problem occurred in v2.1

What do you mean by "adding 6 million kangaroos dead" ?
Did you modify the code ?

[Marynarz]

Ah...this google translator over 6 million dead kangaroo appeared while solving the problem with DP13, I solved the problem using the -t 4 processor if it matters.


PS. I didn't modify the code.

[Jean_Luc]

Ah...this google translator over 6 million dead kangaroo appeared while solving the problem with DP13, I solved the problem using the -t 4 processor if it matters.


PS. I didn't modify the code.

OK could give me your input file and how you launched the program ?
Lots of dead kangaroos usually means that you search for a key which is out of the specified range.

[PawGo]

The expected number of operation is the average number of group operations needed to solve the key (including the DP overhead). It correspond to ~50% probability.
If you use -m 3 and if the search is aborted, you are sure at ~99.7% that the key is not in the given range.

Thank you, now it is clear.

[Marynarz]

OK could give me your input file and how you launched the program ?
Lots of dead kangaroos usually means that you search for a key which is out of the specified range.

I run the program like this

Code:

Kangaroo.exe -t 4 -ws -i save.work2 -w save.work2 -wi 350 in2.txt

In Kangaroo v2.2 I have the same problem with this file, the file will be sent soon in a private message.

Code:

Kangaroo v2.2
Loading: save.work2
Version   : 0
DP bits   : 13
Start     : 0
Stop      : FFFFFFFFFFFFFF
Key       : --------------------------------------------------------------------
Count     : 2405518294016 2^41.129
Time      : 2.4d
DP Size   : 3.4/4.3GB
DP Count  : 114730854 2^26.774
HT Max    : 1212 [@ 00C579]
HT Min    : 0 [@ 01A688]
HT Avg    : 437.66
HT SDev   : 522.59
Kangaroos : 0 2^-inf

[Marynarz]

Hi, are any of the users using kangaroo version Cuda 8.0?  at the moment I can't compile Kangaroo and I need this version.  could someone send a compiled version?

[PawGo]

Maybe just make a change in Makefile to use installed/preferred version instead of specified in the file - change the lines 43 to:

CUDA       = /usr/local/cuda
CXXCUDA    = /usr/bin/g++

[Bitcoinfan2020]

Hi, are any of the users using kangaroo version Cuda 8.0?  at the moment I can't compile Kangaroo and I need this version.  could someone send a compiled version?

Here it is, the latest .exe release.

https://github.com/JeanLucPons/Kangaroo/releases/tag/2.2

[Marynarz]

Does any of the users have such a card?   NVIDIA GeForce GTX Titan Z 12GB

I would like to know what speed you can get in Kangaroo.

[MrFreeDragon]

Does any of the users have such a card?   NVIDIA GeForce GTX Titan Z 12GB

I would like to know what speed you can get in Kangaroo.

It should be better than 2080ti. May be it is close to Tesla performance. However I am not sure.

Why do you have such question? If you consider buying this card, you can run the tests before your final decision.

[Marynarz]

Thanks for the info

[Marynarz]

Hi,


Does anyone know why my speed is so small, the card is GTX Titan Z.

i run kangaroo like this

Code:

Kangaroo.exe -t 0 -d 28 -gpu -gpuId 0,1 -ws -i save.work4 -w save.work4 -wi 600 -o found.txt in2.txt

Code:

Kangaroo v2.2
Loading: save.work4
Start:0
Stop :7FFFFFFFFFFFFFFFFFFFFF
Keys :1
LoadWork: [HashTable 3.0/3.7GB] [20s]
Number of CPU thread: 0
Range width: 2^87
Jump Avg distance: 2^42.96
Number of kangaroos: 2^21.49
Suggested DP: 19
Expected operations: 2^46.56
Expected RAM: 26.7MB
DP size: 28 [0xFFFFFFF000000000]
GPU: GPU #0 GeForce GTX TITAN Z (15x192 cores) Grid(30x384) (119.5 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
GPU: GPU #1 GeForce GTX TITAN Z (15x192 cores) Grid(30x384) (119.5 MB used)
SolveKeyGPU Thread GPU#1: creating kangaroos...
SolveKeyGPU Thread GPU#1: 2^20.49 kangaroos [10.0s]
SolveKeyGPU Thread GPU#0: 2^20.49 kangaroos [10.1s]
[324.91 MK/s][GPU 324.91 MK/s][Count 2^48.60][Dead 0][13.2d (Avg 3.7d)][3.0/3.7G
[512.78 MK/s][GPU 512.78 MK/s][Count 2^48.60][Dead 0][13.2d (Avg 2.3d)][3.0/3.7G
[520.19 MK/s][GPU 520.19 MK/s][Count 2^48.60][Dead 0][13.2d (Avg 2.3d)][3.0/3.7G
[484.27 MK/s][GPU 484.27 MK/s][Count 2^48.60][Dead 0][13.2d (Avg 2.5d)][3.0/3.7G
[452.12 MK/s][GPU 452.12 MK/s][Count 2^48.60][Dead 0][13.2d (Avg 2.7d)][3.0/3.7G
[429.34 MK/s][GPU 429.34 MK/s][Count 2^48.60][Dead 0][13.2d (Avg 2.8d)][3.0/3.7G
[416.00 MK/s][GPU 416.00 MK/s][Count 2^48.60][Dead 0][13.2d (Avg 2.9d)][3.0/3.7G
[407.24 MK/s][GPU 407.24 MK/s][Count 2^48.60][Dead 0][13.2d (Avg 2.9d)][3.0/3.7G
[410.43 MK/s][GPU 410.43 MK/s][Count 2^48.60][Dead 0][13.2d (Avg 2.9d)][3.0/3.7G
[408.74 MK/s][GPU 408.74 MK/s][Count 2^48.60][Dead 0][13.2d (Avg 2.9d)][3.0/3.7G
[411.46 MK/s][GPU 411.46 MK/s][Count 2^48.60][Dead 0][13.2d (Avg 2.9d)][3.0/3.7G
[410.52 MK/s][GPU 410.52 MK/s][Count 2^48.60][Dead 0][13.2d (Avg 2.9d)][3.0/3.7G
[411.84 MK/s][GPU 411.84 MK/s][Count 2^48.60][Dead 0][13.2d (Avg 2.9d)][3.0/3.7G
[411.98 MK/s][GPU 411.98 MK/s][Count 2^48.60][Dead 0][13.2d (Avg 2.9d)][3.0/3.7G
[410.49 MK/s][GPU 410.49 MK/s][Count 2^48.60][Dead 0][13.2d (Avg 2.9d)][3.0/3.7G

I am using the compiled version of Jean_Luc.

[Jean_Luc]

Hi,
Does anyone know why my speed is so small, the card is GTX Titan Z.

At the beginning of the process, the speed was the same ?
Avoid to have too large hashtable in RAM even if you have enough RAM on your system, it is preferable to use -wsplit and merge workfile offline.

[Marynarz]

Hi,
Does anyone know why my speed is so small, the card is GTX Titan Z.

At the beginning of the process, the speed was the same ?
Avoid to have too large hashtable in RAM even if you have enough RAM on your system, it is preferable to use -wsplit and merge workfile offline.

Unfortunately I am not using Kangaroo in server mode.

A few days ago I bought a Titan card and wanted to resume working (previously I used 2 x ASUS GTX 1060 6GB = 460 MK/s) and to my surprise this speed is from the start and no matter what DP is set. I have the latest graphics drivers installed and CUDA 10.2 and the truth is, my hands are dropping, I have no idea where the problem is. Will there be any good soul to help solve this problem?

My motherboard is ASUS CROSSHAIR V FORMULA-Z,
16 GB RAM,
Corsair 850W power supply
AMD FX 8350 processor

I will be very grateful for any help.

[PawGo]

Which ccap you use for compilation?