Taylor Huang's profile - activity

Hi, I was trying to count the number of basic arithmetics happened in a GF(q)[x] or GF(q)[x].quo(irr) operation. I turned to define a wrapper class

Fq = GF(q)
class probeFq(Fq):
  def __init__(self,*p,**kw):
    self._cnt = 0
    super(probeFq,self).__init__(*p,**kw)
  def __add__(self, *p,**kw):
    self._cnt += 1
    return super(probeFq,self).__add__(*p,**kw)

However, I turns out that GF(q) in sage is not a class. Instead it is some sort of factory object. Is there any way to count the number of arithmetics happened to an element?

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?

It seems my question didn't raise enough attention. I would answer my own question, though.

To embed a curve into a larger field, simply use change_ring with specified morphisms. For my particular case

p, degree = 2538055698343985819, 8
q  = p^2
Fq = GF(q)
E = EllipticCurve(Fq,[1,0])
irr = PolynomialRing(GF(p),'x').irreducible_element(2*degree)
extFq = GF(q^degree,'x',irr)
# we could obtain embedding by
rel = RelativeFiniteFieldExtension(extFq,Fq)
E.change_ring(rel.embedding())
E.random_element()

@rburing It's because I would need to do some arithmetics in these different field and I couldn't priori decide the larger ring.

I've added runnable codes.

@tmonteil I have edit and include the codes

So I was trying to construct a curve and compute arithmetics on different hierachy of extensions. The problem is, since in my application the characteristic $p$ is so large that the regular Fq.extension(degree) runs like forever. I'm not sure why but I could instead compute irr = PolynomialRing(Fq,'x').irreducible_element(degree) and then just do the extension extFq = Fq.extension(irr) by explicitly specifying a irreducible. However, my curve obtain by E.change_ring(extFq) would no longer be recognized over finite field and able to sample a random point. Thus the following snippet fails

q, degree = 6441726727896377540006619567673100761, 8
# q is some priori decided prime power and degree is roughly 8
Fq = GF(q)
E = EllipticCurve(Fq,[1,0])
irr = PolynomialRing(Fq,'x').irreducible_element(degree)
extFq = Fq.extension(irr)
extE = E.change_ring(extFq)
extE.random_element() #this fails

On another hand, if I simply specify the relative extension extFq = GF(q^degree) and use the relative extension RelativeFiniteFieldExtension to get the embedding, then I'm not sure how to specify the coersion explicitly while using E.change_ring.

p, degree = 2538055698343985819, 8
q  = p^2
Fq = GF(q)
E = EllipticCurve(Fq,[1,0])
irr = PolynomialRing(GF(p),'x').irreducible_element(2*degree)
extFq = GF(q^degree,'x',irr)
# we could obtain embedding by
# rel = RelativeFiniteFieldExtension(extFq,Fq)
E.change_ring(extFq) # error: no coersion

Is there any way to get around this?

So I was trying to construct a curve and compute arithmetics on different hierachy of extensions. The problem is, since in my application the characteristic $p$ is so large that the regular Fq.extension(degree) runs like forever. I'm not sure why but I could instead compute irr = PolynomialRing(Fq,'x').irreducible_element(degree) and then just do the extension extFq = Fq.extension(irr) by explicitly specifying a irreducible. However, my curve obtain by E.change_ring(extFq) would no longer be recognized over finite field and able to sample a random point.

On another hand, if I simply specify the relative extension extFq = GF(q^degree) and use the relative extension to specify the embedding, then I'm not sure how to specify the coersion explicitly while using E.change_ring.

Is there any way to get around this?

Hi, I was wondering given two curves $E_1,E_2$ $\ell$-isogeneous where $\ell$ is some prime. Do we have anything in Sage that help us compute its itermediate isogeny?

Hi, I was wondering given two curves $E_1,E_2$ $\ell$-isogeneous where $\ell$ is some prime. Do we have anything in Sage that help us compute its itermediate isogeny?