ASKSAGE: Sage Q&A Forum - Latest question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 01 Jun 2020 06:12:27 -0500Lifting an Isogeny without Starting All Overhttp://ask.sagemath.org/question/51671/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 $\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?Taylor HuangMon, 01 Jun 2020 06:12:27 -0500http://ask.sagemath.org/question/51671/Isogeny from Two Curveshttp://ask.sagemath.org/question/49951/isogeny-from-two-curves/ 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?Taylor HuangSun, 16 Feb 2020 10:55:09 -0600http://ask.sagemath.org/question/49951/Isogeny from Two Curveshttp://ask.sagemath.org/question/49950/isogeny-from-two-curves/ 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?Taylor HuangSun, 16 Feb 2020 10:52:13 -0600http://ask.sagemath.org/question/49950/Isogeny computation for larger numbers doesn't finishhttp://ask.sagemath.org/question/41214/isogeny-computation-for-larger-numbers-doesnt-finish/I have the following code segment in Sage:
from sage.all import *
proof.arithmetic(False)
f = 1
lA = 2
lB = 3
eA = 372
eB = 239
p = f*lA**eA*lB**eB-1
assert p.is_prime()
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_0 = EllipticCurve(Fp2, [1,0])
assert E_0.is_supersingular()
l = [lA, lB]
e = [eA, eB]
def starting_node(E_i, count):
if count == 96:
return E_i
kers = E_i(0).division_points(3)
P = E_i(0)
while P == E_i(0):
P = kers[randint(0, 8)]
psi = E_i.isogeny(P)
return starting_node(psi.codomain(), count+1)
def walk(E_i, j,lvl, prev_j ,max_lvl):
children = {}
if lvl < max_lvl:
for P in E_i(0).division_points(2):
if P == E_i(0):
continue
psi = E_i.isogeny(P)
E_child = psi.codomain()
j_child = str(E_child.j_invariant())
lvl_child = lvl+1
if j_child in children:
children[j_child] += 1
else:
children[j_child] = 1
if (j_child != prev_j) or (children[j_child] > 1):
walk(E_child, j_child, lvl_child,j, max_lvl)
idx = 0
E = starting_node(E_0, 0)
print "start: ", str(E.j_invariant())
walk(E, str(E.j_invariant()), 0, "", e[idx])
The above code seems to execute fine when I use smaller values, but still it executes very slowly. Whereas, when I use the above numbers it does not finish with the execution. There already seems to be a similar problem mentioned [here](https://ask.sagemath.org/question/40675/isogeny-computation-does-not-finish-in-sage/), but the solution there seems to be just for 3-isogenies, but what about the general case, for different isogenies and using kernels? Also Magma seems to handle isogeny computations quite efficiently, why is Sage having such a hard time? Any ideas how can I modify the above code so that it actually finishes the execution in a "reasonable" time?ninhoWed, 21 Feb 2018 04:31:58 -0600http://ask.sagemath.org/question/41214/Even degree large isogeny computationhttp://ask.sagemath.org/question/41236/even-degree-large-isogeny-computation/I want to calculate $2^{372}$ and $3^{239}$ degree isogenies in Sage, but what I noticed is that using `EllipticCurveIsogeny` function does not finish executing for such large degree isogenies. There is already a partial answer by Dan Fulea [here](https://ask.sagemath.org/question/40675/isogeny-computation-does-not-finish-in-sage/), but it does not seem to work for the even degree isogenies, and also for the above mentioned large degree odd isogeny as there is no chaining of small degree ones.
So, basically I have the following class from Dan's answer:
class EllipticCurveWithTorsionPoint(object):
"""
Class putting together in a bag:
- an elliptic curve,
- with a point R with same order as isogeny degree,
- and with a list of other points.
The main method <image> will associate an object of the same instance,
which is the "image" of the given structure w.r.t. the isogeny with kernel O, R, 2R, ... (d-1)R.
"""
def __init__(self, E, R, d=None, points=[]):
"""
E should be given in Weierstrass form.
"""
self.is_valid = True # so far
self.E = E
if E != EllipticCurve(E.base_field(), [E.a4(), E.a6()]):
self.is_valid = False
self.points = points
self.R = R
if d:
self.d = ZZ(d)
else:
self.d = ZZ(R.order())
print "Computed: order of R is %s" % R.order().factor()
if 2.divides(self.d):
print "This class works only for an odd order d, but d=%s" % self.d
self.valid = False
self.kernel = [k*R for k in [0..(self.d-1)]]
self.d1 = ZZ((self.d-1) / 2)
def image(self):
"""
Pass to E', here denoted EE, the curve which is isogenous to E, so that
ker(E -> E') is {0, R, 2R, ... (d-1)R}. Also map to E' all the existing structure.
"""
if not self.is_valid:
print "Invalid object, no image is computed"
return self
E = self.E
F = E.base_field()
R = self.R
if R == E(0):
print "No further isogeny can be built"
return self
a, b = E.a4(), E.a6()
v, w = F(0), F(0)
data = []
for mult in [1..self.d1]:
# We split the set G = R, 2R, ... , (d-2)R, (d-1)R in two, G(+)
# and G(-) so that P in G(+) <=> -P in G(-), the multiplicities
# above correspond to those for G(+).
P = mult*R # point in G(+)
xP , yP = P.xy()
gxP, gyP = 3*xP^2 + a, -2*yp
vP , uP = 2*gxP , gyP^2
v += vP
w += uP + xP*vP
data.append([xP, yP, uP, vP])
EE = EllipticCurve(F, [a-5*v, b-7*w])
def phi(point):
print "Computing phi(%s)..." % str(point)
if point in self.kernel:
return EE(0)
x , y = point.xy()
xx, yy = x, y
for xP, yP, uP, vP in data:
xx += vP /(x-xP) + uP /(x-xP)^2
yy -= uP*2*y/(x-xP)^3 + vP*y/(x-xP)^2
return EE((xx, yy))
return EllipticCurveWithTorsionPoint(EE
, EE(0)
, d = 1
, points = [phi(point) for point in self.points])
def imageStrandard(self):
"""
This does the same thing as "image" method but using the Sage
isogeny implementation.
"""
if not self.is_valid:
return self
E = self.E
R = self.R
phi = EllipticCurveIsogeny(E, R)
EE = phi.codomain()
return EllipticCurveWithTorsionPoint(EE
, EE(0)
, d = 1
, points = [phi(point) for point in self.points])
But when | try to calculate isogeny, using the following field and elliptic curve:
p = 10354717741769305252977768237866805321427389645549071170116189679054678940682478846502882896561066713624553211618840202385203911976522554393044160468771151816976706840078913334358399730952774926980235086850991501872665651576831
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])
and the following elements:
R = (9007518108646169717637829256143902727256908604612852170262845383236308734546752870948023665818612994373405439104311563180515971827416888758364379345147971116263603311381076594736408857657724917306603115510356333363208849059629*j + 8143875544876203102731118758998042519548033956324586056599014675159430178641351639084698635604334996400279245810044652728374901773305503117205094200107841651156165349992200320758569566012680521517849444975619314122642286738078 : 5933067621852699133314119054291511797259450704514751366342623924502189539964363940282453138760679452407770908256363554867263728524097776132882938143129922521585626385240622607283870971683009886348379499590584807528366215593257*j + 3243060684426863808401390460086135176972427334603406644358264254553792355536601776050361287848102972929373427788393162068323805718475829130551068182582167101080584984966674872491237953303465307684436948645319932524248022850554 : 1)
phiP = (5784307033157574162391672474522522983832304511218905707704962058799572462719474192769980361922537187309960524475241186527300549088533941865412874661143122262830946833377212881592965099601886901183961091839303261748866970694633 : 5528941793184617364511452300962695084942165460078897881580666552736555418273496645894674314774001072353816966764689493098122556662755842001969781687909521301233517912821073526079191975713749455487083964491867894271185073160661 : 1)
phiQ = (4570410708611731090586095763344282337595085134330165462411227620255106477963004653732902534638529526314592687143599015857903362887988612527631285807628029554145760006701700452765434631350888025796273995011688240123798680882198 : 5528941793184617364511452300962695084942165460078897881580666552736555418273496645894674314774001072353816966764689493098122556662755842001969781687909521301233517912821073526079191975713749455487083964491867894271185073160661*j : 1)
such that
X = EllipticCurveWithTorsionPoint(E, R, None, [phiP, phiQ])
W = X.image()
It doesn't seem to finish execution, where R has order $3^{239}$. And the class doesn't even work for an even degree isogeny, for example, evaluation this one:
R = (5110605836845566926025654047424167572170042372900551706614198682868609124986515618280597159249062586518558366705653348177099645521579421315786637369850653444795496916683519951328090963213358196198661324642758054901662568911454*j + 4234869830555943849779568791108578084407579904872225169650118735805222570371281152259184280337943783338310393473931143980765745444039692659441232529288102314058310400426732946525612162308610371741399922257500660578782200917155 : 5100498610209823809391228850023209691234397421134363575826918390640143899484912001953261335357385806761065415074391051805515401642580444835961489218757392256505375361061973605756427459420249731757621385279542696786456958672535*j + 3945657958394557421465268691904614939064430526791563586067697568085750995914128796629365705178878140816178998799696237175564589123664889202169294820353858542756862036043886052635535912561145255328107702126311995666291927980188 : 1)
phiP = (4359917396849101231053336763700300892915096700013704210194781457801412731643988367389870886884336453245156775454336249199185654250159051929975600857047173121187832546031604804277991148436536445770452624367894371450077315674371 : 106866937607440797536385002617766720826944674650271400721039514250889186719923133049487966730514682296643039694531052672873754128006844434636819566554364257913332237123293860767683395958817983684370065598726191088239028762772 : 1)
phiQ = (5994800344920204021924431474166504428512292945535366959921408221253266209038490479113012009676730260379396436164503953186018257726363502463068559611723978695788874294047308530080408582516238481209782462483097130422588335902460 : 106866937607440797536385002617766720826944674650271400721039514250889186719923133049487966730514682296643039694531052672873754128006844434636819566554364257913332237123293860767683395958817983684370065598726191088239028762772*j : 1)
such that
X = EllipticCurveWithTorsionPoint(E, R, None, [phiP, phiQ])
W = X.image()
where R has degree $2^{372}$. How can one chain 2 and 3 isogenies compute high degree isgonies that are powers of 2 and 3?. Any ideas how to do these efficiently in Sage so that the computations finish a "reasonable" time?ninhoThu, 22 Feb 2018 16:20:01 -0600http://ask.sagemath.org/question/41236/Isogeny computation does not finish in Sagehttp://ask.sagemath.org/question/40675/isogeny-computation-does-not-finish-in-sage/I'm using the `EllipticCurveIsogeny` function to calculate isogenies, but what I have noticed is that the function does not finish executing (at least in a reasonable amount of time). My code segment looks like this:
proof.arithmetic(False)
params = [
5784307033157574162391672474522522983832304511218905707704962058799572462719474192769980361922537187309960524475241186527300549088533941865412874661143122262830946833377212881592965099601886901183961091839303261748866970694633,
5528941793184617364511452300962695084942165460078897881580666552736555418273496645894674314774001072353816966764689493098122556662755842001969781687909521301233517912821073526079191975713749455487083964491867894271185073160661,
4359917396849101231053336763700300892915096700013704210194781457801412731643988367389870886884336453245156775454336249199185654250159051929975600857047173121187832546031604804277991148436536445770452624367894371450077315674371,
106866937607440797536385002617766720826944674650271400721039514250889186719923133049487966730514682296643039694531052672873754128006844434636819566554364257913332237123293860767683395958817983684370065598726191088239028762772
]
p = 10354717741769305252977768237866805321427389645549071170116189679054678940682478846502882896561066713624553211618840202385203911976522554393044160468771151816976706840078913334358399730952774926980235086850991501872665651576831
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)
E0 = EllipticCurve(Fp2, [1,0])
assert E0.is_supersingular()
E = EllipticCurve(Fp2, [1,0]) # Weierstrass curve y^2=x^3+x
RR.<x> = PolynomialRing(Fp2) # for computing isogeny kernels
phiP = E0([params[0], params[1]])
phiQ = E0([-params[0], j*params[1]])
SK = 210
eB = 239
P = E0([params[2], params[3]])
Q = E0([-params[2], j*params[3]])
R = P + SK * Q
for e in range(eB-1, 0, -1):
S = 3^e * R
ker = [x-P[0] for P in [z*S for z in [1..3]]]
ker = reduce(lambda x, y: x*y, ker)
print "ker ({}) = {}".format(e, ker)
ker_roots = ker.roots(ring=Fp2, multiplicities=False)
print "ker_roots ({}) = {}".format(e, ker_roots)
points = [E.lift_x(a) for a in ker_roots]
print "points ({}) = {}".format(e, points)
phi = EllipticCurveIsogeny(E, points)
print "phi ({}) = {}".format(e, phi)
E = phi.codomain()
R = phi(R)
phiP = phi(phiP)
phiQ = phi(phiQ)
coeffs = E.coefficients()
print "coeffs =", coeffs
I put multiple print statements inside the loop to see where the bottleneck is, and I noticed that the first iteration executes successfully, and everything is calculated, but then in the second iteration of the loop, when it comes to calculating the isogeny, it somehow doesn't finish. I actually run the loop without the isogeny computation, and it manages to find all the roots and lifts in a short period of time, so the bottleneck here is the isogeny calculations from the given points. What's causing Sage not to be able to finish the isogeny calculations, and how can I correct it so that my loop executes successfully?ninhoThu, 18 Jan 2018 04:55:34 -0600http://ask.sagemath.org/question/40675/Calculating 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?ninhoTue, 16 Jan 2018 15:57:58 -0600http://ask.sagemath.org/question/40648/Compose Affine/Projective Curve morphism with Elliptic Curve isogenyhttp://ask.sagemath.org/question/38045/compose-affineprojective-curve-morphism-with-elliptic-curve-isogeny/When I tried to do this, I got TypeError: ... must be a map to multiply it by Isogeny ...
And when I tried to dehomogenize projective curve morphism in x,y,z by z-coordinate, the remaining variables become x0 and x1. Can I keep them as x and y instead?
EDIT: Example code:
k = GF(23)
x,y,z = k['x,y,z'].gens()
d = k(2)
C = Curve([x^3+y^3+z^3-3*d*x*y*z]) #domain curve
a = d+2
b = 4*(d^2+d+1)/3
E = EllipticCurve(y^2-x^3-(a*x+b)^2) #codomain curve
m = b
n = 4*(d^3 -1)/3
X = m*(x+y+z)
Y = n*(z-y)
Z = -z-y-d*x
f = C.Hom(E)([X,Y,Z]) #map from C to E
Q = E(2,9,1) #a point on E
g = E.isogeny(Q) #isogeny
g*f #TypeError hereRoadWed, 21 Jun 2017 10:43:25 -0500http://ask.sagemath.org/question/38045/Elliptic curve isogenies: kernel polynomial not monichttp://ask.sagemath.org/question/32717/elliptic-curve-isogenies-kernel-polynomial-not-monic/Hello, I was trying to follow the example [here](http://doc.sagemath.org/html/en/reference/plane_curves/sage/schemes/elliptic_curves/ell_curve_isogeny.html) to create a kernel equal to the full 2 torsion. But I ran into the problem of not having a monic kernel polynomial. This is what I have
sage: p = 22031
sage: K = GF(p)
sage: F.<z> = K[]
sage: L = GF(p^2,'a',modulus=z^2+2); a = L.gen()
sage: E = EllipticCurve(K,[6486*a+8098, 12871*a+17004])
sage: ker_list = E_B.division_polynomial(2).list()
sage: phi = EllipticCurveIsogeny(E, ker_list); phi
ValueError: The kernel polynomial must be monic.
I've tried to salvage the situation by feeding the list of 2-torsion points into the function, but I do not get the same isogeny.
sage: E = EllipticCurve(GF(3), [0,0,0,1,1])
sage: ker_list = E.division_polynomial(2).list()
sage: phi = EllipticCurveIsogeny(E, ker_list)
sage: print phi
Isogeny of degree 4 from Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field of size 3 to Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field of size 3
sage: ETwoTors = E(0).division_points(2)
sage: phi = EllipticCurveIsogeny(E, ETwoTors)
sage: print phi
Isogeny of degree 2 from Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field of size 3 to Elliptic Curve defined by y^2 = x^3 + 2*x over Finite Field of size 3
What I am really after is to let $\phi$ be the multiplication by 2 endomorphism.BlackadderFri, 04 Mar 2016 21:01:46 -0600http://ask.sagemath.org/question/32717/