Re: Pollard's kangaroo ECDLP solver

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