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.Wed, 17 Jan 2018 18:01:42 -0600Calculating elliptic curve isogeny from a kernel polynomialhttp://ask.sagemath.org/question/40648/calculating-elliptic-curve-isogeny-from-a-kernel-polynomial/This question is related to my previous [question](https://ask.sagemath.org/question/40624/elliptic-curves-and-isogenies-in-sage/), where I got partial answer to my problem. I have a code segment in Sage that roughly looks like this:
p = 10354717741769305252977768237866805321427389645549071170116189679054678940682478846502882896561066713624553211618840202385203911976522554393044160468771151816976706840078913334358399730952774926980235086850991501872665651576831
# Prime field of order p
Fp = GF(p)
R.<x> = PolynomialRing(Fp)
# The quadratic extension via x^2 + 1 since p = 3 mod 4
Fp2.<j> = Fp.extension(x^2 + 1)
E = EllipticCurve(Fp2, [1,0])
for e in range(200, 0, -2):
# Some calculation here, which produces a polynomial,
# let's call the polynomial generated is called "ker"
phi = EllipticCurveIsogeny(E, ker)
The point is that this throws an error also shown in my other question, which is `NotImplementedError: For basic Kohel's algorithm, if the kernel degree is even then the kernel must be contained in the two torsion.`. In the other question I got one answer as to compute an actual point that generates the isogeny and use it in the `EllipticCurveIsogeny` function. Though, is there a way in Sage to compute a point that generates the isogeny, from the kernel polynomial that generates the isogeny? Also if someone is interested [here](https://pastebin.com/A9HJitex) is a list of some kernel polynomials that I have generated. I have multiple loops that look like in the above example, so I need one universal solution so that I can apply to all my loops. Any ideas how to achieve what I want?Tue, 16 Jan 2018 15:57:58 -0600http://ask.sagemath.org/question/40648/calculating-elliptic-curve-isogeny-from-a-kernel-polynomial/Comment by ninho for <p>This question is related to my previous <a href="https://ask.sagemath.org/question/40624/elliptic-curves-and-isogenies-in-sage/">question</a>, where I got partial answer to my problem. I have a code segment in Sage that roughly looks like this:</p>
<pre><code>p = 10354717741769305252977768237866805321427389645549071170116189679054678940682478846502882896561066713624553211618840202385203911976522554393044160468771151816976706840078913334358399730952774926980235086850991501872665651576831
# Prime field of order p
Fp = GF(p)
R.<x> = PolynomialRing(Fp)
# The quadratic extension via x^2 + 1 since p = 3 mod 4
Fp2.<j> = Fp.extension(x^2 + 1)
E = EllipticCurve(Fp2, [1,0])
for e in range(200, 0, -2):
# Some calculation here, which produces a polynomial,
# let's call the polynomial generated is called "ker"
phi = EllipticCurveIsogeny(E, ker)
</code></pre>
<p>The point is that this throws an error also shown in my other question, which is <code>NotImplementedError: For basic Kohel's algorithm, if the kernel degree is even then the kernel must be contained in the two torsion.</code>. In the other question I got one answer as to compute an actual point that generates the isogeny and use it in the <code>EllipticCurveIsogeny</code> function. Though, is there a way in Sage to compute a point that generates the isogeny, from the kernel polynomial that generates the isogeny? Also if someone is interested <a href="https://pastebin.com/A9HJitex">here</a> is a list of some kernel polynomials that I have generated. I have multiple loops that look like in the above example, so I need one universal solution so that I can apply to all my loops. Any ideas how to achieve what I want?</p>
http://ask.sagemath.org/question/40648/calculating-elliptic-curve-isogeny-from-a-kernel-polynomial/?comment=40669#post-id-40669I updated the question with the new Pastebin. It appears the link had expired.Wed, 17 Jan 2018 18:01:42 -0600http://ask.sagemath.org/question/40648/calculating-elliptic-curve-isogeny-from-a-kernel-polynomial/?comment=40669#post-id-40669Comment by dan_fulea for <p>This question is related to my previous <a href="https://ask.sagemath.org/question/40624/elliptic-curves-and-isogenies-in-sage/">question</a>, where I got partial answer to my problem. I have a code segment in Sage that roughly looks like this:</p>
<pre><code>p = 10354717741769305252977768237866805321427389645549071170116189679054678940682478846502882896561066713624553211618840202385203911976522554393044160468771151816976706840078913334358399730952774926980235086850991501872665651576831
# Prime field of order p
Fp = GF(p)
R.<x> = PolynomialRing(Fp)
# The quadratic extension via x^2 + 1 since p = 3 mod 4
Fp2.<j> = Fp.extension(x^2 + 1)
E = EllipticCurve(Fp2, [1,0])
for e in range(200, 0, -2):
# Some calculation here, which produces a polynomial,
# let's call the polynomial generated is called "ker"
phi = EllipticCurveIsogeny(E, ker)
</code></pre>
<p>The point is that this throws an error also shown in my other question, which is <code>NotImplementedError: For basic Kohel's algorithm, if the kernel degree is even then the kernel must be contained in the two torsion.</code>. In the other question I got one answer as to compute an actual point that generates the isogeny and use it in the <code>EllipticCurveIsogeny</code> function. Though, is there a way in Sage to compute a point that generates the isogeny, from the kernel polynomial that generates the isogeny? Also if someone is interested <a href="https://pastebin.com/A9HJitex">here</a> is a list of some kernel polynomials that I have generated. I have multiple loops that look like in the above example, so I need one universal solution so that I can apply to all my loops. Any ideas how to achieve what I want?</p>
http://ask.sagemath.org/question/40648/calculating-elliptic-curve-isogeny-from-a-kernel-polynomial/?comment=40666#post-id-40666The pastebin is gone...
*This page is no longer available. It has either expired, been removed by its creator, or removed by one of the Pastebin staff.*
Is it possible to compute the zeros of the `ker`? Do the corresponding "$x$-values" lift to some points of "small torsion" on `E`?Wed, 17 Jan 2018 16:40:47 -0600http://ask.sagemath.org/question/40648/calculating-elliptic-curve-isogeny-from-a-kernel-polynomial/?comment=40666#post-id-40666Answer by dan_fulea for <p>This question is related to my previous <a href="https://ask.sagemath.org/question/40624/elliptic-curves-and-isogenies-in-sage/">question</a>, where I got partial answer to my problem. I have a code segment in Sage that roughly looks like this:</p>
<pre><code>p = 10354717741769305252977768237866805321427389645549071170116189679054678940682478846502882896561066713624553211618840202385203911976522554393044160468771151816976706840078913334358399730952774926980235086850991501872665651576831
# Prime field of order p
Fp = GF(p)
R.<x> = PolynomialRing(Fp)
# The quadratic extension via x^2 + 1 since p = 3 mod 4
Fp2.<j> = Fp.extension(x^2 + 1)
E = EllipticCurve(Fp2, [1,0])
for e in range(200, 0, -2):
# Some calculation here, which produces a polynomial,
# let's call the polynomial generated is called "ker"
phi = EllipticCurveIsogeny(E, ker)
</code></pre>
<p>The point is that this throws an error also shown in my other question, which is <code>NotImplementedError: For basic Kohel's algorithm, if the kernel degree is even then the kernel must be contained in the two torsion.</code>. In the other question I got one answer as to compute an actual point that generates the isogeny and use it in the <code>EllipticCurveIsogeny</code> function. Though, is there a way in Sage to compute a point that generates the isogeny, from the kernel polynomial that generates the isogeny? Also if someone is interested <a href="https://pastebin.com/A9HJitex">here</a> is a list of some kernel polynomials that I have generated. I have multiple loops that look like in the above example, so I need one universal solution so that I can apply to all my loops. Any ideas how to achieve what I want?</p>
http://ask.sagemath.org/question/40648/calculating-elliptic-curve-isogeny-from-a-kernel-polynomial/?answer=40667#post-id-40667We really need the `ker`. Since i had none, i started with one where the computation could succeed in relatively short time.
I am using as `ker` the following polynomial....
ker = E.torsion_polynomial( 3 ).monic()
phi1 = EllipticCurveIsogeny(E, ker)
print "phi1 (using ker):\n%s\n" % phi1
ker_roots = ker.roots( ring=Fp2, multiplicities=False )
points = [ E.lift_x(a) for a in ker_roots ]
phi2 = EllipticCurveIsogeny(E, points)
print "phi2 (using lift of ker-roots, taken as x-component):\n%s\n" % phi2
print bool( phi1 == phi2 )
The above gives:
phi1 (using ker):
Isogeny of degree 9 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field in j of size 10354717741769305252977768237866805321427389645549071170116189679054678940682478846502882896561066713624553211618840202385203911976522554393044160468771151816976706840078913334358399730952774926980235086850991501872665651576831^2 to Elliptic Curve defined by y^2 = x^3 + 81*x over Finite Field in j of size 10354717741769305252977768237866805321427389645549071170116189679054678940682478846502882896561066713624553211618840202385203911976522554393044160468771151816976706840078913334358399730952774926980235086850991501872665651576831^2
phi2 (using lift of ker-roots, taken as x-component):
Isogeny of degree 9 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field in j of size 10354717741769305252977768237866805321427389645549071170116189679054678940682478846502882896561066713624553211618840202385203911976522554393044160468771151816976706840078913334358399730952774926980235086850991501872665651576831^2 to Elliptic Curve defined by y^2 = x^3 + 81*x over Finite Field in j of size 10354717741769305252977768237866805321427389645549071170116189679054678940682478846502882896561066713624553211618840202385203911976522554393044160468771151816976706840078913334358399730952774926980235086850991501872665651576831^2
True
The big numbers are $p$ and $p^2$, so nobody is intimidated. The main information is the passage from the equation `y^2 = x^3 + x` to `y^2 = x^3 + 81*x` .
The last `True` translates in words: The isogenies constructed
* by using the `ker` as kernel polynomial, respectively
* by using the $x$-roots of `ker`, extended / lifted to points $(x,\pm y)$ on `E`
do coincide. This should also be the case in the needed concrete case. (If the generated polynomial in the `for e in range(200, 0, -2)`-loop is too complicated (big degree), then the construction of the isogeny may take a loong time. If there are too many roots, then i would use compositions of isogenies... )Wed, 17 Jan 2018 16:59:31 -0600http://ask.sagemath.org/question/40648/calculating-elliptic-curve-isogeny-from-a-kernel-polynomial/?answer=40667#post-id-40667Comment by ninho for <p>We really need the <code>ker</code>. Since i had none, i started with one where the computation could succeed in relatively short time.
I am using as <code>ker</code> the following polynomial....</p>
<pre><code>ker = E.torsion_polynomial( 3 ).monic()
phi1 = EllipticCurveIsogeny(E, ker)
print "phi1 (using ker):\n%s\n" % phi1
ker_roots = ker.roots( ring=Fp2, multiplicities=False )
points = [ E.lift_x(a) for a in ker_roots ]
phi2 = EllipticCurveIsogeny(E, points)
print "phi2 (using lift of ker-roots, taken as x-component):\n%s\n" % phi2
print bool( phi1 == phi2 )
</code></pre>
<p>The above gives:</p>
<pre><code>phi1 (using ker):
Isogeny of degree 9 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field in j of size 10354717741769305252977768237866805321427389645549071170116189679054678940682478846502882896561066713624553211618840202385203911976522554393044160468771151816976706840078913334358399730952774926980235086850991501872665651576831^2 to Elliptic Curve defined by y^2 = x^3 + 81*x over Finite Field in j of size 10354717741769305252977768237866805321427389645549071170116189679054678940682478846502882896561066713624553211618840202385203911976522554393044160468771151816976706840078913334358399730952774926980235086850991501872665651576831^2
phi2 (using lift of ker-roots, taken as x-component):
Isogeny of degree 9 from Elliptic Curve defined by y^2 = x^3 + x over Finite Field in j of size 10354717741769305252977768237866805321427389645549071170116189679054678940682478846502882896561066713624553211618840202385203911976522554393044160468771151816976706840078913334358399730952774926980235086850991501872665651576831^2 to Elliptic Curve defined by y^2 = x^3 + 81*x over Finite Field in j of size 10354717741769305252977768237866805321427389645549071170116189679054678940682478846502882896561066713624553211618840202385203911976522554393044160468771151816976706840078913334358399730952774926980235086850991501872665651576831^2
True
</code></pre>
<p>The big numbers are $p$ and $p^2$, so nobody is intimidated. The main information is the passage from the equation <code>y^2 = x^3 + x</code> to <code>y^2 = x^3 + 81*x</code> .</p>
<p>The last <code>True</code> translates in words: The isogenies constructed</p>
<ul>
<li>by using the <code>ker</code> as kernel polynomial, respectively</li>
<li>by using the $x$-roots of <code>ker</code>, extended / lifted to points $(x,\pm y)$ on <code>E</code></li>
</ul>
<p>do coincide. This should also be the case in the needed concrete case. (If the generated polynomial in the <code>for e in range(200, 0, -2)</code>-loop is too complicated (big degree), then the construction of the isogeny may take a loong time. If there are too many roots, then i would use compositions of isogenies... )</p>
http://ask.sagemath.org/question/40648/calculating-elliptic-curve-isogeny-from-a-kernel-polynomial/?comment=40668#post-id-40668Sorry about the Pastebin thing. Here are the kernels: https://pastebin.com/A9HJitexWed, 17 Jan 2018 18:01:24 -0600http://ask.sagemath.org/question/40648/calculating-elliptic-curve-isogeny-from-a-kernel-polynomial/?comment=40668#post-id-40668