#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 )
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)
Change History (59)
comment:1 Changed 6 years ago by
- Cc defeo added
comment:2 Changed 6 years ago by
- Keywords sd51 added
comment:3 Changed 6 years ago by
# Files:
- ell_curve_isogeny_split.patch
- isogeny_genus_0.patch
# Description:
- It splits the current "ell_curve_isogeny.py" to two files, namely "ell_curve_isogeny.py" and "isogeny_genus_0.py".
- 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.
Changed 6 years ago by
Changed 6 years ago by
comment:4 Changed 6 years ago by
comment:5 Changed 6 years ago by
The patches apply fine to version 5.11.beta3. But there are some issues which need to be addressed:
- 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.
- Some new functions have no docstring, or no one-line summary:
hyperelliptic_isogeny_data
,Psi2
.
least_semi_primitive
docstring missing an asterisk.
- 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 inisogenies_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
- Reviewers set to John Cremona, Jenny Cooley, Samuele Anni
- Status changed from new to needs_review
comment:7 follow-up: ↓ 8 Changed 6 years ago by
- Status changed from needs_review to needs_work
comment:8 in reply to: ↑ 7 Changed 6 years ago by
Replying to cremona: I am starting to work on the points listed above.
comment:9 Changed 6 years ago by
- 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
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 inisogeny_genus_0.py
. Why is it not inell_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: ↓ 12 Changed 6 years ago by
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
- 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!
comment:13 Changed 6 years ago by
- 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
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
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.
comment:16 Changed 6 years ago by
- 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.
comment:17 follow-up: ↓ 18 Changed 6 years ago by
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
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
- Description modified (diff)
comment:20 Changed 6 years ago by
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
comment:21 Changed 6 years ago by
- 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
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
Yes, definitely. But,
- 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
andisogenies_sporadic_Q
, making it harder to verify that you did not leave out some j by mistake.
- Efficiency-wise, your code does 11 + 11 equality tests in
QQ
, mine does 11 * 11. An equality test inQQ
takes ~3μs on my laptop, and indeed testingisogenies_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
- Keywords sd52 added
comment:25 follow-up: ↓ 26 Changed 6 years ago by
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
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.
comment:27 Changed 6 years ago by
- 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
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
comment:29 Changed 6 years ago by
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
- Description modified (diff)
Apply only: trac_13615_combined_4th_review.patch
comment:31 Changed 6 years ago by
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: ↓ 33 Changed 6 years ago by
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
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
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.
comment:35 follow-up: ↓ 36 Changed 6 years ago by
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
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
- 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: ↓ 40 Changed 6 years ago by
- Status changed from needs_review to positive_review
Looks ok to me. Good job.
comment:39 Changed 6 years ago by
Apply only: trac_13615_combined_4th_review.patch, trac_13615_fix.patch
comment:40 in reply to: ↑ 38 Changed 6 years ago by
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
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
- Description modified (diff)
comment:43 Changed 6 years ago by
I changed the formatting of the patching instructions. Perhaps that will work.
comment:44 Changed 6 years ago by
- Milestone changed from sage-5.12 to sage-5.13
comment:45 Changed 6 years ago by
- 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
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
Certainly -- and this will be fixed very soon! Don't let 5.13 out without this, please!
comment:48 Changed 6 years ago by
- 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
- 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
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!
I have two patches which are ready for testing.