Processing math: 100%
Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

Lifting an Isogeny without Starting All Over

So I was computing isogeny over finite field in different extension degrees. Let's suppose I have obtained an isogeny ϕ over Fq and an embedding . ι:FqFqk

What I did for now is to extract the kernel polynomial ϕxFq, componentwise lift its coefficient to Fqk and obtain ˜ϕx=ι(ϕx), then using Kohel's formula to compute the lifted isogeny ˜ϕ:EE[˜ϕx].

Fq = GF(1009)
extFq = GF(1009^10)
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()
phix = sum(iota(ci)*extFq[x](x)^di for di, ci in enumerate(phix))
E = phi.domain().change_ring(iota)
phi = E.isogeny(phix)

However, this costs too much computational resources to recompute the whole isogeny from scratch. In theory, since we have already computed ϕ before hand, one reasonable approach is to simply lift the rational coefficients of ϕ by ι 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?

Lifting an Isogeny without Starting All Over

So I was computing isogeny over finite field in different extension degrees. Let's suppose I have obtained an isogeny ϕ over Fq and an embedding . ι:FqFqk

What I did for now is to extract the kernel polynomial ϕxFq, componentwise ϕxFq[x]; componentwisely lift its coefficient to Fqk and obtain ˜ϕx=ι(ϕx), then using Kohel's formula to compute the lifted isogeny ˜ϕ:EE[˜ϕx].

Fq = GF(1009)
extFq = GF(1009^10)
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()
phix = sum(iota(ci)*extFq[x](x)^di for di, ci in enumerate(phix))
E = phi.domain().change_ring(iota)
phi = E.isogeny(phix)

However, this costs too much computational resources to recompute the whole isogeny from scratch. In theory, since we have already computed ϕ before hand, one reasonable approach is to simply lift the rational coefficients of ϕ by ι 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?

Lifting an Isogeny without Starting All Over

So I was computing isogeny over finite field in different extension degrees. Let's suppose I have obtained an isogeny ϕ over Fq and an embedding . ι:FqFqkι:FqFqk.

What I did for now is to extract the kernel polynomial ϕxFq[x]; componentwisely lift its coefficient to Fqk and obtain ˜ϕx=ι(ϕx), then using Kohel's formula to compute the lifted isogeny ˜ϕ:EE[˜ϕx].

Fq = GF(1009)
extFq = GF(1009^10)
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()
phix = sum(iota(ci)*extFq[x](x)^di for di, ci in enumerate(phix))
E = phi.domain().change_ring(iota)
phi = E.isogeny(phix)

However, this costs too much computational resources to recompute the whole isogeny from scratch. In theory, since we have already computed ϕ before hand, one reasonable approach is to simply lift the rational coefficients of ϕ by ι 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?

Lifting an Isogeny without Starting All Over

So I was computing isogeny over finite field in different extension degrees. Let's suppose I have obtained an isogeny ϕ over Fq and an embedding . ι:FqFqk.ι:FqFqk. How do I lift ϕ to a larger field Fqk?

What I did for now is to extract the kernel polynomial ϕxFq[x]; componentwisely lift its coefficient to Fqk and obtain ˜ϕx=ι(ϕx), then using Kohel's formula to compute the lifted isogeny ˜ϕ:EE[˜ϕx].

Fq = GF(1009)
extFq = GF(1009^10)
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()
phix = sum(iota(ci)*extFq[x](x)^di for di, ci in enumerate(phix))
E = phi.domain().change_ring(iota)
phi = E.isogeny(phix)

However, this costs too much computational resources to recompute the whole isogeny from scratch. In theory, since we have already computed ϕ before hand, one reasonable approach is to simply lift the rational coefficients of ϕ by ι 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?

Lifting an Isogeny without Starting All Over

So I was computing isogeny over finite field in different extension degrees. Let's suppose I have obtained an isogeny ϕ over Fq and an embedding . ι:FqFqk. How do I lift ϕ to a larger field Fqk?Fqk by ι?

What I did for now is to extract the kernel polynomial ϕxFq[x]; componentwisely lift its coefficient to Fqk and obtain ˜ϕx=ι(ϕx), then using Kohel's formula to compute the lifted isogeny ˜ϕ:EE[˜ϕx].

