Opened 7 years ago

Closed 6 years ago

Last modified 6 years ago

#13615 closed enhancement (fixed)

Extend elliptic curve isogenies to arbitrary prime degrees

Reported by: cremona Owned by: John Cremona
Priority: major Milestone: sage-5.13
Component: elliptic curves Keywords: isogenies, sd51, sd52
Cc: kimi, defeo Merged in: sage-5.13.beta0
Authors: Kimi Tsukazaki, John Cremona, Luca De Feo Reviewers: John Cremona, Jenny Cooley, Samuele Anni, Luca De Feo
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by cremona)

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: trac_13615_combined_4th_review.patch​, trac_13615_fix.patch

Attachments (9)

ell_curve_isogeny_split.patch (145.1 KB) - added by cremona 6 years ago.
isogeny_genus_0.patch (42.5 KB) - added by cremona 6 years ago.
trac_13615_review.patch (54.7 KB) - added by cremona 6 years ago.
Apply after previous patches
trac_13615_second_review.patch (43.8 KB) - added by defeo 6 years ago.
reviewer patch
trac_13615_extra.patch (43.9 KB) - added by cremona 6 years ago.
Apply after all previous patches
trac_13615_3rd_review.patch (2.0 KB) - added by defeo 6 years ago.
trac_13615_combined.patch (216.8 KB) - added by cremona 6 years ago.
Replaces all previous patches
trac_13615_combined_4th_review.patch (202.3 KB) - added by defeo 6 years ago.
trac_13615_fix.patch (2.0 KB) - added by cremona 6 years ago.
small fix for trac_13615_combined_4th_review.patch

Download all attachments as: .zip

Change History (59)

comment:1 Changed 7 years ago by defeo

  • Cc defeo added

comment:2 Changed 6 years ago by cremona

  • Keywords sd51 added

I have two patches which are ready for testing.

comment:3 Changed 6 years ago by cremona

# 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".
  1. 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 my thesis)

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

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

Version 0, edited 6 years ago by cremona (next)

Changed 6 years ago by cremona

Changed 6 years ago by cremona

comment:4 Changed 6 years ago by cremona

  • Authors set to Kimi Tsukazaki

comment:5 Changed 6 years ago by cremona

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.
  1. Some new functions have no docstring, or no one-line summary: hyperelliptic_isogeny_data, Psi2.
  1. least_semi_primitive docstring missing an asterisk.
  1. 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.

comment:6 Changed 6 years ago by cremona

  • Reviewers set to John Cremona, Jenny Cooley, Samuele Anni
  • Status changed from new to needs_review

comment:7 follow-up: Changed 6 years ago by cremona

  • Status changed from needs_review to needs_work

comment:8 in reply to: ↑ 7 Changed 6 years ago by cremona

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

Changed 6 years ago by cremona

Apply after previous patches

comment:9 Changed 6 years ago by cremona

  • Authors changed from Kimi Tsukazaki to Kimi Tsukazaki, John Cremona
  • Description modified (diff)
  • Milestone changed from sage-5.11 to sage-5.12
  • Status changed from needs_work to needs_review

comment:10 Changed 6 years ago by defeo

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).

comment:11 follow-up: Changed 6 years ago by cremona

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.

comment:12 in reply to: ↑ 11 Changed 6 years ago by defeo

  • Branch set to u/defeo/trac13615
  • Description modified (diff)
  • Reviewers changed from John Cremona, Jenny Cooley, Samuele Anni to John Cremona, Jenny Cooley, Samuele Anni, Luca De Feo

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!

Changed 6 years ago by defeo

reviewer patch

comment:13 Changed 6 years ago by defeo

  • Branch u/defeo/trac13615 deleted
  • Description modified (diff)

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​

comment:14 Changed 6 years ago by cremona

Thanks a lot for making your changes in to a mercurial patch. Looking at it reminded me that I had always intended to remove the global (to the module) isog_table anyway, replacing it with a function as we did for the hyperelliptic_isogeny_data which plays a rather similar role. IN addition this meanse that instaed of having these mysterious numbers in there, I can put in a function which by default returns stored values, but can also compute them on the fly, which then (1) allowed doctesting and (2) makes it clearer where they come from (currently this is partially done in an extended comment). The result will be something like the (cached) function Psi(l, use_stored=True) which was converted to this form when someone noticed that this file contributed a non-negligible amount to Sage's startup time. I will do that tomorrow.

comment:15 Changed 6 years ago by defeo

Excellent! I should have time to review it before the end of the week.

Note that the patches do not apply anymore, according to patchbot.

Changed 6 years ago by cremona

Apply after all previous patches

comment:16 Changed 6 years ago by cremona

  • Description modified (diff)

I had no trouble in applying the 4 patches to 5.12.beta4. The additional patch does what I said before, i.e. replaces the global dict called _isog_table with a function _sporadic_Q_data which by default returns precomputed data, but can also compute it from scratch. The function has a test (which only takes 2 seconds to run) which checks that the computed and stored values are the same for all 11 possible inputs.

