# Calculating elliptic curve isogeny from a kernel polynomial

This question is related to my previous question, 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 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?

edit retag close merge delete

The 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?

( 2018-01-17 16:40:47 -0500 )edit

I updated the question with the new Pastebin. It appears the link had expired.

( 2018-01-17 18:01:42 -0500 )edit

Sort by » oldest newest most voted

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

more

Sorry about the Pastebin thing. Here are the kernels: https://pastebin.com/A9HJitex

( 2018-01-17 18:01:24 -0500 )edit