Opened 9 years ago

Closed 5 years ago

#11327 closed defect (fixed)

isogeny code uses deprecated(?) multi-variate gcd

Reported by: cjh Owned by: cremona
Priority: major Milestone: sage-6.4
Component: elliptic curves Keywords: isogeny multivariate dual
Cc: Merged in:
Authors: John Cremona Reviewers: Chris Wuthrich
Report Upstream: N/A Work issues:
Branch: 4abaea8 (Commits) Commit: 4abaea8b85879a9fbe91404e8a43b57f994938de
Dependencies: Stopgaps:

Description (last modified by cremona)

New branch sorts out the use of uni- versus multi-variate polynomials systematically, and makes a lot of minor improvements and simplifications and improves many docstrings. The specific errors originally reported here (see below) and at #16779 are fixed.

In sage.schemes.elliptic_curves.ell_curve_isogeny (of sage 4.6.2) the routine two_torsion_part() invokes a gcd on two polynomials. When the polynomials belong to a multivariate ring, an error occurs. Perhaps this is because the gcd routine in sage.rings.polynomial.multi_polynomial_element has been commented out (because it uses Singular?!).

Converting psi (and perhaps psi2) to univariate polynomials within two_torsion_part() before taking the gcd seems to work, but there seems to be other code in the module which uses a multivariate ring when a univariate ring would suffice (e.g. in init_from_kernel_polynomial).

I discovered this error when trying to create a dual isogeny (for an elliptic curve over Q(t)). The original isogeny was a cyclic 2-isogeny and thus the dual should also be a cyclic 2-isogeny. Without giving more details on how I created the curve, let me simply report the error message which results when I call isogeny.dual():

Traceback (most recent call last):

File "<stdin>", line 1, in <module> File "_sage_input_5.py", line 10, in <module>

exec compile(u'open("_code_.py","w").write("# -*- coding: utf-8 -*-
n" + _support_.preparse_worksheet_cell(base64.b64decode("cHNpID0gcGhpLmR1YWwoKQ=="),globals())+"
n"); execfile(os.path.abspath("_code_.py"))

File "", line 1, in <module>

File "/private/var/folders/4V/4VAOdForFpanThca5kJ5xE+++TI/-Tmp-/tmp8DXIBC/_code_.py", line 2, in <module>

exec compile(u'psi = phi.dual()

File "", line 1, in <module>

File "/Applications/sage/local/lib/python2.6/site-packages/sage/schemes/elliptic_curves/ell_curve_isogeny.py", line 3248, in dual

phi_hat = EllipticCurveIsogeny?(E1, None, E2, d)

File "/Applications/sage/local/lib/python2.6/site-packages/sage/schemes/elliptic_curves/ell_curve_isogeny.py", line 914, in init

self.init_from_kernel_polynomial(kernel, degree)

File "/Applications/sage/local/lib/python2.6/site-packages/sage/schemes/elliptic_curves/ell_curve_isogeny.py", line 2038, in init_from_kernel_polynomial

psi_G = two_torsion_part(E, poly_ring, psi, degree);

File "/Applications/sage/local/lib/python2.6/site-packages/sage/schemes/elliptic_curves/ell_curve_isogeny.py", line 453, in two_torsion_part

psi_G = poly_ring(psi.gcd(psi_2))

File "element.pyx", line 327, in sage.structure.element.Element.getattr (sage/structure/element.c:2715) File "parent.pyx", line 277, in sage.structure.parent.getattr_from_other_class (sage/structure/parent.c:2841) File "parent.pyx", line 177, in sage.structure.parent.raise_attribute_error (sage/structure/parent.c:2663)

AttributeError?: 'MPolynomial_polydict' object has no attribute 'gcd'

Attachments (1)

trac_11327-isogs.patch (5.3 KB) - added by cremona 8 years ago.
Applies to 4.7.1.rc1

Download all attachments as: .zip

Change History (13)

comment:1 Changed 9 years ago by cremona

I have run into this myself, but never had time to fix it as the problem always seemed to grow bigger. Feel free to make a patch! Before you do, please note that there are other patches around which affect this file -- one of which splits it into two -- so it would best to work on top of that.

Changed 8 years ago by cremona

Applies to 4.7.1.rc1

comment:2 Changed 8 years ago by cremona

  • Milestone changed from sage-4.7.1 to sage-4.7.2

The patch trac_11327-isogs.patch was made by me from an edited version of ell_curve_isogeny.py which cjh sent me. It needs work.

comment:3 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:4 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:5 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:6 Changed 5 years ago by cremona

  • Dependencies set to #16779

Very sorry to have forgotten about this after 3 years. I just created a new ticket and a simpler solution to a similar problem at #16779. The patch I will put there does not solve the problem over function fields, and this ticket should remain open but with #16779 as a dependency.

comment:7 Changed 5 years ago by cremona

  • Authors set to John Cremona
  • Branch set to u/cremona/ticket/11327
  • Commit set to e043ae8eeb0ed3b12f748131904d5e0e0476a83e
  • Status changed from new to needs_review

New commits:

e043ae8#11327,#16779: improvements to isogeny class internals and docstrings

comment:8 Changed 5 years ago by cremona

  • Dependencies #16779 deleted
  • Description modified (diff)

comment:9 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:10 Changed 5 years ago by wuthrich

  • Branch changed from u/cremona/ticket/11327 to u/wuthrich/ticket/11327
  • Commit changed from e043ae8eeb0ed3b12f748131904d5e0e0476a83e to 4abaea8b85879a9fbe91404e8a43b57f994938de
  • Reviewers set to Chris Wuthrich
  • Status changed from needs_review to positive_review

All tests pass and the problem is solved indeed. Thanks also for all the improvments on the documentation.

Tiny: There is a "#" appearing in the documentation of the class EllipticCurveIsogeny. So I changed that.


New commits:

4abaea8trac 16779: small correction in doc

comment:11 Changed 5 years ago by cremona

Thanks a lot!

comment:12 Changed 5 years ago by vbraun

  • Branch changed from u/wuthrich/ticket/11327 to 4abaea8b85879a9fbe91404e8a43b57f994938de
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.