elliptic curve isogeny: error in documentation and a comment

[williamstein]

The isogeny code claims to check whether the input is valid, but it does not. The algorithm checks only that the polynomial defines a subset of the n-torsion, not that it describes a subgroup. This tiny patches fixes the documentation to not blatantly lie.

Also, there is a "vast" that should be "fast" in a comment.

Component: elliptic curves

Author: William Stein

Reviewer: Dan Shumow

Merged: sage-4.7.2.alpha1

Issue created by migration from https://trac.sagemath.org/ticket/11578

[williamstein]

comment:2

Note: The docstring in this patch is invalid ReST, i.e., the bulleted list is misformated. This is the case for dozens (!) of the docstrings in this file. Fixing this should be done later as a single separate patch.

[williamstein]

comment:3

Attachment: trac_11578.patch.gz

[williamstein]

comment:4

Positive review from Dan Shumow (original author of the code): "Looks good to me. -D"

[JohnCremona]

comment:5

Comment (about the comment and examples added): I have code (written by Kimi Tsukazaki) which checks properly that a given kernel polynomial is genuine, which I have been meaning to make into a patch for a long time. It is not very cheap to run though, so we would need to have a "check=False" parameter.

[williamstein]

comment:6

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}

[jdemeyer]

Reviewer: Dan Shumow

[jdemeyer]

Author: William Stein

[jdemeyer]

Merged: sage-4.7.2.alpha1