Can I know from a Bitcoin public key if the private key is odd or even?

Can I know just from a Bitcoin public key if the private key is odd or even?

[moderator note] That is, can we find parity of the private key from a secp256k1 public key?
For the original dump of digits, see here.

Can I know just from a Bitcoin public key if the private key is odd or even?

We hope you can't; if you can, then you can solve the discrete log problem, that is, find the entire private key.

In cryptographical terminology, we say that the lsbit of the private key is a "hard core" bit, as it is as hard to recover as the entire value.

How it is done is straight-forward (at least, in the nonprobabilistic case, where your 'find-the-lsbit' algorithm always returns the correct answer); it works as follows $\log(q)$ times:

• Take the public key $Y$ and use your algorithm to find the lsbit of the private key; this gives us the lsbit of the private key $y$.

• If that lsbit was a '1', then replace $Y := Y - G$; this has the effect of replacing $y$ with $y-1$

• Then, replace $Y := [2^{-1}] Y$, that is, do a point multiplication with the inverse of 2 (which exists, because the curve has an odd order); this has the effect of replacing $y$ with $y/2$.

By doing this $\log(p)$ times, this reads off the bits of the private exponent in lsbit-first order; giving us the entire value.