-snip-
for you 1000 pubkeys in 54 bit range total time for check ?
i don`t know how many time was spent for test but calc say that need average time 2^ 3.8s for 1 Pub with 20Mop/s on CPUfor you 1000 pubkeys in 54 bit range total time for check ?
Topic: Pollard's kangaroo ECDLP solver - page 95. (Read 59389 times)
-snip-
Etar
if i am not wrong
you have 49 bit 1000 pubkeys
you shift dp file to 54 bit
and you have this info
" Expected operations 2^28.06, Total op was 261530636052 = 2^37.93 "
if i am not wrong you total op 2^38 work = to search 1 pubkey in 2^76 bitrange
76 bit = 75557863725914323419135
54 bit = 18014398509481983
distance = 4194303 for 1000 pub key
and for 1 pubkey = 419.4303
and for 32*g = 134217.72
in short you used tooo much time as compare to equal 76 bit work
hope u understand
2^37.93 for ALL pubkeysEtar
if i am not wrong
you have 49 bit 1000 pubkeys
you shift dp file to 54 bit
and you have this info
" Expected operations 2^28.06, Total op was 261530636052 = 2^37.93 "
if i am not wrong you total op 2^38 work = to search 1 pubkey in 2^76 bitrange
76 bit = 75557863725914323419135
54 bit = 18014398509481983
distance = 4194303 for 1000 pub key
and for 1 pubkey = 419.4303
and for 32*g = 134217.72
in short you used tooo much time as compare to equal 76 bit work
hope u understand
for 1 pubkeys average op is 2^27.98
And i didn`t have 1000pubkeys in 49bit range. I solve 1 keys and convert work file to range 54bit.
In 54bit i solve 1000pubkeys
-snip-
run any random pubkey for 76 bit, and see you need these 2^37.93 for finish
Range 2^ 54.0run any random pubkey for 76 bit, and see you need these 2^37.93 for finish
Expected OP 2^ 28.054231864896956
Range 2^ 76.0
Expected OP 2^ 39.05419477968964
@JeanLuc make please option for save all dead kangaroo to .txt file in readable format ? This is needed information for understand mistake with ranges and -d param.
@JeanLuc and make please counting +/- dead kangaroo: [Dead 10] -> [Dead total: 10 ["+" 8, "-" 2 ]]
BR.
@JeanLuc and make please counting +/- dead kangaroo: [Dead 10] -> [Dead total: 10 ["+" 8, "-" 2 ]]
BR.
@JeanLuc
Buddy, will you reliase this ?
BR
The best time complexity with the birthday paradox and kangaroo having a starting position uniformly distributed in [0..N] is obtained when drawing alternatively one tame and one wild. When using DP0, you get ~2.sqrt(N). When using DPx, it is like drawing alternatively 2^x TAME and then 2^x WILD, you have then a DP overhead.
I managed to get the formula for parallel version which is: ~2.CubicRoot( N (k.theta + sqrt(N)) ) where theta=2^dpbit and k the number of kangaroo-2 running in parallel.
For theta=1 (DP0) and k=0 (or when k.theta << sqrt(N)) we well get ~2.sqrt(N), when k.theta >> sqrt(N), the time complexity tend to ~2.CubicRoot(k.N.theta).
So it is important to choose a DP such as k.theta << sqrt(N).
I managed to get the formula for parallel version which is: ~2.CubicRoot( N (k.theta + sqrt(N)) ) where theta=2^dpbit and k the number of kangaroo-2 running in parallel.
For theta=1 (DP0) and k=0 (or when k.theta << sqrt(N)) we well get ~2.sqrt(N), when k.theta >> sqrt(N), the time complexity tend to ~2.CubicRoot(k.N.theta).
So it is important to choose a DP such as k.theta << sqrt(N).
Great work!
The number of kangaroos running in parallel transforms DP (that means less RAM) in a overhead.
For the #120, if you and Zielar use 2^30 kangaroos, you need to use a DP < 28.
The problem is: how fast is a single kangaroo? You can't 'concentrate' the speed of several kangaroo in more speed for one. And it takes a lot for a single kangaroo to walk through a path of length = 2^28.
If you reduce k, you reduce the speed, then you have to reduce theta (DP).
How many kangaroos run in parallel on a single V100 ? At wich speed?
-snip-
Etar
if i am not wrong
you have 49 bit 1000 pubkeys
you shift dp file to 54 bit
and you have this info
" Expected operations 2^28.06, Total op was 261530636052 = 2^37.93 "
if i am not wrong you total op 2^38 work = to search 1 pubkey in 2^76 bitrange
76 bit = 75557863725914323419135
54 bit = 18014398509481983
distance = 4194303 for 1000 pub key
and for 1 pubkey = 419.4303
and for 32*g = 134217.72
in short you used tooo much time as compare to equal 76 bit work
hope u understand
2^37.93 for ALL pubkeysEtar
if i am not wrong
you have 49 bit 1000 pubkeys
you shift dp file to 54 bit
and you have this info
" Expected operations 2^28.06, Total op was 261530636052 = 2^37.93 "
if i am not wrong you total op 2^38 work = to search 1 pubkey in 2^76 bitrange
76 bit = 75557863725914323419135
54 bit = 18014398509481983
distance = 4194303 for 1000 pub key
and for 1 pubkey = 419.4303
and for 32*g = 134217.72
in short you used tooo much time as compare to equal 76 bit work
hope u understand
for 1 pubkeys average op is 2^27.98
And i didn`t have 1000pubkeys in 49bit range. I solve 1 keys and convert work file to range 54bit.
In 54bit i solve 1000pubkeys
-snip-
Etar
if i am not wrong
you have 49 bit 1000 pubkeys
you shift dp file to 54 bit
and you have this info
" Expected operations 2^28.06, Total op was 261530636052 = 2^37.93 "
if i am not wrong you total op 2^38 work = to search 1 pubkey in 2^76 bitrange
76 bit = 75557863725914323419135
54 bit = 18014398509481983
distance = 4194303 for 1000 pub key
and for 1 pubkey = 419.4303
and for 32*g = 134217.72
in short you used tooo much time as compare to equal 76 bit work
hope u understand
2^37.93 for ALL pubkeysEtar
if i am not wrong
you have 49 bit 1000 pubkeys
you shift dp file to 54 bit
and you have this info
" Expected operations 2^28.06, Total op was 261530636052 = 2^37.93 "
if i am not wrong you total op 2^38 work = to search 1 pubkey in 2^76 bitrange
76 bit = 75557863725914323419135
54 bit = 18014398509481983
distance = 4194303 for 1000 pub key
and for 1 pubkey = 419.4303
and for 32*g = 134217.72
in short you used tooo much time as compare to equal 76 bit work
hope u understand
for 1 pubkeys average op is 2^27.98
And i didn`t have 1000pubkeys in 49bit range. I solve 1 keys and convert work file to range 54bit.
In 54bit i solve 1000pubkeys. And work file will the same for each pubkeys i didn`t append DP to file while solving range 54bit.
-snip-
The gain (- 5,4%) is little, how many DPs have you generated for the key in 49 bit?
-snip-
DP Count : 240568 2^17.876 in 49bit workfile. i have source file and converted file. I can share if you want to verify DPs. But each DP after multiplication was verifed with G' and x-coordinate correct.The gain (- 5,4%) is little, how many DPs have you generated for the key in 49 bit?
-snip-
Code:
DP bits : 8
Start : 40000000000000
Stop : 7FFFFFFFFFFFFF
Key : 025C396BA4347253BBAAFFAC6D4F9BA092847B27F2599EB2EB225DDA54F9964190
Count : 0 2^-inf
Time : 00s
DP Size : 9.3/30.6MB
DP Count : 240568 2^17.876
HT Max : 8 [@ 01D30E]
HT Min : 0 [@ 000001]
HT Avg : 0.92
HT SDev : 0.95
Start : 40000000000000
Stop : 7FFFFFFFFFFFFF
Key : 025C396BA4347253BBAAFFAC6D4F9BA092847B27F2599EB2EB225DDA54F9964190
Count : 0 2^-inf
Time : 00s
DP Size : 9.3/30.6MB
DP Count : 240568 2^17.876
HT Max : 8 [@ 01D30E]
HT Min : 0 [@ 000001]
HT Avg : 0.92
HT SDev : 0.95
-snip-
"Total op was 261530636052 = 2^37.93" this for 1000 pubkey or only one ?
For 1000 pubkeys"Total op was 261530636052 = 2^37.93" this for 1000 pubkey or only one ?
-snip-
Etar, this is a CPU or GPU version ?
Test done on CPUEtar, this is a CPU or GPU version ?
if i am not wrong
you have 49 bit 1000 pubkeys
you shift dp file to 54 bit
and you have this info
" Expected operations 2^28.06, Total op was 261530636052 = 2^37.93 "
if i am not wrong you total op 2^38 work = to search 1 pubkey in 2^76 bitrange
76 bit = 75557863725914323419135
54 bit = 18014398509481983
distance = 4194303 for 1000 pub key
and for 1 pubkey = 419.4303
and for 32*g = 134217.72
in short you used tooo much time as compare to equal 76 bit work
hope u understand
The best time complexity with the birthday paradox and kangaroo having a starting position uniformly distributed in [0..N] is obtained when drawing alternatively one tame and one wild. When using DP0, you get ~2.sqrt(N). When using DPx, it is like drawing alternatively 2^x TAME and then 2^x WILD, you have then a DP overhead.
I managed to get the formula for parallel version which is: ~2.CubicRoot( N (k.theta + sqrt(N)) ) where theta=2^dpbit and k the number of kangaroo-2 running in parallel.
For theta=1 (DP0) and k=0 (or when k.theta << sqrt(N)) we well get ~2.sqrt(N), when k.theta >> sqrt(N), the time complexity tend to ~2.CubicRoot(k.N.theta).
So it is important to choose a DP such as k.theta << sqrt(N).
In that case best choice for solving keys is using CPU I managed to get the formula for parallel version which is: ~2.CubicRoot( N (k.theta + sqrt(N)) ) where theta=2^dpbit and k the number of kangaroo-2 running in parallel.
For theta=1 (DP0) and k=0 (or when k.theta << sqrt(N)) we well get ~2.sqrt(N), when k.theta >> sqrt(N), the time complexity tend to ~2.CubicRoot(k.N.theta).
So it is important to choose a DP such as k.theta << sqrt(N).
i7 7 thread 20Mop/s and 7168 kangaroos
2080ti 1.4Gop/s and 4464292 kangaroos
1.4Gop/s / 20Mop/s = 70 CPU the same speed but also only 501760 Kangaroos, 8.9 times less DP overhead.
The best time complexity with the birthday paradox and kangaroo having a starting position uniformly distributed in [0..N] is obtained when drawing alternatively one tame and one wild. When using DP0, you get ~2.sqrt(N). When using DPx, it is like drawing alternatively 2^x TAME and then 2^x WILD, you have then a DP overhead.
I managed to get the formula for parallel version which is: ~2.CubicRoot( N (k.theta + sqrt(N)) ) where theta=2^dpbit and k the number of kangaroo-2 running in parallel.
For theta=1 (DP0) and k=0 (or when k.theta << sqrt(N)) we well get ~2.sqrt(N), when k.theta >> sqrt(N), the time complexity tend to ~2.CubicRoot(k.N.theta).
So it is important to choose a DP such as k.theta << sqrt(N).
I managed to get the formula for parallel version which is: ~2.CubicRoot( N (k.theta + sqrt(N)) ) where theta=2^dpbit and k the number of kangaroo-2 running in parallel.
For theta=1 (DP0) and k=0 (or when k.theta << sqrt(N)) we well get ~2.sqrt(N), when k.theta >> sqrt(N), the time complexity tend to ~2.CubicRoot(k.N.theta).
So it is important to choose a DP such as k.theta << sqrt(N).
-snip-
To get 2^27.98, it is like 2^25.876 was worth about 2^21.8, the effect of reuse of old DPs is reduced by a factor of 16.
I think that for birthday paradox is a big difference between have 16Tame DP and 2 wild DP or 9tame and 9wild.To get 2^27.98, it is like 2^25.876 was worth about 2^21.8, the effect of reuse of old DPs is reduced by a factor of 16.
Maybe if Kangaroo app first launch wild (as you say somewhere above) gain the same amount as tame DPs maybe in this case we will have faster result.
Yes, but in that case there is no big difference:
(2^x + 2^25.876) tame * (2^x + 2^25.876) wild = 2^54 couples
2^x + 2^25.876 = 2^27
x = log2(2^27-2^25.876) = 26.1
--> only 2^26.1 tame + 2^26.1 wild + 2^25.876 wild steps are needed -> 2^27.61
-snip-
To get 2^27.98, it is like 2^25.876 was worth about 2^21.8, the effect of reuse of old DPs is reduced by a factor of 16.
I think that for birthday paradox is a big difference between have 16Tame DP and 2 wild DP or 9tame and 9wild.To get 2^27.98, it is like 2^25.876 was worth about 2^21.8, the effect of reuse of old DPs is reduced by a factor of 16.
Maybe if Kangaroo app first launch wild (as you say somewhere above) gain the same amount as tame DPs maybe in this case we will have faster result.
-snip-
The gain (- 5,4%) is little, how many DPs have you generated for the key in 49 bit?
-snip-
DP Count : 240568 2^17.876 in 49bit workfileThe gain (- 5,4%) is little, how many DPs have you generated for the key in 49 bit?
-snip-
Then you have computed 2^17.876 * 2^8 = 2^25.876 points,
(2^x + 2^25.876) tame * (2^x) wild = 2^54 couples
--> x = 26.67
In theory it would be enough 2^27.67 steps instead of 2^27.98.
To get 2^27.98, it is like 2^25.876 was worth about 2^21.8, the effect of reuse of old DPs is reduced by a factor of 16.
"For 1000 pubkeys"
Think I not understand something but, for 1000 pubkeys 2^37.93 is very fast.
expected op for 1 pub = 2^28.06Think I not understand something but, for 1000 pubkeys 2^37.93 is very fast.
1000 pubkeys ~2^ 9.965
2^28.06*2^9.965=(28.06+9.965)=2^38.025
So 2^37.93 is little-little bit faster then expected
"For 1000 pubkeys"
Think I not understand something but, for 1000 pubkeys 2^37.93 is very fast.
Think I not understand something but, for 1000 pubkeys 2^37.93 is very fast.
-snip-
The gain (- 5,4%) is little, how many DPs have you generated for the key in 49 bit?
-snip-
DP Count : 240568 2^17.876 in 49bit workfile. i have source file and converted file. I can share if you want to verify DPs. But each DP after multiplication was verifed with G' and x-coordinate correct.The gain (- 5,4%) is little, how many DPs have you generated for the key in 49 bit?
-snip-
Code:
DP bits : 8
Start : 40000000000000
Stop : 7FFFFFFFFFFFFF
Key : 025C396BA4347253BBAAFFAC6D4F9BA092847B27F2599EB2EB225DDA54F9964190
Count : 0 2^-inf
Time : 00s
DP Size : 9.3/30.6MB
DP Count : 240568 2^17.876
HT Max : 8 [@ 01D30E]
HT Min : 0 [@ 000001]
HT Avg : 0.92
HT SDev : 0.95
Start : 40000000000000
Stop : 7FFFFFFFFFFFFF
Key : 025C396BA4347253BBAAFFAC6D4F9BA092847B27F2599EB2EB225DDA54F9964190
Count : 0 2^-inf
Time : 00s
DP Size : 9.3/30.6MB
DP Count : 240568 2^17.876
HT Max : 8 [@ 01D30E]
HT Min : 0 [@ 000001]
HT Avg : 0.92
HT SDev : 0.95
-snip-
"Total op was 261530636052 = 2^37.93" this for 1000 pubkey or only one ?
For 1000 pubkeys"Total op was 261530636052 = 2^37.93" this for 1000 pubkey or only one ?
-snip-
Etar, this is a CPU or GPU version ?
Test done on CPU Etar, this is a CPU or GPU version ?
@arulbero test with 1000 pub keys fulfilled.
Workfile taken from puzzle 49 bit and prepared to work in the range 54 bit.
Each wild DPs tamed. All DPs multipled by 32 and checked (x-coordinate was correct when distance*G' )
-xbit was 5 so G'=G*inv(32) = (bb2228d3ea32cb3c1eb160cc824a4ba8115f9a7f415d18ddcaac8193defc2c47,71f8c9c7cc35f99b8b2abcdcab86d12cb7539b3fbb45bc433b3bd9421b35be53)
1000 keys was generated in range 40000000000000:7fffffffffffff
Each pubkeys was multipled by inv(32) and solved with G'and Kangaroo v1.4
Expected operations 2^28.06
Total op was 261530636052 = 2^37.93
In average 2^27.98
Workfile taken from puzzle 49 bit and prepared to work in the range 54 bit.
Each wild DPs tamed. All DPs multipled by 32 and checked (x-coordinate was correct when distance*G' )
-xbit was 5 so G'=G*inv(32) = (bb2228d3ea32cb3c1eb160cc824a4ba8115f9a7f415d18ddcaac8193defc2c47,71f8c9c7cc35f99b8b2abcdcab86d12cb7539b3fbb45bc433b3bd9421b35be53)
1000 keys was generated in range 40000000000000:7fffffffffffff
Each pubkeys was multipled by inv(32) and solved with G'and Kangaroo v1.4
Expected operations 2^28.06
Total op was 261530636052 = 2^37.93
In average 2^27.98
Many thanks.
The gain (- 5,7%) is little, how many DPs did you have generate for the key in 49 bit?
Etar, this is a CPU or GPU version ?
@arulbero test with 1000 pub keys fulfilled.
Workfile taken from puzzle 49 bit and prepared to work in the range 54 bit.
Each wild DPs tamed. All DPs multipled by 32 and checked (x-coordinate was correct when distance*G' )
-xbit was 5 so G'=G*inv(32) = (bb2228d3ea32cb3c1eb160cc824a4ba8115f9a7f415d18ddcaac8193defc2c47,
71f8c9c7cc35f99b8b2abcdcab86d12cb7539b3fbb45bc433b3bd9421b35be53)
1000 keys was generated in range 40000000000000:7fffffffffffff
Each pubkeys was multipled by inv(32) and solved with G'and Kangaroo v1.4
Expected operations 2^28.06
Total op was 261530636052 = 2^37.93
In average 2^27.98
Workfile taken from puzzle 49 bit and prepared to work in the range 54 bit.
Each wild DPs tamed. All DPs multipled by 32 and checked (x-coordinate was correct when distance*G' )
-xbit was 5 so G'=G*inv(32) = (bb2228d3ea32cb3c1eb160cc824a4ba8115f9a7f415d18ddcaac8193defc2c47,
71f8c9c7cc35f99b8b2abcdcab86d12cb7539b3fbb45bc433b3bd9421b35be53)
1000 keys was generated in range 40000000000000:7fffffffffffff
Each pubkeys was multipled by inv(32) and solved with G'and Kangaroo v1.4
Expected operations 2^28.06
Total op was 261530636052 = 2^37.93
In average 2^27.98
Many thanks.
The gain (- 5,4%) is little, how many DPs have you generated for the key in 49 bit?
If you have generated 2^25.08 points, then:
(2^x + 2^25.08) tame * (2^x) wild = 2^54 couples
2^(2x) + 2^(25.08)*2^x - 2^54 = 0
--> x = 2^26.81
Then you should have computed on average 2^26.81 tame-steps + 2^26.81 wild-steps = 2^27.81 steps
@arulbero test with 1000 pub keys fulfilled.
Workfile taken from puzzle 49 bit and prepared to work in the range 54 bit.
Each wild DPs tamed. All DPs multipled by 32 and checked (x-coordinate was correct when distance*G' )
-xbit was 5 so G'=G*inv(32) = (bb2228d3ea32cb3c1eb160cc824a4ba8115f9a7f415d18ddcaac8193defc2c47,71f8c9c7cc35f99b8b2abcdcab86d12cb7539b3fbb45bc433b3bd9421b35be53)
1000 keys was generated in range 40000000000000:7fffffffffffff
Each pubkeys was multipled by inv(32) and solved with G'and Kangaroo v1.4
Expected operations 2^28.06
Total op was 261530636052 = 2^37.93
In average 2^27.98
Workfile taken from puzzle 49 bit and prepared to work in the range 54 bit.
Each wild DPs tamed. All DPs multipled by 32 and checked (x-coordinate was correct when distance*G' )
-xbit was 5 so G'=G*inv(32) = (bb2228d3ea32cb3c1eb160cc824a4ba8115f9a7f415d18ddcaac8193defc2c47,71f8c9c7cc35f99b8b2abcdcab86d12cb7539b3fbb45bc433b3bd9421b35be53)
1000 keys was generated in range 40000000000000:7fffffffffffff
Each pubkeys was multipled by inv(32) and solved with G'and Kangaroo v1.4
Expected operations 2^28.06
Total op was 261530636052 = 2^37.93
In average 2^27.98
Hello
"Total op was 261530636052 = 2^37.93" this for 1000 pubkey or only one ?
@arulbero test with 1000 pub keys fulfilled.
Workfile taken from puzzle 49 bit and prepared to work in the range 54 bit.
Each wild DPs tamed. All DPs multipled by 32 and checked (x-coordinate was correct when distance*G' )
-xbit was 5 so G'=G*inv(32) = (bb2228d3ea32cb3c1eb160cc824a4ba8115f9a7f415d18ddcaac8193defc2c47,71f8c9c7cc35f99b8b2abcdcab86d12cb7539b3fbb45bc433b3bd9421b35be53)
1000 keys was generated in range 40000000000000:7fffffffffffff
Each pubkeys was multipled by inv(32) and solved with G'and Kangaroo v1.4
Expected operations 2^28.06
Total op was 261530636052 = 2^37.93
In average 2^27.98
Workfile taken from puzzle 49 bit and prepared to work in the range 54 bit.
Each wild DPs tamed. All DPs multipled by 32 and checked (x-coordinate was correct when distance*G' )
-xbit was 5 so G'=G*inv(32) = (bb2228d3ea32cb3c1eb160cc824a4ba8115f9a7f415d18ddcaac8193defc2c47,71f8c9c7cc35f99b8b2abcdcab86d12cb7539b3fbb45bc433b3bd9421b35be53)
1000 keys was generated in range 40000000000000:7fffffffffffff
Each pubkeys was multipled by inv(32) and solved with G'and Kangaroo v1.4
Expected operations 2^28.06
Total op was 261530636052 = 2^37.93
In average 2^27.98
Jump to: