ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 27 Nov 2017 03:26:34 -0600Defining a subgroup of elliptic curves with specific characteristicshttp://ask.sagemath.org/question/39726/defining-a-subgroup-of-elliptic-curves-with-specific-characteristics/Hey,
is there a way, to define a subgroup of an elliptic curve with two or more characteristics? I would like to take an elliptic curve over a finite field of order p and $p^4$, define the r-torsion subgroup (where $r$ is a prime, too) and reduce those to the set of points, which also lays in the Frobenius-eigenspace.
For example:
p= 13
r=5
R=GF(p)
_.<x> = PolynomialRing(R)
R4.<x> = R.extension(x^4 - 2, 'x')
_.<y> = PolynomialRing(R)
b= x^-1
E = EllipticCurve(R, [1,0]) # y^2 = x^3+x
E4 = EllipticCurve(R4, [b,0])
Well, it is easy to find a point on $Q\in E4$, such that $r*Q = (0:1:0)$, use
Q=ZZ(E4.order()/r *Q
, but checking, if $( x(Q)^p, y(Q)^p )=\pi(Q) = pQ$ is hard. I only need one point of that group at all, but my $p$ is even larger (~340 bits), so brute-forcing would be an option, if I could start it 6-12 month ago :)
Furthermore, if I concider to evaluate the secant or tangent on E and let me return a point on that curve, it will have projective coordinates, with $z(P)\neq1$. Shall I apply $\pi$ to all three coordinates?Wed, 22 Nov 2017 07:16:18 -0600http://ask.sagemath.org/question/39726/defining-a-subgroup-of-elliptic-curves-with-specific-characteristics/Comment by Shalec for <p>Hey,</p>
<p>is there a way, to define a subgroup of an elliptic curve with two or more characteristics? I would like to take an elliptic curve over a finite field of order p and $p^4$, define the r-torsion subgroup (where $r$ is a prime, too) and reduce those to the set of points, which also lays in the Frobenius-eigenspace. </p>
<p>For example:</p>
<pre><code>p= 13
r=5
R=GF(p)
_.<x> = PolynomialRing(R)
R4.<x> = R.extension(x^4 - 2, 'x')
_.<y> = PolynomialRing(R)
b= x^-1
E = EllipticCurve(R, [1,0]) # y^2 = x^3+x
E4 = EllipticCurve(R4, [b,0])
</code></pre>
<p>Well, it is easy to find a point on $Q\in E4$, such that $r*Q = (0:1:0)$, use</p>
<pre><code>Q=ZZ(E4.order()/r *Q
</code></pre>
<p>, but checking, if $( x(Q)^p, y(Q)^p )=\pi(Q) = pQ$ is hard. I only need one point of that group at all, but my $p$ is even larger (~340 bits), so brute-forcing would be an option, if I could start it 6-12 month ago :)</p>
<p>Furthermore, if I concider to evaluate the secant or tangent on E and let me return a point on that curve, it will have projective coordinates, with $z(P)\neq1$. Shall I apply $\pi$ to all three coordinates?</p>
http://ask.sagemath.org/question/39726/defining-a-subgroup-of-elliptic-curves-with-specific-characteristics/?comment=39814#post-id-39814My Question is actually obsolet. I will add an answere and some miss-thoughts in the next days.Mon, 27 Nov 2017 03:26:34 -0600http://ask.sagemath.org/question/39726/defining-a-subgroup-of-elliptic-curves-with-specific-characteristics/?comment=39814#post-id-39814Comment by Shalec for <p>Hey,</p>
<p>is there a way, to define a subgroup of an elliptic curve with two or more characteristics? I would like to take an elliptic curve over a finite field of order p and $p^4$, define the r-torsion subgroup (where $r$ is a prime, too) and reduce those to the set of points, which also lays in the Frobenius-eigenspace. </p>
<p>For example:</p>
<pre><code>p= 13
r=5
R=GF(p)
_.<x> = PolynomialRing(R)
R4.<x> = R.extension(x^4 - 2, 'x')
_.<y> = PolynomialRing(R)
b= x^-1
E = EllipticCurve(R, [1,0]) # y^2 = x^3+x
E4 = EllipticCurve(R4, [b,0])
</code></pre>
<p>Well, it is easy to find a point on $Q\in E4$, such that $r*Q = (0:1:0)$, use</p>
<pre><code>Q=ZZ(E4.order()/r *Q
</code></pre>
<p>, but checking, if $( x(Q)^p, y(Q)^p )=\pi(Q) = pQ$ is hard. I only need one point of that group at all, but my $p$ is even larger (~340 bits), so brute-forcing would be an option, if I could start it 6-12 month ago :)</p>
<p>Furthermore, if I concider to evaluate the secant or tangent on E and let me return a point on that curve, it will have projective coordinates, with $z(P)\neq1$. Shall I apply $\pi$ to all three coordinates?</p>
http://ask.sagemath.org/question/39726/defining-a-subgroup-of-elliptic-curves-with-specific-characteristics/?comment=39803#post-id-39803Ok. Thinking about you mentioned behaviour delivers, that this can't work. I'll add a more precise question.Sun, 26 Nov 2017 14:52:29 -0600http://ask.sagemath.org/question/39726/defining-a-subgroup-of-elliptic-curves-with-specific-characteristics/?comment=39803#post-id-39803Comment by Shalec for <p>Hey,</p>
<p>is there a way, to define a subgroup of an elliptic curve with two or more characteristics? I would like to take an elliptic curve over a finite field of order p and $p^4$, define the r-torsion subgroup (where $r$ is a prime, too) and reduce those to the set of points, which also lays in the Frobenius-eigenspace. </p>
<p>For example:</p>
<pre><code>p= 13
r=5
R=GF(p)
_.<x> = PolynomialRing(R)
R4.<x> = R.extension(x^4 - 2, 'x')
_.<y> = PolynomialRing(R)
b= x^-1
E = EllipticCurve(R, [1,0]) # y^2 = x^3+x
E4 = EllipticCurve(R4, [b,0])
</code></pre>
<p>Well, it is easy to find a point on $Q\in E4$, such that $r*Q = (0:1:0)$, use</p>
<pre><code>Q=ZZ(E4.order()/r *Q
</code></pre>
<p>, but checking, if $( x(Q)^p, y(Q)^p )=\pi(Q) = pQ$ is hard. I only need one point of that group at all, but my $p$ is even larger (~340 bits), so brute-forcing would be an option, if I could start it 6-12 month ago :)</p>
<p>Furthermore, if I concider to evaluate the secant or tangent on E and let me return a point on that curve, it will have projective coordinates, with $z(P)\neq1$. Shall I apply $\pi$ to all three coordinates?</p>
http://ask.sagemath.org/question/39726/defining-a-subgroup-of-elliptic-curves-with-specific-characteristics/?comment=39801#post-id-39801I'm on generating an example from now on.Sun, 26 Nov 2017 12:30:01 -0600http://ask.sagemath.org/question/39726/defining-a-subgroup-of-elliptic-curves-with-specific-characteristics/?comment=39801#post-id-39801Comment by Shalec for <p>Hey,</p>
<p>is there a way, to define a subgroup of an elliptic curve with two or more characteristics? I would like to take an elliptic curve over a finite field of order p and $p^4$, define the r-torsion subgroup (where $r$ is a prime, too) and reduce those to the set of points, which also lays in the Frobenius-eigenspace. </p>
<p>For example:</p>
<pre><code>p= 13
r=5
R=GF(p)
_.<x> = PolynomialRing(R)
R4.<x> = R.extension(x^4 - 2, 'x')
_.<y> = PolynomialRing(R)
b= x^-1
E = EllipticCurve(R, [1,0]) # y^2 = x^3+x
E4 = EllipticCurve(R4, [b,0])
</code></pre>
<p>Well, it is easy to find a point on $Q\in E4$, such that $r*Q = (0:1:0)$, use</p>
<pre><code>Q=ZZ(E4.order()/r *Q
</code></pre>
<p>, but checking, if $( x(Q)^p, y(Q)^p )=\pi(Q) = pQ$ is hard. I only need one point of that group at all, but my $p$ is even larger (~340 bits), so brute-forcing would be an option, if I could start it 6-12 month ago :)</p>
<p>Furthermore, if I concider to evaluate the secant or tangent on E and let me return a point on that curve, it will have projective coordinates, with $z(P)\neq1$. Shall I apply $\pi$ to all three coordinates?</p>
http://ask.sagemath.org/question/39726/defining-a-subgroup-of-elliptic-curves-with-specific-characteristics/?comment=39789#post-id-39789Ok. You got it right. I might produce an example in the next hours. For instance the parameters "p=13" and "r=5" should do it. Consider $E':\ y^2=x^3+ (2^{-1/4})x$ over $\mathbb F_{p^4}$. This curve becomes isomorphic over $\mathbb F_{p^{16}}$ to $E:\ y^2=x^3+x$, where $E(\mathbb F_p)[r]=E(\mathbb F_{p^{16}})[r]\cap \{P\in E:\ \pi (P)= \mathcal O \}$. (Twist)Sat, 25 Nov 2017 10:11:03 -0600http://ask.sagemath.org/question/39726/defining-a-subgroup-of-elliptic-curves-with-specific-characteristics/?comment=39789#post-id-39789Comment by dan_fulea for <p>Hey,</p>
<p>is there a way, to define a subgroup of an elliptic curve with two or more characteristics? I would like to take an elliptic curve over a finite field of order p and $p^4$, define the r-torsion subgroup (where $r$ is a prime, too) and reduce those to the set of points, which also lays in the Frobenius-eigenspace. </p>
<p>For example:</p>
<pre><code>p= 13
r=5
R=GF(p)
_.<x> = PolynomialRing(R)
R4.<x> = R.extension(x^4 - 2, 'x')
_.<y> = PolynomialRing(R)
b= x^-1
E = EllipticCurve(R, [1,0]) # y^2 = x^3+x
E4 = EllipticCurve(R4, [b,0])
</code></pre>
<p>Well, it is easy to find a point on $Q\in E4$, such that $r*Q = (0:1:0)$, use</p>
<pre><code>Q=ZZ(E4.order()/r *Q
</code></pre>
<p>, but checking, if $( x(Q)^p, y(Q)^p )=\pi(Q) = pQ$ is hard. I only need one point of that group at all, but my $p$ is even larger (~340 bits), so brute-forcing would be an option, if I could start it 6-12 month ago :)</p>
<p>Furthermore, if I concider to evaluate the secant or tangent on E and let me return a point on that curve, it will have projective coordinates, with $z(P)\neq1$. Shall I apply $\pi$ to all three coordinates?</p>
http://ask.sagemath.org/question/39726/defining-a-subgroup-of-elliptic-curves-with-specific-characteristics/?comment=39743#post-id-39743Things are still somehow unclear for me. I'll try to write sentences, please correct me where i am going wrong...
Let $K=\mathbb F_{p^4}$ for some prime $p$. Let $F$ be the Frobenius morphism, $Fx=x^p$, on $K$, $x\in K$.
Let $E$ be the elliptic curve over $K$ defined by the equation
$$y^2 = x^3+bx$$
for some suitable $b$ **not in** the prime field $\mathbb F_p$ inside $K$.
So we fix a point $Q = (x_Q,y_Q)$ in $E(K)$, it satisfies:
$$y_Q^2 = x_Q^3 +bx_Q\ . $$
Applying $F$ on the above, we get a point $\pi Q=(x_Q^p,y_Q^p)$ on the curve $E'$,
$$y^2 = x^3+b^p x\ .$$
And $b^p\ne b$.
On the other side, the point $pQ$ is on the curve $E$. An equality $\pi Q=pQ$ leads to $b^p x_Q = bx_Q$...
Please give a working example (brute force even) in some small field situation.Thu, 23 Nov 2017 08:16:24 -0600http://ask.sagemath.org/question/39726/defining-a-subgroup-of-elliptic-curves-with-specific-characteristics/?comment=39743#post-id-39743Comment by Shalec for <p>Hey,</p>
<p>is there a way, to define a subgroup of an elliptic curve with two or more characteristics? I would like to take an elliptic curve over a finite field of order p and $p^4$, define the r-torsion subgroup (where $r$ is a prime, too) and reduce those to the set of points, which also lays in the Frobenius-eigenspace. </p>
<p>For example:</p>
<pre><code>p= 13
r=5
R=GF(p)
_.<x> = PolynomialRing(R)
R4.<x> = R.extension(x^4 - 2, 'x')
_.<y> = PolynomialRing(R)
b= x^-1
E = EllipticCurve(R, [1,0]) # y^2 = x^3+x
E4 = EllipticCurve(R4, [b,0])
</code></pre>
<p>Well, it is easy to find a point on $Q\in E4$, such that $r*Q = (0:1:0)$, use</p>
<pre><code>Q=ZZ(E4.order()/r *Q
</code></pre>
<p>, but checking, if $( x(Q)^p, y(Q)^p )=\pi(Q) = pQ$ is hard. I only need one point of that group at all, but my $p$ is even larger (~340 bits), so brute-forcing would be an option, if I could start it 6-12 month ago :)</p>
<p>Furthermore, if I concider to evaluate the secant or tangent on E and let me return a point on that curve, it will have projective coordinates, with $z(P)\neq1$. Shall I apply $\pi$ to all three coordinates?</p>
http://ask.sagemath.org/question/39726/defining-a-subgroup-of-elliptic-curves-with-specific-characteristics/?comment=39741#post-id-39741Ok, I do. :) $\pi$ is the p-Frobenius, that means: $\pi(P)=(x(P)^p, y(P)^p)$ and the prime is around 340 bits of size. You can find that in the edit also.Thu, 23 Nov 2017 05:57:14 -0600http://ask.sagemath.org/question/39726/defining-a-subgroup-of-elliptic-curves-with-specific-characteristics/?comment=39741#post-id-39741Comment by dan_fulea for <p>Hey,</p>
<p>is there a way, to define a subgroup of an elliptic curve with two or more characteristics? I would like to take an elliptic curve over a finite field of order p and $p^4$, define the r-torsion subgroup (where $r$ is a prime, too) and reduce those to the set of points, which also lays in the Frobenius-eigenspace. </p>
<p>For example:</p>
<pre><code>p= 13
r=5
R=GF(p)
_.<x> = PolynomialRing(R)
R4.<x> = R.extension(x^4 - 2, 'x')
_.<y> = PolynomialRing(R)
b= x^-1
E = EllipticCurve(R, [1,0]) # y^2 = x^3+x
E4 = EllipticCurve(R4, [b,0])
</code></pre>
<p>Well, it is easy to find a point on $Q\in E4$, such that $r*Q = (0:1:0)$, use</p>
<pre><code>Q=ZZ(E4.order()/r *Q
</code></pre>
<p>, but checking, if $( x(Q)^p, y(Q)^p )=\pi(Q) = pQ$ is hard. I only need one point of that group at all, but my $p$ is even larger (~340 bits), so brute-forcing would be an option, if I could start it 6-12 month ago :)</p>
<p>Furthermore, if I concider to evaluate the secant or tangent on E and let me return a point on that curve, it will have projective coordinates, with $z(P)\neq1$. Shall I apply $\pi$ to all three coordinates?</p>
http://ask.sagemath.org/question/39726/defining-a-subgroup-of-elliptic-curves-with-specific-characteristics/?comment=39727#post-id-39727What is the projection $\pi$?
The order of `E4` is not divisible by `r = 5`:
sage: E4.order().factor()
2 * 14401
Please edit the question, so that these two sensible points become clear.
The "real case" has to do with a prime `p` like - say - `p = ZZ(10^50).next_prime()`? (Or bigger...)Wed, 22 Nov 2017 09:55:19 -0600http://ask.sagemath.org/question/39726/defining-a-subgroup-of-elliptic-curves-with-specific-characteristics/?comment=39727#post-id-39727