Revision history [back]

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. What's the problem, and how can I correct it so that my loop executes successfully?

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 the problem, causing Sage not to be able to finish the isogeny calculations, and how can I correct it so that my loop executes successfully?

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 Any ideas as to 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?

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. Any ideas as to what's What might be causing Sage not to be able to finish the isogeny calculations, and how can I correct it so that my loop executes successfully?

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 Any ideas what might be causing Sage not to be able to finish the isogeny calculations, and how can I correct it so that my loop executes successfully?

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. Any ideas what might be What is causing Sage not to be able to finish the isogeny calculations, and how can I correct it so that my loop executes successfully?

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 Any ideas what is causing Sage not to be able to finish the isogeny calculations, and how can I correct it so that my loop executes successfully?

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. Any ideas what is 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?