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 = [2,3]
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)
def runner():
uni_total = 0
nodes_total = 0
res = []
res_single = []
res_uni = []
res_uni_single = []
for b in range(0, 100):
print "Iteration: ", b
idx = 0
E = starting_node(E_0, 0)
print "start: ", str(E.j_invariant())
walk(E, str(E.j_invariant()), 0, "", e[idx])
# Rest removed for brevity
runner()
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, 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?
