# Is there an economic way to check if an eliptic curve point in jacobian coordiate is the same as a compressed point

On an elliptic curve such as $y^2 = x^3 + b$, we define $a$ compressed point $P = (x, y)$ by it's coordinate $x$ and the parity of the $y$ coordinate. $y$ can be computed using $y = \pm\sqrt{x^3 + b}$ and choosing the right value of $y$ using the parity information.

We also define a point in Jacobian coordinate such as $P = (a, b, z)$ with $x = a / z^2$ and $y = b / z^3$ .

I would like to know if there is a known way to check if 2 points in these two set of coordinates are the same point that is cheap. Computing if the $x$ coordinates are the same is easy by checking if $x * z^2 = a$ .

To check if the $y$ coordinate are the same, the best I can come up with is to compute $y = a * z^{-3}$ and check if it has the same parity as the compressed point. However, it requires an expensive computation of the multiplicative inverse of $z$ to get $z^{-1}$. This seems rather overkill as it compute way more information than required. Only one bit is needed.

I was wondering if there is a known way to check if thee 2 points are the same that do not involve expensive computations such as the finding multiplicative inverse or a quadratic residue to decompress the point.

• Obvious question: are you sure you need to check the $y$ coordinate? For some protocols (e.g. ECDH, where the shared secret consists of only the $x$ coordinate), which $y$ coordinate you use literally does not matter. Of course, for other protocols, which $y$ coordinate you use is essential, and so your answer might be "yes, I'm sure..." – poncho Mar 20 '17 at 18:36
• Yes, for malleability reasons. However, indeed, I check the y only if the x do match, which avoids the need for inversion for invalid signatures. – deadalnix Mar 20 '17 at 20:33

Computing the $z^{-1}$ is very cheap. We can do this by Euclidean algorithm, and in logarithmic time. But you can set $z=1$ in projective coordination. This make computations easy($O(1)$ since $z^{-1}=1$), and with this representation you can see the equality of points evidently.
Note that, instead of computing $y=b*z^{-3}$ you can check $y*z^3=b$. In this state, you don't need to finding multiplicative inverse.
Also in powerful programs such as MAGMA, $z$ is equal to $1$, by default.
• Simple $\ne$ cheap... – poncho Mar 20 '17 at 19:00
• So, an $O(n^3)$ algorithm is "cheap"? That's obviously a meaning of cheap that I'm not familiar with... – poncho Mar 20 '17 at 20:16
• @poncho, $O(n^3)$ or $O(n^2)$? Note that, $n$ is a number of digits of number, and we are talking about elliptic curves. Is it not cheap? I computed the inverse of $100000$ bit numbers in less that millisecond, by MAGMA. I'm sorry, maybe I don't know the meaning of cheap. – Meysam Ghahramani Mar 20 '17 at 20:48