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)
Change History (9)
comment:1 Changed 8 years ago by
- 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
Changed 8 years ago by
comment:3 Changed 8 years ago by
- Status changed from new to needs_review
comment:4 Changed 8 years ago by
- 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
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
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
- Reviewers set to Dan Shumow
comment:8 Changed 8 years ago by
- Merged in set to sage-4.7.2.alpha1
- Resolution set to fixed
- Status changed from positive_review to closed
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.