Opened 8 years ago

Closed 8 years ago

#11578 closed defect (fixed)

elliptic curve isogeny: error in documentation and a comment

Reported by: was Owned by: cremona
Priority: major Milestone: sage-4.7.2
Component: elliptic curves Keywords:
Cc: Merged in: sage-4.7.2.alpha1
Authors: William Stein Reviewers: Dan Shumow
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

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.

Attachments (1)

trac_11578.patch (3.0 KB) - added by was 8 years ago.

Download all attachments as: .zip

Change History (9)

comment:1 Changed 8 years ago by was

  • Component changed from PLEASE CHANGE to elliptic curves
  • Owner changed from tbd to cremona
  • Type changed from PLEASE CHANGE to defect

comment:2 Changed 8 years ago by was

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.

Changed 8 years ago by was

comment:3 Changed 8 years ago by was

  • Status changed from new to needs_review

comment:4 Changed 8 years ago by was

  • Status changed from needs_review to positive_review

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

comment:5 Changed 8 years ago by cremona

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.

comment:6 Changed 8 years ago 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}

comment:7 Changed 8 years ago by jdemeyer

  • Authors set to William Stein
  • Reviewers set to Dan Shumow

comment:8 Changed 8 years ago by jdemeyer

  • Merged in set to sage-4.7.2.alpha1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.