# Revision history [back]

### 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, but it does not seem to work for the even degree isogenies, and also for the above mentioned large degree odd isogeny, I do not seem to get an answer too.

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])

def __str__(self):
"""
Implement a simple string/print routine on an instance of this class/
"""

s =  ('Elliptic curve y^2 = x^3 + a4 x + a6 with\n    a4 = %s\n    a6 = %s\n'
% (self.E.a4(), self.E.a6()))
s += ('  torsion point of order 3^%s:\n    %s\n'
% (self.exponent, self.torsion_point))
if self.exponent:
s += ( '  the isogeny will be built w.r.t. the point\n    %s\n\n'
% ((3^self.exponent-1) * self.torsion_point))
s += '  Further points on the curve are:\n'
for point in self.points:
s += '    %s\n' % str(point)

return s


But when | try to calculate isogeny, using the following field:

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)


and the following elements:

E = Elliptic Curve defined by y^2 = x^3 + x over Finite Field in j of size 10354717741769305252977768237866805321427389645549071170116189679054678940682478846502882896561066713624553211618840202385203911976522554393044160468771151816976706840078913334358399730952774926980235086850991501872665651576831^2
R = (9007518108646169717637829256143902727256908604612852170262845383236308734546752870948023665818612994373405439104311563180515971827416888758364379345147971116263603311381076594736408857657724917306603115510356333363208849059629*j + 8143875544876203102731118758998042519548033956324586056599014675159430178641351639084698635604334996400279245810044652728374901773305503117205094200107841651156165349992200320758569566012680521517849444975619314122642286738078 : 5933067621852699133314119054291511797259450704514751366342623924502189539964363940282453138760679452407770908256363554867263728524097776132882938143129922521585626385240622607283870971683009886348379499590584807528366215593257*j + 3243060684426863808401390460086135176972427334603406644358264254553792355536601776050361287848102972929373427788393162068323805718475829130551068182582167101080584984966674872491237953303465307684436948645319932524248022850554 : 1)
phiP = (5784307033157574162391672474522522983832304511218905707704962058799572462719474192769980361922537187309960524475241186527300549088533941865412874661143122262830946833377212881592965099601886901183961091839303261748866970694633 : 5528941793184617364511452300962695084942165460078897881580666552736555418273496645894674314774001072353816966764689493098122556662755842001969781687909521301233517912821073526079191975713749455487083964491867894271185073160661 : 1)
phiQ = (4570410708611731090586095763344282337595085134330165462411227620255106477963004653732902534638529526314592687143599015857903362887988612527631285807628029554145760006701700452765434631350888025796273995011688240123798680882198 : 5528941793184617364511452300962695084942165460078897881580666552736555418273496645894674314774001072353816966764689493098122556662755842001969781687909521301233517912821073526079191975713749455487083964491867894271185073160661*j : 1)


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:

E = Elliptic Curve defined by y^2 = x^3 + x over Finite Field in j of size 10354717741769305252977768237866805321427389645549071170116189679054678940682478846502882896561066713624553211618840202385203911976522554393044160468771151816976706840078913334358399730952774926980235086850991501872665651576831^2
R = (5110605836845566926025654047424167572170042372900551706614198682868609124986515618280597159249062586518558366705653348177099645521579421315786637369850653444795496916683519951328090963213358196198661324642758054901662568911454*j + 4234869830555943849779568791108578084407579904872225169650118735805222570371281152259184280337943783338310393473931143980765745444039692659441232529288102314058310400426732946525612162308610371741399922257500660578782200917155 : 5100498610209823809391228850023209691234397421134363575826918390640143899484912001953261335357385806761065415074391051805515401642580444835961489218757392256505375361061973605756427459420249731757621385279542696786456958672535*j + 3945657958394557421465268691904614939064430526791563586067697568085750995914128796629365705178878140816178998799696237175564589123664889202169294820353858542756862036043886052635535912561145255328107702126311995666291927980188 : 1)
phiP = (4359917396849101231053336763700300892915096700013704210194781457801412731643988367389870886884336453245156775454336249199185654250159051929975600857047173121187832546031604804277991148436536445770452624367894371450077315674371 : 106866937607440797536385002617766720826944674650271400721039514250889186719923133049487966730514682296643039694531052672873754128006844434636819566554364257913332237123293860767683395958817983684370065598726191088239028762772 : 1)
phiQ = (5994800344920204021924431474166504428512292945535366959921408221253266209038490479113012009676730260379396436164503953186018257726363502463068559611723978695788874294047308530080408582516238481209782462483097130422588335902460 : 106866937607440797536385002617766720826944674650271400721039514250889186719923133049487966730514682296643039694531052672873754128006844434636819566554364257913332237123293860767683395958817983684370065598726191088239028762772*j : 1)


where R has degree $2^{372}$. Any ideas how to evaluate these isogenies in a "reasonable" time in Sage?

### 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, but it does not seem to work for the even degree isogenies, and also for the above mentioned large degree odd isogeny, I do not seem to get an answer too.

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])

def __str__(self):
"""
Implement a simple string/print routine on an instance of this class/
"""

s =  ('Elliptic curve y^2 = x^3 + a4 x + a6 with\n    a4 = %s\n    a6 = %s\n'
% (self.E.a4(), self.E.a6()))
s += ('  torsion point of order 3^%s:\n    %s\n'
% (self.exponent, self.torsion_point))
if self.exponent:
s += ( '  the isogeny will be built w.r.t. the point\n    %s\n\n'
% ((3^self.exponent-1) * self.torsion_point))
s += '  Further points on the curve are:\n'
for point in self.points:
s += '    %s\n' % str(point)

return s


But when | try to calculate isogeny, using the following field:

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)


and the following elements:

