Extend elliptic curve isogenies to arbitrary prime degrees

[JohnCremona]

As of Sage 5.4, we can compute l-isogenies of elliptic curves only for l=2,3,5,7,13 (the ones for which X_0(l) has genus 0), together with some "sporadic" degrees which can occur over QQ.

In this ticket we will add extra functionality to be able to compute l-isogenies for arbitrary prime degrees.

Apply only: attachment: trac_13615_combined_4th_review.patch​, attachment: trac_13615_fix.patch

CC: @sagetrac-kimi @defeo

Component: elliptic curves

Keywords: isogenies, sd51, sd52

Author: Kimi Tsukazaki, John Cremona, Luca De Feo

Reviewer: John Cremona, Jenny Cooley, Samuele Anni, Luca De Feo

Merged: sage-5.13.beta0

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

[JohnCremona]

comment:2

I have two patches which are ready for testing.

[JohnCremona]

Changed keywords from isogenies to isogenies, sd51

[JohnCremona]

comment:3

# Files:

1. ell_curve_isogeny_split.patch
2. isogeny_genus_0.patch

# Description:

1. It splits the current "ell_curve_isogeny.py" to two files, namely
   "ell_curve_isogeny.py" and "isogeny_genus_0.py".

2. It adds new isogeny codes in "isogeny_genus_0.py", including:

