Ask Your Question
0

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 +0200

maan gravatar image

updated 2021-03-10 02:35:39 +0200

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 flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
2

answered 2021-03-10 00:46:44 +0200

Max Alekseyev gravatar image

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

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 more

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 gravatar imagemaan ( 2021-03-10 02:40:14 +0200 )edit

You are welcome!

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

Commonplaces gravatar imageCommonplaces ( 2021-04-21 09:08:58 +0200 )edit

Your Answer

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

Add Answer

Question Tools

2 followers

Stats

Asked: 2021-03-10 00:11:08 +0200

Seen: 89 times

Last updated: Mar 10