Interesting... But how (why?) does this reduction work 2^116->2^58?
Does it mean that if I have for example private key in a range 2^144 and if I know public key then problem is reduced to 2^77?
Willing to learn more about it ;-)
For that key is more suitable Pollard's Kangaroo method. At current time, it is still uncrackable in years.
Yes, of course; it was just an example - to see the possible approach.
It means that exposing public key changes really a lot...
it really does not.
brute forcing has always been about reducing the space you need to search. having the public key only changes the method but it will never reduce the search space. you still have to search the 256 bit space by only having the public key.
this puzzle was possible to brute force because it first reduces the search space to 144 bits then reduces it a little more by the last hint down to 116 bits. and finally with symmetry the search space is reduced down to half that value meaning 58-bits.