Lifting an Isogeny without Starting All Over

asked 2020-06-01 13:12:27 +0200

Taylor Huang gravatar image

updated 2020-06-02 12:51:57 +0200

So I was computing isogeny over finite field in different extension degrees. Let's suppose I have obtained an isogeny $\phi$ over $\mathbb{F}_q$ and an embedding . $\iota:\mathbb{F}_{q}\to\mathbb{F}_{q^k}$. How do I lift $\phi$ to a larger field $\mathbb{F}_{q^k}$ by $\iota$?

What I did for now is to extract the kernel polynomial $\phi_x\in\mathbb{F_q}[x]$; componentwisely lift its coefficient to $\mathbb{F}_{q^k}$ and obtain $\tilde\phi_x=\iota(\phi_x)$, then using Kohel's formula to compute the lifted isogeny $\tilde\phi:E\to E[\tilde\phi_x]$.

from sage.coding.relative_finite_field_extension import *
Fq = GF(71^2)
extFq = GF(71^4)
iota = RelativeFiniteFieldExtension(extFq,Fq).embedding()
E = EllipticCurve(Fq,[1,0])
P = E.random_element()*1024
phi = E.isogeny(P)
# above are settings for copy-paste
phix = phi.kernel_polynomial()
extPhix = sum(iota(ci)*extFq[x](x)^di for di, ci in enumerate(phix))
extE = phi.domain().change_ring(iota)
extPhi = extE.isogeny(phix)

However, this costs too much computational resources to recompute the whole isogeny from scratch. In theory, since we have already computed $\phi$ before hand, one reasonable approach is to simply lift the rational coefficients of $\phi$ by $\iota$ componentwise. But I'm not quite sure how we could do this within Sage because I can't find a constructor to construct an isogeny object without specifying its kernel. Any ideas?

edit retag flag offensive close merge delete

Comments

I don't believe there is a better method than what you suggest, at the moment.

Luca gravatar imageLuca ( 2021-11-03 23:04:43 +0200 )edit