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 y.
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 y to x which will not, and vice-versa?
x. $\endgroup$ – valdo Jun 3 '18 at 9:11