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

asked 2021-03-10 00:11:08 +0100

maan
27 ●2 ●4 ●8

updated 2023-01-10 11:11:43 +0100

FrédéricC

5311 ●4 ●44 ●118

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 2021-03-10 00:46:44 +0100

Max Alekseyev

6540 ●9 ●47 ●154

updated 2021-03-10 01:09:35 +0100

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

edit flag offensive delete 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 ( 2021-03-10 02:40:14 +0100 )edit

You are welcome!

Max Alekseyev ( 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.

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

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 $x$ value? edit

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?