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?
