Let's say we have a point on an elliptic curve $p=(x, y)$ which is not the point-at-infinity.

Can there be some other point $\hat{p} = (\hat{x}, y)$ that is also on the curve and that has the same y-coordinate, but a different x-coordinate (i.e. $x \neq \hat{x}$)?

Clearly, if the elliptic curve is over the real numbers, this is not the case (as can be seen by drawing a horizontal line between two saddle points). An example of a particular finite-field elliptic curve shows this can be the case for finite-field elliptic curves too.

Are there any finite-field elliptic curves for which points can be represented uniquely by their y-coordinate? If so, how can you determine whether, for a particular finite-field elliptic curve, a point can be represented uniquely by its y-coordinate. For instance, can this be done for secp256k1?

  • $\begingroup$ This is due to the square root, right? $\endgroup$ – kelalaka Sep 9 '19 at 19:53
  • $\begingroup$ @kelalaka The square root means that the same $x$ will have correspond to two different values of $y$. But I want to know whether the same $y$ will correspond to multiple values of $x$. $\endgroup$ – danxinnoble Sep 9 '19 at 20:15
  • 2
    $\begingroup$ When $p \equiv 2 \bmod 3$, cube roots are unique. $\endgroup$ – Samuel Neves Sep 9 '19 at 20:25
  • $\begingroup$ Thanks @SamuelNeves. Do you have a ref to a proof for that? So the statement holds when $p \equiv 2 \bmod 3$, does it only hold in this case? $\endgroup$ – danxinnoble Sep 9 '19 at 20:53
  • $\begingroup$ Actually, I think I figured out a proof. If prime $p \equiv 1 \bmod 3$, then $Z/pZ^*$ will be a cyclic group of order $p-1 \equiv 0 \bmod 3$. Therefore, if there is a generator $g$ then an element $a = g^\alpha$ will have three cubic roots $g^{\frac{\alpha}{3}}, g^{\frac{4\alpha}{3}}, g^{\frac{7\alpha}{3}}$ if $\alpha \equiv 0 \bmod 3$ and 0 otherwise. Whereas if $p \equiv 2 \bmod 3$, $p-1 \equiv 1 \bmod 3$ and the cubic root of $g^{\alpha}$ is uniquely defined as $g^{\alpha ^{-1} \bmod (p-1)}$ $\endgroup$ – danxinnoble Sep 9 '19 at 21:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.