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}$. 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?
add a comment