・l-isogeny computation using generic kernel polynomial for
　　　　　l = 11,17,19,23,29,31,41,47,59,71. (from ch.5 in Kimi's thesis)

・l-isogeny computation using the l-division polynomial (from ch.3 in Kimi's thesis)

# NOTE:
Please apply ell_curve_isogeny_split.patch first and
then apply isogeny_genus_0.patch.

[JohnCremona]

Attachment: ell_curve_isogeny_split.patch.gz

Attachment: isogeny_genus_0.patch.gz

[JohnCremona]

Author: Kimi Tsukazaki

[JohnCremona]

comment:5

The patches apply fine to version 5.11.beta3. But there are some issues which need to be addressed:

1. The references to John C and Jenny C need to be moved to the new file, and the header information on the new file needs to be completed with additional author, dates, etc. with a citation to Kimi's thesis for justification of all the formulae.

2. Some new functions have no docstring, or no one-line summary: hyperelliptic_isogeny_data, Psi2.

3. least_semi_primitive docstring missing an asterisk.

4. The interface to the isogeny function from the elliptic curve class in ell_field.py needs to be updated, otherwise the new functionality will not be available to users! This should include a new helper function in isogenies_genus_0 which makes the decision about which of the three functions to call. It will also be necessary to disable the code which allows for an empty list of primes to be given, since we can now handle all primes with the sole exception of the characteristic.

[JohnCremona]

Reviewer: John Cremona, Jenny Cooley, Samuele Anni

[JohnCremona]

comment:8

Replying to @JohnCremona:
I am starting to work on the points listed above.

[JohnCremona]

Attachment: trac_13615_review.patch.gz

Apply after previous patches

[JohnCremona]

Changed author from Kimi Tsukazaki to Kimi Tsukazaki, John Cremona

[defeo]

comment:10

Nice work! I'm reviewing the patch, but of all the new functions in isogeny_genus_0.py the only one I could understand is isogenies_prime_degree_general().

I can't seem to find Kimi's thesis online. Could you put it somewhere, so that we can compare with the theory? Also, it would be nice if the docstrings of the new functions pointed to the corresponding sections in Kimi's thesis (assuming that's the only source).

Here's more thoughts:

• It seems weird that isogenies_prime_degree_general() is in isogeny_genus_0.py. Why is it not in ell_curve_isogeny.py() or in some other generic place?

• least_semi_primitive() is a purely internal function, I would rename it to _least_semi_primitive().

• In the docstring of least_semi_primitive(), the {1,-1} should be \{1,-1\} (although this is not very important if you follow my previous suggestion).

[JohnCremona]

comment:11

I have put the thesis at http://homepages.warwick.ac.uk/staff/J.E.Cremona/theses/tsukazaki.pdf
since it has not appeared on Warwick's official repository (but was approved in July 2013).

I agree that the filename is not wonderful, but we did want to split off the general isogeny code now in ell_curve_isogeny from the special cases. Perhaps you are right that the "general" one belongs in the other file.

least_semi_primitive is indeed internal. If I thught there would be other applications I might have suggested putting it with primitive roots and similar functions.

I am about to go on holiday, but feel free to ask more questions if you don't mind a little delay.

[defeo]

Changed reviewer from John Cremona, Jenny Cooley, Samuele Anni to John Cremona, Jenny Cooley, Samuele Anni, Luca De Feo

[defeo]

Branch: u/defeo/trac13615

[defeo]

comment:12

Thanks for the link, and congratulations to Kimi. I quickly read it through. I obviously didn't check line by line, but no doubt that you got the maths and the coding right. So, I'm ready to give a positive review.

I agree that the filename is not wonderful, but we did want to split off the general isogeny code now in ell_curve_isogeny from the special cases. Perhaps you are right that the "general" one belongs in the other file.

I agree, it is best to keep specific algorithms separate from the isogeny class. On second thought, all the algorithms in that file have something in common: they are generic algorithms only practical for small prime degrees (as you suggest in the title of the doc page). Maybe it's just the filename that needs to be changed. What about isogenies_small_degree.py?

least_semi_primitive is indeed internal. If I thught there would be other applications I might have suggested putting it with primitive roots and similar functions.

I had the same feeling about the variable isog_table and the function hyperelliptic_isogeny_data. Hence, I renamed all the three by adding an underscore in front of them.

I also

• Edited the copyright banner by adding your names
• Fixed the docstring of _least_semi_primitive()
• Added ALGORITHM:: sections to some functions, pointing to the relevant chapter in Kimi's thesis.

I'm attaching my reviewer's patch. I'm working with the git repo, and I'm confused by this directory renaming stuff, so I guess it'll be easier if I link to my git branch on trac.

I'm not giving a positive review right away, so that you can review my patch, and give your opinion on renaming the file. Enjoy vacation!

[defeo]

reviewer patch

[defeo]

comment:13

Attachment: trac_13615_second_review.patch.gz

Found the time to make a mercurial patch.

Apply: ell_curve_isogeny_split.patch, isogeny_genus_0.patch, trac_13615_review.patch, trac_13615_second_review.patch​

[defeo]

comment:35

My fault. I removed a test for the primality of l in isogenies_sporadic_Q.

[JohnCremona]

comment:36

Replying to @defeo:

My fault. I removed a test for the primality of l in isogenies_sporadic_Q.

No problem. I'm about to upload a small addition patch for this.

[JohnCremona]

Changed author from Kimi Tsukazaki, John Cremona to Kimi Tsukazaki, John Cremona, Luca de Feo

[JohnCremona]

comment:37

Done. It's slightly better than before since now E.isogenies_prime_degree("rubbish") calmly raises an error saying that "rubbish" is no prime, rather than an error saying that strings do not have an is_prime attribute. (But I did not add another doctest for that.)

Since I am happy with your other reviewer changes, if you agree with this latest one then I think you can set this to positive review.

[defeo]

comment:38

Looks ok to me. Good job.

[defeo]

Changed author from Kimi Tsukazaki, John Cremona, Luca de Feo to Kimi Tsukazaki, John Cremona, Luca De Feo

[defeo]

comment:39

Apply only: trac_13615_combined_4th_review.patch​, trac_13615_fix.patch​

[JohnCremona]

comment:40

Replying to @defeo:

Looks ok to me. Good job.

Thanks -- and a good case of thorough and constructive reviewing! Sorry about /d/D/.

[defeo]

comment:41

Patchbot is still not getting it. I don't know what else to do!

Apply trac_13615_combined_4th_review.patch​

Apply trac_13615_fix.patch​

[JohnCremona]

comment:43

I changed the formatting of the patching instructions. Perhaps that will work.

[jdemeyer]

comment:45

There are problems while building the documentation:

dochtml.log:[plane_cur] /scratch/release/merger/sage-5.13.beta0/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/isogeny_small_degree.py:docstring of sage.schemes.elliptic_curves.isogeny_small_degree.isogenies_prime_degree_general:15: WARNING: Literal block expected; none found.
dochtml.log:[plane_cur] /scratch/release/merger/sage-5.13.beta0/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/isogeny_small_degree.py:docstring of sage.schemes.elliptic_curves.isogeny_small_degree.isogenies_prime_degree_genus_0:22: WARNING: Literal block expected; none found.
dochtml.log:[plane_cur] /scratch/release/merger/sage-5.13.beta0/local/lib/python2.7/site-packages/sage/schemes/elliptic_curves/isogeny_small_degree.py:docstring of sage.schemes.elliptic_curves.isogeny_small_degree.isogenies_prime_degree_genus_plus_0:21: WARNING: Literal block expected; none found.

[jdemeyer]

comment:46

Note: the errors above usually arise if you do something like

EXAMPLES::

Some explaining text::

    sage: 1+1
    2

The above is wrong, the first line should have single colon.

[JohnCremona]

comment:47

Certainly -- and this will be fixed very soon! Don't let 5.13 out without this, please!

[JohnCremona]

Attachment: trac_13615_fix.patch.gz

small fix for trac_13615_combined_4th_review.patch

[JohnCremona]

comment:48

I changed the second patch which fixes the three problems (which were, in fact all the same: an ALGORITHM block erroneously had :: instead of :).

I took the liberty of changing back to positive review.

[jdemeyer]

Merged: sage-5.13.beta0

[JohnCremona]

comment:50

We have a problem, which I am investigating:

sage: K.<i> = NumberField(x^2+1)                                                                         
sage: E = EllipticCurve(K,[-2*i-1,0])                                                                   
sage: E.isogenies_prime_degree(17)
...

ValueError: The polynomial does not define a finite subgroup of the elliptic curve.

while in fact this curve does have 2 17-isogenies:

sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_prime_degree_general
sage: isogenies_prime_degree_general(E,17) # rather slow
[Isogeny of degree 17 from Elliptic Curve defined by y^2 = x^3 + (-2*i-1)*x over Number Field in i with defining polynomial x^2 + 1 to Elliptic Curve defined by y^2 = x^3 + (-82*i-641)*x over Number Field in i with defining polynomial x^2 + 1,
 Isogeny of degree 17 from Elliptic Curve defined by y^2 = x^3 + (-2*i-1)*x over Number Field in i with defining polynomial x^2 + 1 to Elliptic Curve defined by y^2 = x^3 + (-562*i+319)*x over Number Field in i with defining polynomial x^2 + 1]

This was found by Warwick undergraduate Warren Moore, and I am looking into it....

This problem can be fixed as follows: in line 1770 of isogeny_small_degree.py replace -27c4 by -27c4/1296 (or -c4/48) twice. Something similar may be needed on line 1690 (the j=0 endomorphism case). I will check that out and make a patch.

See #15434 for the extra patch!