# Is there a way to check if a given Elliptic-curve in a finite field has an element with a certain $x$ value?

Hi, I already found out how to generate an elliptic curve in a finite field in sagemath. How to get its oder, an element and some more. E.g.

E = EllipticCurve(GF(43),[2,8]);
E.order();
E.gens();
E.random_element()


But is there a way to check if the EC contains a point with a given x-coordinate?

(which returns a point including the y-coordinate as well)

Or as alternative a function which searches for a point closest to a given x value.

(For small EC I could just search among all elements but target usage is an EC with very high order)

edit retag close merge delete

Sort by » oldest newest most voted

The question amounts to substituting given $x$ in the elliptic curve equation, and solving the resulting quadratic equation for $y$. Here is a sample code:

def compute_y(E,x):
R.<y> = PolynomialRing(E.base_ring())
a = E.a_invariants()
L = (y^2 + (a[0]*x + a[2])*y - (x^3 + a[1]*x^2 + a[3]*x + a[4])).roots()
return {l[0] for l in L}

E = EllipticCurve(GF(43),[2,8])
print( compute_y(E,1) )


For a given curve and $x=1$, it computes that $y\in \{21,22\}$. It is easy to verify that $21^2 = 22^2 = 1^3 + 2\cdot 1 + 8$ and in GF(43).

more

Thank you very much. Forgot to say I'm new to sage math. Fascinating it is. I didn't knew it can be converted to a polynomial ring and than just roots(). As simple as that. Very nice.

( 2021-03-10 02:40:14 +0100 )edit

You are welcome!

( 2021-03-10 02:55:54 +0100 )edit

Yes thank you for this, I somehow expected that this would a basic method of the elliptic curve object.

( 2021-04-21 09:08:58 +0100 )edit