# 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 +0200 )edit

You are welcome!

( 2021-03-10 02:55:54 +0200 )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 +0200 )edit