Fq = GF(1009)
extFq = GF(1009^10)
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()
phix = sum(iota(ci)*extFq[x](x)^di for di, ci in enumerate(phix))
E = phi.domain().change_ring(iota)
phi = E.isogeny(phix)

However, this costs too much computational resources to recompute the whole isogeny from scratch. In theory, since we have already computed ϕ before hand, one reasonable approach is to simply lift the rational coefficients of ϕ by ι 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?

Lifting an Isogeny without Starting All Over

So I was computing isogeny over finite field in different extension degrees. Let's suppose I have obtained an isogeny ϕ over Fq and an embedding . ι:FqFqk. How do I lift ϕ to a larger field Fqk by ι?

What I did for now is to extract the kernel polynomial ϕxFq[x]; componentwisely lift its coefficient to Fqk and obtain ˜ϕx=ι(ϕx), then using Kohel's formula to compute the lifted isogeny ˜ϕ:EE[˜ϕx].

from sage.coding.relative_finite_field_extension import *
Fq = GF(1009)
extFq = GF(1009^10)
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()
phix = sum(iota(ci)*extFq[x](x)^di for di, ci in enumerate(phix))
E = phi.domain().change_ring(iota)
phi = E.isogeny(phix)

However, this costs too much computational resources to recompute the whole isogeny from scratch. In theory, since we have already computed ϕ before hand, one reasonable approach is to simply lift the rational coefficients of ϕ by ι 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?

Lifting an Isogeny without Starting All Over

So I was computing isogeny over finite field in different extension degrees. Let's suppose I have obtained an isogeny ϕ over Fq and an embedding . ι:FqFqk. How do I lift ϕ to a larger field Fqk by ι?

What I did for now is to extract the kernel polynomial ϕxFq[x]; componentwisely lift its coefficient to Fqk and obtain ˜ϕx=ι(ϕx), then using Kohel's formula to compute the lifted isogeny ˜ϕ:EE[˜ϕx].

from sage.coding.relative_finite_field_extension import *
Fq = GF(1009)
GF(1009^2)
extFq = GF(1009^10)
GF(1009^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()
phix = sum(iota(ci)*extFq[x](x)^di for di, ci in enumerate(phix))
E = phi.domain().change_ring(iota)
phi = E.isogeny(phix)

However, this costs too much computational resources to recompute the whole isogeny from scratch. In theory, since we have already computed ϕ before hand, one reasonable approach is to simply lift the rational coefficients of ϕ by ι 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?

Lifting an Isogeny without Starting All Over

So I was computing isogeny over finite field in different extension degrees. Let's suppose I have obtained an isogeny ϕ over Fq and an embedding . ι:FqFqk. How do I lift ϕ to a larger field Fqk by ι?

What I did for now is to extract the kernel polynomial ϕxFq[x]; componentwisely lift its coefficient to Fqk and obtain ˜ϕx=ι(ϕx), then using Kohel's formula to compute the lifted isogeny ˜ϕ:EE[˜ϕx].

from sage.coding.relative_finite_field_extension import *
Fq = GF(1009^2)
GF(71^2)
extFq = GF(1009^4)
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()
phix = sum(iota(ci)*extFq[x](x)^di for di, ci in enumerate(phix))
E = phi.domain().change_ring(iota)
phi = E.isogeny(phix)

However, this costs too much computational resources to recompute the whole isogeny from scratch. In theory, since we have already computed ϕ before hand, one reasonable approach is to simply lift the rational coefficients of ϕ by ι 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?

Lifting an Isogeny without Starting All Over

So I was computing isogeny over finite field in different extension degrees. Let's suppose I have obtained an isogeny ϕ over Fq and an embedding . ι:FqFqk. How do I lift ϕ to a larger field Fqk by ι?

What I did for now is to extract the kernel polynomial ϕxFq[x]; componentwisely lift its coefficient to Fqk and obtain ˜ϕx=ι(ϕx), then using Kohel's formula to compute the lifted isogeny ˜ϕ:EE[˜ϕ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()
phix extPhix = sum(iota(ci)*extFq[x](x)^di for di, ci in enumerate(phix))
E extE = phi.domain().change_ring(iota)
phi = E.isogeny(phix)
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 ϕ before hand, one reasonable approach is to simply lift the rational coefficients of ϕ by ι 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?