Opened 6 years ago

Last modified 3 years ago

#21883 new defect

EllipticCurveIsogeny raising a value error that an isogeny doesn't exist while it most certainly does!

Reported by: mderickx Owned by:
Priority: major Milestone: sage-7.5
Component: elliptic curves Keywords:
Cc: Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

sage: E = EllipticCurve_from_j(0)
sage: E
Elliptic Curve defined by y^2 + y = x^3 over Rational Field
sage: phi = E.isogenies_prime_degree(3)[1]
sage: phi
Isogeny of degree 3 from Elliptic Curve defined by y^2 + y = x^3 over Rational Field to Elliptic Curve defined by y^2 + y = x^3 - 7 over Rational Field
sage: EllipticCurveIsogeny(E,None,codomain=phi.codomain(),degree=3)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-58-7c6e8f3f3fa6> in <module>()
----> 1 EllipticCurveIsogeny(E,None,codomain=phi.codomain(),degree=Integer(3))

/Applications/sage/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_curve_isogeny.pyc in __init__(self, E, kernel, codomain, degree, model, check)
   1008             old_codomain = codomain
   1009 
-> 1010             (pre_isom, post_isom, E, codomain, kernel) = compute_sequence_of_maps(E, codomain, degree)
   1011 
   1012         self.__init_algebraic_structs(E)

/Applications/sage/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_curve_isogeny.pyc in compute_sequence_of_maps(E1, E2, ell)
   4003     (E1pr, E2pr, pre_isom, post_isom) = compute_intermediate_curves(E1, E2)
   4004 
-> 4005     ker_poly = compute_isogeny_kernel_polynomial(E1pr, E2pr, ell)
   4006 
   4007     return (pre_isom, post_isom, E1pr, E2pr, ker_poly)

/Applications/sage/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_curve_isogeny.pyc in compute_isogeny_kernel_polynomial(E1, E2, ell, algorithm)
   3831         x^3 + x
   3832     """
-> 3833     return split_kernel_polynomial(compute_isogeny_starks(E1, E2, ell))
   3834 
   3835 def compute_intermediate_curves(E1, E2):

/Applications/sage/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/ell_curve_isogeny.pyc in compute_isogeny_starks(E1, E2, ell)
   3735         if (n == ell+1 or T == 0):
   3736             if (T == 0 or T.valuation()<2):
-> 3737                 raise ValueError("The two curves are not linked by a cyclic normalized isogeny of degree %s" % ell)
   3738             break
   3739 

ValueError: The two curves are not linked by a cyclic normalized isogeny of degree 3

The above might seem like a silly example, since I am asking for an object I already know. But it is the underlying problem of why:

sage: phi.dual()
...
ValueError: The two curves are not linked by a cyclic normalized isogeny of degree 3

is also broken.

Change History (4)

comment:1 Changed 6 years ago by defeo

Weird. I thought this used to work, but now I am having a very hard time finding an example that does. I managed to compute this one (a multiplication endomorphism):

sage: E = EllipticCurve([1,1])
sage: F = E.change_weierstrass_model([1/3,0,0,0])
sage: EllipticCurveIsogeny(E,None,codomain=F,degree=9)
Isogeny of degree 9 from Elliptic Curve defined by y^2 = x^3 + x + 1 over Rational Field to Elliptic Curve defined by y^2 = x^3 + 81*x + 729 over Rational Field

but many similar examples fail. Note that "normalized" is very important here:

sage: EllipticCurveIsogeny(E,None,codomain=E,degree=9)
...
ValueError: The two curves are not linked by a cyclic normalized isogeny of degree 9

Given two isogenous elliptic curves, Sage only knows how to compute an isogeny between them if the models are normalized (isogeny sends invariant differential of codomain onto invariant differential of domain). Actually, I think the best algorithm to compute non-normalized isogenies between elliptic curves in characteristic 0 is still factoring the division polynomial, which Sage does not implement. There are better algorithms for finite fields (Couveignes, Lercier-Sirvent), but they are a pain to implement.

Note that you can do better if your goal is to compute the dual: choose enough points (about 2 times deg φ), for each of them compute φ(P) and [deg φ]P, and deduce φ by interpolation.

Sadly, Sage has many specialized algorithms for isogenies, but is severly lacking generic ones.

comment:2 Changed 3 years ago by cremona

  1. It does not make sense to talk about a normalised model here, unless by "model" you mean "Weierstrass equation and a choice of invariant differential" (which you probably do. Isogenies can be normalised, while means that the pull-back of a standard differential on the codomain is the standard differential on the domain (in general it is a scalar multiple of it, nonzero for separable isogenies).
  2. For any isogeny of phi degree d from E1 to E2 it makes sense to ask if it is normalised (in the example, phi.is_normalised() does return True) and more generally what the scaling factor is (phi.formal()[1] -- which should have a method to get more easily).

Since this phi *is* normalised this is just a plain Bug.

The sentence "Actually, ..." is extremely misleading. Sage absolutely does implement the computation of isogenies via finding appropriate factors of the division polynomial. I spent a long time (and supervised part of a PhD thesis) showing how to do this -- picking an appropriate subset of the factors of the division polynomial is not trivial. But is is also *very slow* which is why the rest of the aforementioned thesis which is all implemented in Sage -- has been here for years now -- does this for all isogenies of prime degree p such that X_0^+(p) has genus 0.

Sage's isogeny capabilities are in my opinion very good. It is the only software in which one can compute isogenies as easily, or compute complete isogeny classes over arbitrary number fields -- there are hundreds (or more) lines devoted to this in several files. I implemented all that because I needed it in my own work (e.g. to compute the full isogeny classes for all the elliptic curves in the LMFDB, which are defined over number fields of degree up to 6). If other people need different capabilities, for example implementations which work better over large finite fields, they are welcome to implement them. But the fact that not everything of this type has been implemented does *not* imply that "Sage is severely lacking generic [algorithms]". I strongly dispute that statement, even without "severely".

Constructing isogenies given only domain and codomain and degree is something which is important for elliptic curves over finite fields because of elliptic curve cryptography, but much less so over number fields. So someone else can implement it.

Now I will put on my to-do list to actually fix the bug which leads to the reported behaviour.

comment:3 Changed 3 years ago by defeo

Hi John. I'm sorry if you got offended by my comment. It's 3 years old, I did not know about your code for grouping factors of the division polynomial back then (if it was already in Sage at the time).

I realize now that my diagnosis was misguided: indeed, phi.dual() seems to be correctly computing normalized models, so I'm not sure what's causing this failure. If you find the root cause of the bug, I'll be happy to review the fix.

Constructing isogenies given only domain and codomain and degree is something which is important for elliptic curves over finite fields because of elliptic curve cryptography, but much less so over number fields. So someone else can implement it.

I haven't really had any time to do "maths" developement in Sage in the past 3 years, but I hope things to change soon...

I'll open a separate ticket for my suggestion of falling back to the generic code when the models are not normalized.

comment:4 Changed 3 years ago by cremona

No worries -- I just did not want the misleading impression to go uncorrected. The code I mentioned went in soon after Kimi's thesis was finished in 2013.

Note: See TracTickets for help on using tickets.