#11578: elliptic curve isogeny: error in documentation and a comment
-------------------------------+--------------------------------------------
Reporter: was | Owner: cremona
Type: defect | Status: positive_review
Priority: major | Milestone: sage-4.7.2
Component: elliptic curves | Keywords:
Work_issues: | Upstream: N/A
Reviewer: | Author:
Merged: | Dependencies:
-------------------------------+--------------------------------------------
Comment(by was):
I also now have code that does this, which I wrote with my REU students.
It is also not for free speedwise. Here is all the relevant code (this
actually finds the whole isogeny class over any number field, using
isogenies up to a given degree):
{{{
#########################################################
############# isogeny classes ###############
#########################################################
def ap(E,p):
return E.change_ring(p.residue_field()).trace_of_frobenius()
R.<ch> = GF(2)[]
def frob(E,p):
t = ap(E,p)
return ch^2 - ap(E, p)*ch + int(p.norm())
def disc(E, p):
t = ap(E, p)
return t^2 - 4*p.norm()
def isogeny_primes(E, norm_bound, isog_degree_bound): #Returns
prime for which E has an isogeny
P = [p for p in sqrt5.ideals_of_bounded_norm(norm_bound) if
p.is_prime() and E.has_good_reduction(p)]
w = set(primes(isog_degree_bound+1))
i = 0
w.remove(2)
while len(w) > 0 and i < len(P):
d = disc(E, P[i])
w = [ell for ell in w if not (legendre_symbol(d,ell) == -1)]
i = i +1
i = 0
while i < len(P):
if frob(E,P[i]).is_irreducible():
break
i = i+1
if i == len(P):
w.insert(0,2)
return w
def closed_under_multiplication_by_m(E, f, m):
"""
INPUT:
- E -- elliptic curve in *short* Weierstrass form
- f -- a polynomial that defines a finite subset S of E[p] that is
closed under [-1]
- m -- integer m >= 2 coprime to p.
We assume that p is odd.
OUTPUT:
- True if [m]*S = S, and False otherwise.
"""
K = E.base_field()
h = E.multiplication_by_m(m, x_only=True)
n = h.numerator(); d = h.denominator()
S.<x, Z> = K[]
psi = n.parent().hom([x,0])
tau = f.parent().hom([x])
r = tau(f).resultant(psi(n)-Z*psi(d), x)
r0 = S.hom([0,f.parent().gen()])(r)
return r0.monic() == f.monic()
def is_subgroup(E, f, p):
"""
INPUT:
- E -- elliptic curve in *short* Weierstrass form
- f -- a polynomial that defines a finite subset S of E[p] that is
closed under [-1]
- p -- an odd prime
OUTPUT:
- True exactly if S union {0} is a group.
"""
m = primitive_root(p)
return closed_under_multiplication_by_m(E, f, m)
def isogeny_class_computation(E, p):
if p != 2:
E = E.short_weierstrass_model()
F = E.division_polynomial(p).change_ring(K)
candidates = [f for f in divisors(F) if f.degree() == (p-1)/2 and
is_subgroup(E,f,p)]
v = []
w = []
for f in candidates:
try:
v.append(E.change_ring(K).isogeny(f).codomain())
w.append(f)
except ValueError:
pass
v = [F.change_ring(K).global_minimal_model() for F in v]
return v
else:
w = [Q for Q in E.torsion_subgroup() if order(Q)==2]
v = [E.isogeny(E(Q)).codomain() for Q in w]
return v
def curve_isogeny_vector(E): #Returns isogeny class and
adjacency matrix
curve_list = [E]
i = 0
Adj = matrix(50)
ins = 1
norm_bound, isog_degree_bound = 500,500
while i < len(curve_list):
isolist = isogeny_primes(curve_list[i],norm_bound,
isog_degree_bound)
for p in isolist:
for F in isogeny_class_computation(curve_list[i],p):
bool = True
for G in curve_list:
if F.is_isomorphic(G):
bool = False
Adj[i,curve_list.index(G)]=p #if a curve in
the isogeny class computation is isom
Adj[curve_list.index(G),i]=p #to a curve
already in the list, we want a line
if bool:
curve_list.append(F)
Adj[i,ins]=p
Adj[ins,i]=p
ins += 1
i+=1
Adj = Adj.submatrix(nrows=len(curve_list),ncols=len(curve_list))
return {'curve_list':curve_list, 'adjacency_matrix':Adj,
'norm_bound':norm_bound, 'isog_degree_bound':isog_degree_bound,
'subgroup_checked':True}
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11578#comment:6>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