I think we have now done everything mentioned above, except for possibly changing the name of the new file from isogeny_genus_0 to isogeny_small_degree. If you want that, I can change my patch to do that too.

I am just running a full test...done.

Last edited 6 years ago by cremona (previous) (diff)

comment:17 follow-up: Changed 6 years ago by defeo

Just doctested with --all --long. Everything looks ok.

The patchbot is still skipping my patch, so I guess it won't be able to apply.

Maybe folding all the patches into a single one could help; that would also be a good occasion to change the file name. Can you do it?

comment:18 in reply to: ↑ 17 Changed 6 years ago by cremona

Replying to defeo:

Just doctested with --all --long. Everything looks ok.

The patchbot is still skipping my patch, so I guess it won't be able to apply.

Maybe folding all the patches into a single one could help; that would also be a good occasion to change the file name. Can you do it?

OK, I will do that. Watch this space.

comment:19 Changed 6 years ago by cremona

  • Description modified (diff)

comment:20 Changed 6 years ago by cremona

The new patch trac_13615_combined.patch combines all thre previous patches into one, which applies to 5.12.beta4. The only additional difference is that the new file which was called isogeny_genus_0.py is now classed isogeny_small_degree.py.

Ready for a final review!

Changed 6 years ago by defeo

comment:21 Changed 6 years ago by defeo

  • Description modified (diff)

Here's one more review. I've corrected a few spelling mistakes, and modified isogenies_sporadic_Q to be slightly more readable and pythonic.

It is good to go for me. Feel free to give positive review if you accept my reviewer patch.

Apply only: trac_13615_combined.patch, trac_13615_3rd_review.patch

comment:22 Changed 6 years ago by cremona

You have done rather more than that in your second change. Yes, it looks neater; but I have used the knowledge that isogenies of these degrees exist if and only if the j-invariant is one of the known values. On the other hand, the _sporadic_Q_data function will quickly determine whichm if any, of these apply. I still feel something has been lost though: at most one of these l values gives an isogeny, but your core will try them all.

comment:23 Changed 6 years ago by defeo

Yes, definitely. But,

  1. These j-invariants are big numbers, hard to compare visually. Before your last patch they used to be only in one place: _isog_table, after they were replicated in _sporadic_Q_data and isogenies_sporadic_Q, making it harder to verify that you did not leave out some j by mistake.
  1. Efficiency-wise, your code does 11 + 11 equality tests in QQ, mine does 11 * 11. An equality test in QQ takes ~3μs on my laptop, and indeed testing isogenies_sporadic_Q I get a ~300μs slowdown for a curve which has no isogeny (and thus goes through all tests). That's a serious penalty (about 10x) for a curve which has no isogeny, but it's negligible for a sporadic curve (where it takes in the order of milliseconds to return the isogeny). Do we really care?

comment:24 Changed 6 years ago by defeo

  • Keywords sd52 added

comment:25 follow-up: Changed 6 years ago by cremona

I definitely agree that there should be only one place where this finite list of exceptional pairs is listed! One advantage of the old dict was that one could easily check whether (l,j) was in isog_table.keys(), and perhaps that list should still exist somewhere, and used in the function _sporadic_data_Q instead of what I do now.

You have certainly done a thorough job checking the timings! Of course, curves which are not sporadic are the vast majority (and I use this code on files with many thousands of curves) so I would like to eliminate them from consideration as soon as possible.

Here's one possible plan: have a global dict with 11 entries, the keys are the sporadic j-invariants and the vales are the associated primes l. Then _sporadic_data_Q can check if the j-invariant is a key and return what it does now if so, while isogenies_sporadic_Q can also use the same dict. If you like that, I will do it.

comment:26 in reply to: ↑ 25 Changed 6 years ago by defeo

If it's sheer speed you're looking after, you should revert to the old code. The time for isogenies_sporadic_Q on a non-sporadic curve has gone up from ~4μs before this ticket, to ~35μs after your patch (to ~340μs after mine).

