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