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

Is there a way to check if a given Elliptic-curve in a finite field has an element with a certain

$x$ value?

asked 4 years ago

maan
27 ●2 ●4 ●8

updated 2 years ago

FrédéricC

5426 ●4 ●44 ●121

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)

answered 4 years ago

Max Alekseyev

6932 ●9 ●52 ●162

updated 4 years ago

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).

link

Comments

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.

maan ( 4 years ago )

You are welcome!

Max Alekseyev ( 4 years ago )

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

Commonplaces ( 3 years ago )

add a comment

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

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

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

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

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

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