Re: Pollard's kangaroo ECDLP solver

Quote from: Etar on Today at 09:07:22 PM

I think we can reduce the search range by 1 bit by shifting the initial range, and then shifting half the range.
For example, the 79bit puzzle is shifted to the 78bit range:

Code:

Start:0
Stop :3FFFFFFFFFFFFFFFFFFF
Range width: 2^78
[1405.94 MK/s][GPU 1405.94 MK/s][Count 2^38.90][Dead 0][06:55 (Avg 15:15)][481.5/608.4MB]
Key# 0 [1S]Pub: 0x02F65E6E18EAB67F86287D565702468C2F30A303F22EBDCEBE556C23D016350222
Priv: 0x2A1A5C66DCC11B5AD181 + 0x3fffffffffffffffffff + 0x80000000000000000000 = 0xea1a5c66dcc11b5ad180

without shifting:

Code:

Start:80000000000000000000
Stop :FFFFFFFFFFFFFFFFFFFF
Range width: 2^79
[1380.42 MK/s][GPU 1380.42 MK/s][Count 2^40.59][Dead 0][22:35 (Avg 21:15)][1541.1/1932.8MB]
Key# 0 [1S]Pub: 0x037E1238F7B1CE757DF94FAA9A2EB261BF0AEB9F84DBF81212104E78931C2A19DC
Priv: 0xEA1A5C66DCC11B5AD180

As you can see time and count less with shifting.
If pubkey appear "under zero" after shifting it is not a matter you any way will found key.

Here is example were pubkey is "below zero"
random key 0xbc690499fb50bfde866b

Code:

Start:0
Stop :3FFFFFFFFFFFFFFFFFFF
Range width: 2^78
[1390.34 MK/s][GPU 1390.34 MK/s][Count 2^40.00][Dead 0][14:53 (Avg 15:26)][1027.3/1290.6MB]
Key# 0 [1S]Pub: 0x02996740F4755163FB167F7D06875B3F415CD7AB9E2F198DE66E1E7D082086E64F
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF489CA4C46C59DD9014C7AD + 0x3fffffffffffffffffff + 0x80000000000000000000 = 0xbc690499fb50bfde866b

without shifting:

Code:

Start:80000000000000000000
Stop :FFFFFFFFFFFFFFFFFFFF
Range width: 2^79
[1385.36 MK/s][GPU 1385.36 MK/s][Count 2^39.90][Dead 1][13:54 (Avg 21:10)][957.7/1203.7MB]
Key# 0 [1S]Pub: 0x02D48BBCB4370DA5F3CD5FBC25D1052C8BAC97953C65FB4F837A423320FAE88CB4
Priv: 0xBC690499FB50BFDE866B

In last example without shifting little bit faster because pubkey was around the center of range.
Any way need few test..

Can you give details on how you are shifting? Interesting concept I'd like to learn more about. Thanks.