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

• Note to the OP: questions consisting mostly of ciphertext are off-topic.
– fgrieu
Nov 25 at 19:48

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.