I'm working on a project with elliptic curve cryptography (ECC), I'm using the secp256k1 library (the one that's used in bitcoin).
My goal is to create the most compact platform-independent representation of an elliptic curve point.
Currently my encoding consists of an
x-coordinate, 256 bits wide, encoded in a big-endian form, plus the sign (oddity) bit for the y-coordinate. In order to reconstruct the point I use the curve equation to receive the value for the
y^2, and then find the square root. Though calculating square root isn't trivial, this enables to pass only a single bit for
Now I'm thinking to get rid of this bit too. I realize that it's just 0.4% of the data, but for casual point (part of some bigger data set) it's usually aligned to the byte boundary, so it's practically around 3%. Anyway, I'd like to see if/how this is possible.
The idea is that for
y there's a solution for (roughly) half values of
x, so I thought about using this fact. So that if, for example, there's a solution for the encoded
x then even
y is selected. Otherwise there should be some transformation for
x, and then odd
y is selected.
Is there a way to quickly calculate the "counter-part" of
x, i.e. some unique transformation from
x which will give the quadratic residue for
x which will not, and vice-versa?