Post
Topic
Board Development & Technical Discussion
Re: Pollard's kangaroo ECDLP solver
by
MrFreeDragon
on 02/05/2020, 03:53:09 UTC
I tested v1.4beta, and it found the keys for me ~25% faster (in time) and with 3-5% faster speed compared with v1.3
GeForce GTX 1080 Ti 11Gb

I used 5 keys in 2^75 range and made 10 tests (5 keys in original range, and the same 5 keys in adjusted range shift to the beginning).

First 5 keys were found for 1:11:51 hours (14:22min per key - the same as predicted by program(!)), and the second 5 keys for 1:35:36 hours (19:06min per key). And the whole average was 16:45min per key. Compared with 20-22min with version 1.3. Prevous tests with version 1.3 and same 2^75 ranges are here: https://bitcointalk.org/index.php?topic=5238719.msg54302113#msg54302113

Code:
$ ./kangaroo -gpu -t 0 in75.txt
Kangaroo v1.4beta
Start:60B371918170B1249281CB73F3FA28F4747625CCC9E0BD8CCF264AE3CAC74D24
Stop :60B371918170B1249281CB73F3FA28F4747625CCC9E0C58CCF264AE3CAC74D23
Keys :5
Number of CPU thread: 0
Range width: 2^75
Jump Avg distance: 2^37.03
Number of kangaroos: 2^20.81
Suggested DP: 15
Expected operations: 2^38.65
Expected RAM: 1003.7MB
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 10013.5ms
[500.05 MK/s][GPU 500.05 MK/s][Count 2^37.16][Dead 0][05:54 (Avg 14:21)][362.5MB] 
Key# 0 Pub:  0x0340CC040279AB29CD2201655D10D29A3986DC0BCA2BFCA8D0E497875CB70276E3
       Priv: 0x60B371918170B1249281CB73F3FA28F4747625CCC9E0C20D914856977B74D6DB
[500.11 MK/s][GPU 500.11 MK/s][Count 2^39.05][Dead 1][21:52 (Avg 14:21)][1331.5MB] 
Key# 1 Pub:  0x03B20790C29B02D2B60C71114212210B2077FF1455A3C8B88D2A3622A833E07575
       Priv: 0x60B371918170B1249281CB73F3FA28F4747625CCC9E0BDCC1ECE1B5FADED5D1C
[500.05 MK/s][GPU 500.05 MK/s][Count 2^38.37][Dead 0][13:39 (Avg 14:21)][831.6MB] 
Key# 2 Pub:  0x0341F04243CAFFD267015DE7AFB7C9EA9A865C370A68F15D651AC3A99965D123E4
       Priv: 0x60B371918170B1249281CB73F3FA28F4747625CCC9E0C45EC3C6E480E8A55497
[500.06 MK/s][GPU 500.06 MK/s][Count 2^36.83][Dead 0][04:48 (Avg 14:21)][289.4MB] 
Key# 3 Pub:  0x03413EB0010FFE249909932574DF7EF46DC2FDF2BE98A95DD935EF25D668694607
       Priv: 0x60B371918170B1249281CB73F3FA28F4747625CCC9E0C4744736D7B854B92A35
[498.01 MK/s][GPU 498.01 MK/s][Count 2^39.23][Dead 4][24:59 (Avg 14:24)][1511.5MB] 
Key# 4 Pub:  0x026DC089D162150F80D761E89D97BF65BA6CC055B1E073B9F163CBC02F19EE8D99
       Priv: 0x60B371918170B1249281CB73F3FA28F4747625CCC9E0C56A49FB165E7A2AED37

Done: Total time 01:11:51

-------------------------------------------------------------------------------------------------------------

$ ./kangaroo -gpu -t 0 in75adj.txt
Kangaroo v1.4beta
Start:0
Stop :7FFFFFFFFFFFFFFFFFF
Keys :5
Number of CPU thread: 0
Range width: 2^75
Jump Avg distance: 2^37.03
Number of kangaroos: 2^20.81
Suggested DP: 15
Expected operations: 2^38.65
Expected RAM: 1003.7MB
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 9870.3ms
[500.26 MK/s][GPU 500.26 MK/s][Count 2^37.94][Dead 0][10:17 (Avg 14:20)][619.1MB] 
Key# 0 Pub:  0x039A46F43EDB844F4F54A3FC3AD11F2AAC07F685E02CCB4885702975F43F91C8D2
       Priv: 0x480C2220BB3B0AD89B7
[497.96 MK/s][GPU 497.96 MK/s][Count 2^39.31][Dead 0][26:21 (Avg 14:24)][1594.2MB] 
Key# 1 Pub:  0x023CD0633B267FE3BF2BD43BFEB9101D462D85762447FCA7680D278EFA279E3B89
       Priv: 0x3F4FA7D07BE3260FF8
[498.21 MK/s][GPU 498.21 MK/s][Count 2^38.68][Dead 2][17:00 (Avg 14:24)][1033.2MB] 
Key# 2 Pub:  0x02FFB7FD0CDC140827726EF767A200789381B06E43B5607F7415B0902F6E654323
       Priv: 0x6D1F4A0999D1DDE0773
[498.03 MK/s][GPU 498.03 MK/s][Count 2^39.71][Dead 6][34:26 (Avg 14:24)][2096.6MB] 
Key# 3 Pub:  0x03875C234A56573A419FF84DE5F1788D02A363FA540A7E96EFFEF5901C595D1296
       Priv: 0x6E778108CD489F1DD11
[499.74 MK/s][GPU 499.74 MK/s][Count 2^37.33][Dead 0][06:46 (Avg 14:21)][408.5MB] 
Key# 4 Pub:  0x03352919782690011501EB26A6774E3CC55BA150EF91804F6A4BFC2F7005AF3BE2
       Priv: 0x7DD7AD4CB7AAF63A013

Done: Total time 01:35:36


But strange, I shifted the range (together with the public keys of course) to 0 (deducted start range) and expected that the 5 keys would be found faster or for the same time, but actually they were foound for a longer time.

If you shift the range [a,b] -> [-(b-a)/2, (b-a)/2], each point P in this interval has the property that -P is in interval too. No other operations are needed.

I beleive this shift could make the calcualtions faster... We easily implement the symmetry (!)

Jean_Luc, is it easy to implement such shift of the range? Or just make such shift optional...
The whole range is not length, but a wheel Smiley Let us spin this wheel and set the center of the range to the Zero point  Wink