ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 21 Apr 2021 09:08:58 +0200Is there a way to check if a given Elliptic-curve in a finite field has an element with a certain $x$ value?https://ask.sagemath.org/question/56090/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)Wed, 10 Mar 2021 00:11:08 +0100https://ask.sagemath.org/question/56090/is-there-a-way-to-check-if-a-given-elliptic-curve-in-a-finite-field-has-an-element-with-a-certain-x-value/Answer by Max Alekseyev for <p>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.</p>
<pre><code>E = EllipticCurve(GF(43),[2,8]);
E.order();
E.gens();
E.random_element()
</code></pre>
<p>But is there a way to check if the EC contains a point with a given x-coordinate?</p>
<p>(which returns a point including the y-coordinate as well)</p>
<p>Or as alternative a function which searches for a point closest to a given x value.</p>
<p>(For small EC I could just search among all elements but target usage is an EC with very high order)</p>
https://ask.sagemath.org/question/56090/is-there-a-way-to-check-if-a-given-elliptic-curve-in-a-finite-field-has-an-element-with-a-certain-x-value/?answer=56091#post-id-56091The 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).Wed, 10 Mar 2021 00:46:44 +0100https://ask.sagemath.org/question/56090/is-there-a-way-to-check-if-a-given-elliptic-curve-in-a-finite-field-has-an-element-with-a-certain-x-value/?answer=56091#post-id-56091Comment by Commonplaces for <p>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:</p>
<pre><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) )
</code></pre>
<p>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).</p>
https://ask.sagemath.org/question/56090/is-there-a-way-to-check-if-a-given-elliptic-curve-in-a-finite-field-has-an-element-with-a-certain-x-value/?comment=56751#post-id-56751Yes thank you for this, I somehow expected that this would a basic method of the elliptic curve object.Wed, 21 Apr 2021 09:08:58 +0200https://ask.sagemath.org/question/56090/is-there-a-way-to-check-if-a-given-elliptic-curve-in-a-finite-field-has-an-element-with-a-certain-x-value/?comment=56751#post-id-56751Comment by Max Alekseyev for <p>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:</p>
<pre><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) )
</code></pre>
<p>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).</p>
https://ask.sagemath.org/question/56090/is-there-a-way-to-check-if-a-given-elliptic-curve-in-a-finite-field-has-an-element-with-a-certain-x-value/?comment=56094#post-id-56094You are welcome!Wed, 10 Mar 2021 02:55:54 +0100https://ask.sagemath.org/question/56090/is-there-a-way-to-check-if-a-given-elliptic-curve-in-a-finite-field-has-an-element-with-a-certain-x-value/?comment=56094#post-id-56094Comment by maan for <p>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:</p>
<pre><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) )
</code></pre>
<p>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).</p>
https://ask.sagemath.org/question/56090/is-there-a-way-to-check-if-a-given-elliptic-curve-in-a-finite-field-has-an-element-with-a-certain-x-value/?comment=56093#post-id-56093Thank 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.Wed, 10 Mar 2021 02:40:14 +0100https://ask.sagemath.org/question/56090/is-there-a-way-to-check-if-a-given-elliptic-curve-in-a-finite-field-has-an-element-with-a-certain-x-value/?comment=56093#post-id-56093