Either you can keep the old _isog_table and implement _sporadic_Q_data just for test purposes (and why not make doctests #optional, in that case), or, if you want to improve startup time, you make _sporadic_Q_data return the whole dictionary, and apply the @cached_function decorator to it.

Changed 6 years ago by cremona

Replaces all previous patches

comment:27 Changed 6 years ago by cremona

  • Description modified (diff)

I have repalced my combined patch with one which corrects the typo you found and implements an alternative solution to the problem you noted. Back to you!

comment:28 Changed 6 years ago by cremona

I did not notive your last comment until I had posted mine (and the new patch), but I have had enough on this for today...

Changed 6 years ago by defeo

comment:29 Changed 6 years ago by defeo

Apply only: trac_13615_combined_4th_review.patch​

_sporadic_Q_data takes less than 1/2 a second to compute its output from scratch for any j-invariant. I see no reason not to compute the data on the fly and store it with @cached_function

This new patch removes the precomputed data from the code (most of it is moved in the doctest), and makes _sporadic_Q_data a cached function. isogeny_sporadic_Q now tests its input against a dictionary mapping j-invariants to degrees, and is thus much faster on non-sporadic curves.

Here is the timings I get on my laptop.

sage: from sage.schemes.elliptic_curves.isogeny_small_degree import sporadic_j, _sporadic_Q_data
sage: for j in sporadic_j.keys():
....:    timeit('_sporadic_Q_data(j)', globals=globals().update({'j':j}), number=1, repeat=1)
1 loops, best of 1: 167 ms per loop
1 loops, best of 1: 71.2 ms per loop
1 loops, best of 1: 400 ms per loop
1 loops, best of 1: 69.1 ms per loop
1 loops, best of 1: 59.7 ms per loop
1 loops, best of 1: 110 ms per loop
1 loops, best of 1: 139 ms per loop
1 loops, best of 1: 64.8 ms per loop
1 loops, best of 1: 107 ms per loop
1 loops, best of 1: 113 ms per loop
1 loops, best of 1: 66.9 ms per loop

sage: from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_sporadic_Q
sage: E = EllipticCurve(j=QQ.random_element())
sage: timeit('isogenies_sporadic_Q(E)', globals=globals())
625 loops, best of 3: 1.1 µs per loop

What do you think of it?

comment:30 Changed 6 years ago by defeo

  • Description modified (diff)

Apply only: trac_13615_combined_4th_review.patch​

comment:31 Changed 6 years ago by cremona

Thanks a lot for your work on this. I'll look at it properly as soon as I can.

Some explanation: I generally prefer to do things algebraically, and when I first coded these _sporadic_Q_data things about 4 years ago, I did so algebraically, except for the 163 case for which which that was impractical. When I started to write the function a few days ago, which returned precomputed data by default but also could do the computations on the fly, I also went for the algebraic approach for the first few (which is very quick for 11, 17, 19), but then for simplicity decided that if any were to be computed via floating point then they all could be. Precision issues were easy to deal with, since we already knew the correct result, so I just did some experimentation to determine how much precision was required to get it right in each case. And as you just observed, the result is so quick in every case that having the precomputed values stored is no longer necessary! I still like the idea of preserving the "correct" data in doctests, though they do take up quite a few lines in the file.

comment:32 follow-up: Changed 6 years ago by defeo

I preserved all the data, except the 163 case, in the doctest. But if you like it, I have nothing against including 163 too.

comment:33 in reply to: ↑ 32 Changed 6 years ago by cremona

Replying to defeo:

I preserved all the data, except the 163 case, in the doctest. But if you like it, I have nothing against including 163 too.

It isn't necessary, as any test which computes a 163-isogeny from an elliptic curve with that invariant will implicitly check that the output is correct.

comment:34 Changed 6 years ago by cremona

I'm just investigating this:

File "sage/schemes/elliptic_curves/ell_rational_field.py", line 4191, in sage.schemes.elliptic_curves.ell_rational_field.EllipticCurve_rational_field.reduction.isogenies_prime_degree
Failed example:
    E.isogenies_prime_degree(4) 
Expected:
    Traceback (most recent call last):
    ...
    ValueError: 4 is not prime.
Got:
    []

Previously the function isogenies_sporadic_Q checked that l is primes before tesing to see if (l,j) is in the list. Now we don't. But I think that this is fair, since by definition there are no sporadic l-isogenies if l is not prime. So I am moving the (pseudo-)primality test for l into ell_rational_field where the failing doctest is.

Last edited 6 years ago by cremona (previous) (diff)

comment:35 follow-up: Changed 6 years ago by defeo

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

comment:36 in reply to: ↑ 35 Changed 6 years ago by cremona

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.

comment:37 Changed 6 years ago by cremona

  • Authors changed from Kimi Tsukazaki, John Cremona to Kimi Tsukazaki, John Cremona, Luca de Feo
  • Description modified (diff)

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.

comment:38 follow-up: Changed 6 years ago by defeo

  • Authors changed from Kimi Tsukazaki, John Cremona, Luca de Feo to Kimi Tsukazaki, John Cremona, Luca De Feo
  • Status changed from needs_review to positive_review

Looks ok to me. Good job.

comment:39 Changed 6 years ago by defeo

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

comment:40 in reply to: ↑ 38 Changed 6 years ago by cremona

Replying to defeo:

Looks ok to me. Good job.

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

comment:41 Changed 6 years ago by defeo

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​

comment:42 Changed 6 years ago by cremona

  • Description modified (diff)

comment:43 Changed 6 years ago by cremona

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

comment:44 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.12 to sage-5.13

comment:45 Changed 6 years ago by jdemeyer

  • Status changed from positive_review to needs_work

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.

comment:46 Changed 6 years ago by jdemeyer

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.

comment:47 Changed 6 years ago by cremona

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

Changed 6 years ago by cremona

small fix for trac_13615_combined_4th_review.patch

comment:48 Changed 6 years ago by cremona

  • Status changed from needs_work to positive_review

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.

comment:49 Changed 6 years ago by jdemeyer

  • Merged in set to sage-5.13.beta0
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:50 Changed 6 years ago by cremona

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 -27*c4 by -27*c4/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!

Last edited 6 years ago by cremona (previous) (diff)
Note: See TracTickets for help on using tickets.