E = Elliptic Curve defined by y^2 = x^3 + x over Finite Field in j of size 10354717741769305252977768237866805321427389645549071170116189679054678940682478846502882896561066713624553211618840202385203911976522554393044160468771151816976706840078913334358399730952774926980235086850991501872665651576831^2
R = (9007518108646169717637829256143902727256908604612852170262845383236308734546752870948023665818612994373405439104311563180515971827416888758364379345147971116263603311381076594736408857657724917306603115510356333363208849059629*j + 8143875544876203102731118758998042519548033956324586056599014675159430178641351639084698635604334996400279245810044652728374901773305503117205094200107841651156165349992200320758569566012680521517849444975619314122642286738078 : 5933067621852699133314119054291511797259450704514751366342623924502189539964363940282453138760679452407770908256363554867263728524097776132882938143129922521585626385240622607283870971683009886348379499590584807528366215593257*j + 3243060684426863808401390460086135176972427334603406644358264254553792355536601776050361287848102972929373427788393162068323805718475829130551068182582167101080584984966674872491237953303465307684436948645319932524248022850554 : 1)
phiP = (5784307033157574162391672474522522983832304511218905707704962058799572462719474192769980361922537187309960524475241186527300549088533941865412874661143122262830946833377212881592965099601886901183961091839303261748866970694633 : 5528941793184617364511452300962695084942165460078897881580666552736555418273496645894674314774001072353816966764689493098122556662755842001969781687909521301233517912821073526079191975713749455487083964491867894271185073160661 : 1)
phiQ = (4570410708611731090586095763344282337595085134330165462411227620255106477963004653732902534638529526314592687143599015857903362887988612527631285807628029554145760006701700452765434631350888025796273995011688240123798680882198 : 5528941793184617364511452300962695084942165460078897881580666552736555418273496645894674314774001072353816966764689493098122556662755842001969781687909521301233517912821073526079191975713749455487083964491867894271185073160661*j : 1)


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:

E = Elliptic Curve defined by y^2 = x^3 + x over Finite Field in j of size 10354717741769305252977768237866805321427389645549071170116189679054678940682478846502882896561066713624553211618840202385203911976522554393044160468771151816976706840078913334358399730952774926980235086850991501872665651576831^2
R = (5110605836845566926025654047424167572170042372900551706614198682868609124986515618280597159249062586518558366705653348177099645521579421315786637369850653444795496916683519951328090963213358196198661324642758054901662568911454*j + 4234869830555943849779568791108578084407579904872225169650118735805222570371281152259184280337943783338310393473931143980765745444039692659441232529288102314058310400426732946525612162308610371741399922257500660578782200917155 : 5100498610209823809391228850023209691234397421134363575826918390640143899484912001953261335357385806761065415074391051805515401642580444835961489218757392256505375361061973605756427459420249731757621385279542696786456958672535*j + 3945657958394557421465268691904614939064430526791563586067697568085750995914128796629365705178878140816178998799696237175564589123664889202169294820353858542756862036043886052635535912561145255328107702126311995666291927980188 : 1)
phiP = (4359917396849101231053336763700300892915096700013704210194781457801412731643988367389870886884336453245156775454336249199185654250159051929975600857047173121187832546031604804277991148436536445770452624367894371450077315674371 : 106866937607440797536385002617766720826944674650271400721039514250889186719923133049487966730514682296643039694531052672873754128006844434636819566554364257913332237123293860767683395958817983684370065598726191088239028762772 : 1)
phiQ = (5994800344920204021924431474166504428512292945535366959921408221253266209038490479113012009676730260379396436164503953186018257726363502463068559611723978695788874294047308530080408582516238481209782462483097130422588335902460 : 106866937607440797536385002617766720826944674650271400721039514250889186719923133049487966730514682296643039694531052672873754128006844434636819566554364257913332237123293860767683395958817983684370065598726191088239028762772*j : 1)


where R has degree $2^{372}$. Any ideas how to evaluate these isogenies in a "reasonable" time in Sage?

### 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, but it does not seem to work for the even degree isogenies, and also for the above mentioned large degree odd isogeny, I do not seem to get an answer too.

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: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:

E = Elliptic Curve defined by y^2 = x^3 + x over Finite Field in j of size 10354717741769305252977768237866805321427389645549071170116189679054678940682478846502882896561066713624553211618840202385203911976522554393044160468771151816976706840078913334358399730952774926980235086850991501872665651576831^2
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:

E = Elliptic Curve defined by y^2 = x^3 + x over Finite Field in j of size 10354717741769305252977768237866805321427389645549071170116189679054678940682478846502882896561066713624553211618840202385203911976522554393044160468771151816976706840078913334358399730952774926980235086850991501872665651576831^2
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}$. Any ideas how to evaluate these isogenies in a "reasonable" time in Sage?

### 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, but it does not seem to work for the even degree isogenies, and also for the above mentioned large degree odd isogeny, I do not seem to get an answer too.

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}$. I basically need to chain 2 and 3 isogenies, in order to calculate large degree isogenies which are power of 2 and 3. Any ideas how to evaluate do these isogenies efficiently in Sage so that the computations finish a "reasonable" time in Sage?time?

### 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, but it does not seem to work for the even degree isogenies, and also for the above mentioned large degree odd isogeny, I do not seem to get an answer too.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}$. I basically need to chain 2 and 3 isogenies, in order to calculate large degree isogenies which are power of 2 and 3. Any ideas how to do these efficiently in Sage so that the computations finish a "reasonable" time?

### 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, 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}$. I basically need to How can one chain 2 and 3 isogenies, in order to calculate large isogenies compute high degree isogenies which isgonies that are power powers of 2 and 3. 3?. Any ideas how to do these efficiently in Sage so that the computations finish a "reasonable" time?