Sage: Ticket #13615: Extend elliptic curve isogenies to arbitrary prime degrees
https://trac.sagemath.org/ticket/13615
<p>
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.
</p>
<p>
In this ticket we will add extra functionality to be able to compute l-isogenies for arbitrary prime degrees.
</p>
<p>
Apply only: <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/13615/trac_13615_combined_4th_review.patch" title="Attachment 'trac_13615_combined_4th_review.patch' in Ticket #13615">trac_13615_combined_4th_review.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/13615/trac_13615_combined_4th_review.patch" title="Download"></a>, <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/13615/trac_13615_fix.patch" title="Attachment 'trac_13615_fix.patch' in Ticket #13615">trac_13615_fix.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/13615/trac_13615_fix.patch" title="Download"></a>
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/13615
Trac 1.1.6defeoThu, 29 Nov 2012 16:21:12 GMTcc changed
https://trac.sagemath.org/ticket/13615#comment:1
https://trac.sagemath.org/ticket/13615#comment:1
<ul>
<li><strong>cc</strong>
<em>defeo</em> added
</li>
</ul>
TicketcremonaMon, 22 Jul 2013 08:47:25 GMTkeywords changed
https://trac.sagemath.org/ticket/13615#comment:2
https://trac.sagemath.org/ticket/13615#comment:2
<ul>
<li><strong>keywords</strong>
<em>sd51</em> added
</li>
</ul>
<p>
I have two patches which are ready for testing.
</p>
TicketcremonaMon, 22 Jul 2013 08:51:48 GMT
https://trac.sagemath.org/ticket/13615#comment:3
https://trac.sagemath.org/ticket/13615#comment:3
<p>
# Files:
</p>
<ol><li>ell_curve_isogeny_split.patch
</li><li>isogeny_genus_0.patch
</li></ol><p>
# Description:
</p>
<ol><li>It splits the current "ell_curve_isogeny.py" to two files, namely
"ell_curve_isogeny.py" and "isogeny_genus_0.py".
</li></ol><ol start="2"><li>It adds new isogeny codes in "isogeny_genus_0.py", including:
</li></ol><blockquote>
<p>
・l-isogeny computation using generic kernel polynomial for
</p>
<blockquote>
<p>
l = 11,17,19,23,29,31,41,47,59,71. (from ch.5 in Kimi's thesis)
</p>
</blockquote>
</blockquote>
<blockquote>
<p>
・l-isogeny computation using the l-division polynomial (from ch.3 in Kimi's thesis)
</p>
</blockquote>
<p>
# NOTE:
Please apply ell_curve_isogeny_split.patch first and
then apply isogeny_genus_0.patch.
</p>
TicketcremonaMon, 22 Jul 2013 08:52:20 GMTattachment set
https://trac.sagemath.org/ticket/13615
https://trac.sagemath.org/ticket/13615
<ul>
<li><strong>attachment</strong>
set to <em>ell_curve_isogeny_split.patch</em>
</li>
</ul>
TicketcremonaMon, 22 Jul 2013 08:52:47 GMTattachment set
https://trac.sagemath.org/ticket/13615
https://trac.sagemath.org/ticket/13615
<ul>
<li><strong>attachment</strong>
set to <em>isogeny_genus_0.patch</em>
</li>
</ul>
TicketcremonaMon, 22 Jul 2013 14:20:03 GMTauthor set
https://trac.sagemath.org/ticket/13615#comment:4
https://trac.sagemath.org/ticket/13615#comment:4
<ul>
<li><strong>author</strong>
set to <em>Kimi Tsukazaki</em>
</li>
</ul>
TicketcremonaMon, 22 Jul 2013 15:24:05 GMT
https://trac.sagemath.org/ticket/13615#comment:5
https://trac.sagemath.org/ticket/13615#comment:5
<p>
The patches apply fine to version 5.11.beta3. But there are some issues which need to be addressed:
</p>
<ol><li>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.
</li></ol><ol start="2"><li>Some new functions have no docstring, or no one-line summary: <code>hyperelliptic_isogeny_data</code>, <code>Psi2</code>.
</li></ol><ol start="3"><li><code>least_semi_primitive</code> docstring missing an asterisk.
</li></ol><ol start="4"><li>The interface to the isogeny function from the elliptic curve class in <code>ell_field.py</code> needs to be updated, otherwise the new functionality will not be available to users! This should include a new helper function in <code>isogenies_genus_0</code> 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.
</li></ol><p>
</p>
TicketcremonaMon, 22 Jul 2013 15:25:00 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/13615#comment:6
https://trac.sagemath.org/ticket/13615#comment:6
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>John Cremona, Jenny Cooley, Samuele Anni</em>
</li>
</ul>
TicketcremonaMon, 22 Jul 2013 15:25:53 GMTstatus changed
https://trac.sagemath.org/ticket/13615#comment:7
https://trac.sagemath.org/ticket/13615#comment:7
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
TicketcremonaThu, 25 Jul 2013 14:23:07 GMT
https://trac.sagemath.org/ticket/13615#comment:8
https://trac.sagemath.org/ticket/13615#comment:8
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/13615#comment:7" title="Comment 7">cremona</a>:
I am starting to work on the points listed above.
</p>
TicketcremonaFri, 26 Jul 2013 11:13:49 GMTattachment set
https://trac.sagemath.org/ticket/13615
https://trac.sagemath.org/ticket/13615
<ul>
<li><strong>attachment</strong>
set to <em>trac_13615_review.patch</em>
</li>
</ul>
<p>
Apply after previous patches
</p>
TicketcremonaFri, 26 Jul 2013 11:15:38 GMTstatus, author, description, milestone changed
https://trac.sagemath.org/ticket/13615#comment:9
https://trac.sagemath.org/ticket/13615#comment:9
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>author</strong>
changed from <em>Kimi Tsukazaki</em> to <em>Kimi Tsukazaki, John Cremona</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/13615?action=diff&version=9">diff</a>)
</li>
<li><strong>milestone</strong>
changed from <em>sage-5.11</em> to <em>sage-5.12</em>
</li>
</ul>
TicketdefeoWed, 21 Aug 2013 18:59:36 GMT
https://trac.sagemath.org/ticket/13615#comment:10
https://trac.sagemath.org/ticket/13615#comment:10
<p>
Nice work! I'm reviewing the patch, but of all the new functions in <code>isogeny_genus_0.py</code> the only one I could understand is <code>isogenies_prime_degree_general()</code>.
</p>
<p>
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).
</p>
<p>
Here's more thoughts:
</p>
<ul><li>It seems weird that <code>isogenies_prime_degree_general()</code> is in <code>isogeny_genus_0.py</code>. Why is it not in <code>ell_curve_isogeny.py()</code> or in some other <em>generic</em> place?
</li></ul><ul><li><code>least_semi_primitive()</code> is a purely internal function, I would rename it to <code>_least_semi_primitive()</code>.
</li></ul><ul><li>In the docstring of <code>least_semi_primitive()</code>, the <code>{1,-1}</code> should be <code>\{1,-1\}</code> (although this is not very important if you follow my previous suggestion).
</li></ul>
TicketcremonaWed, 21 Aug 2013 19:24:05 GMT
https://trac.sagemath.org/ticket/13615#comment:11
https://trac.sagemath.org/ticket/13615#comment:11
<p>
I have put the thesis at <a class="ext-link" href="http://homepages.warwick.ac.uk/staff/J.E.Cremona/theses/tsukazaki.pdf"><span class="icon"></span>http://homepages.warwick.ac.uk/staff/J.E.Cremona/theses/tsukazaki.pdf</a>
since it has not appeared on Warwick's official repository (but was approved in July 2013).
</p>
<p>
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.
</p>
<p>
<code>least_semi_primitive</code> is indeed internal. If I thught there would be other applications I might have suggested putting it with primitive roots and similar functions.
</p>
<p>
I am about to go on holiday, but feel free to ask more questions if you don't mind a little delay.
</p>
TicketdefeoThu, 22 Aug 2013 18:22:26 GMTreviewer, description changed; branch set
https://trac.sagemath.org/ticket/13615#comment:12
https://trac.sagemath.org/ticket/13615#comment:12
<ul>
<li><strong>reviewer</strong>
changed from <em>John Cremona, Jenny Cooley, Samuele Anni</em> to <em>John Cremona, Jenny Cooley, Samuele Anni, Luca De Feo</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/13615?action=diff&version=12">diff</a>)
</li>
<li><strong>branch</strong>
set to <em>u/defeo/trac13615</em>
</li>
</ul>
<p>
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.
</p>
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
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 <code>isogenies_small_degree.py</code>?
</p>
<blockquote class="citation">
<p>
<code>least_semi_primitive</code> is indeed internal. If I thught there would be other applications I might have suggested putting it with primitive roots and similar functions.
</p>
</blockquote>
<p>
I had the same feeling about the variable <code>isog_table</code> and the function <code>hyperelliptic_isogeny_data</code>. Hence, I renamed all the three by adding an underscore in front of them.
</p>
<p>
I also
</p>
<ul><li>Edited the copyright banner by adding your names
</li><li>Fixed the docstring of <code>_least_semi_primitive()</code>
</li><li>Added <code>ALGORITHM::</code> sections to some functions, pointing to the relevant chapter in Kimi's thesis.
</li></ul><p>
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.
</p>
<p>
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!
</p>
TicketdefeoWed, 28 Aug 2013 16:18:50 GMTattachment set
https://trac.sagemath.org/ticket/13615
https://trac.sagemath.org/ticket/13615
<ul>
<li><strong>attachment</strong>
set to <em>trac_13615_second_review.patch</em>
</li>
</ul>
<p>
reviewer patch
</p>
TicketdefeoWed, 28 Aug 2013 16:22:39 GMTdescription changed; branch deleted
https://trac.sagemath.org/ticket/13615#comment:13
https://trac.sagemath.org/ticket/13615#comment:13
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/13615?action=diff&version=13">diff</a>)
</li>
<li><strong>branch</strong>
<em>u/defeo/trac13615</em> deleted
</li>
</ul>
<p>
Found the time to make a mercurial patch.
</p>
<p>
Apply: ell_curve_isogeny_split.patch, isogeny_genus_0.patch, trac_13615_review.patch, trac_13615_second_review.patch
</p>
TicketcremonaTue, 03 Sep 2013 15:52:50 GMT
https://trac.sagemath.org/ticket/13615#comment:14
https://trac.sagemath.org/ticket/13615#comment:14
<p>
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.
</p>
TicketdefeoTue, 03 Sep 2013 16:05:57 GMT
https://trac.sagemath.org/ticket/13615#comment:15
https://trac.sagemath.org/ticket/13615#comment:15
<p>
Excellent! I should have time to review it before the end of the week.
</p>
<p>
Note that the patches do not apply anymore, according to patchbot.
</p>
TicketcremonaWed, 04 Sep 2013 10:52:13 GMTattachment set
https://trac.sagemath.org/ticket/13615
https://trac.sagemath.org/ticket/13615
<ul>
<li><strong>attachment</strong>
set to <em>trac_13615_extra.patch</em>
</li>
</ul>
<p>
Apply after all previous patches
</p>
TicketcremonaWed, 04 Sep 2013 10:57:00 GMTdescription changed
https://trac.sagemath.org/ticket/13615#comment:16
https://trac.sagemath.org/ticket/13615#comment:16
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/13615?action=diff&version=16">diff</a>)
</li>
</ul>
<p>
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.
</p>
<p>
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.
</p>
<p>
I am just running a full test...done.
</p>
TicketdefeoWed, 04 Sep 2013 13:11:45 GMT
https://trac.sagemath.org/ticket/13615#comment:17
https://trac.sagemath.org/ticket/13615#comment:17
<p>
Just doctested with <code>--all --long</code>. Everything looks ok.
</p>
<p>
The patchbot is still skipping my patch, so I guess it won't be able to apply.
</p>
<p>
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?
</p>
TicketcremonaWed, 04 Sep 2013 13:15:47 GMT
https://trac.sagemath.org/ticket/13615#comment:18
https://trac.sagemath.org/ticket/13615#comment:18
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/13615#comment:17" title="Comment 17">defeo</a>:
</p>
<blockquote class="citation">
<p>
Just doctested with <code>--all --long</code>. Everything looks ok.
</p>
<p>
The patchbot is still skipping my patch, so I guess it won't be able to apply.
</p>
<p>
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?
</p>
</blockquote>
<p>
OK, I will do that. Watch this space.
</p>
TicketcremonaWed, 04 Sep 2013 13:41:09 GMTdescription changed
https://trac.sagemath.org/ticket/13615#comment:19
https://trac.sagemath.org/ticket/13615#comment:19
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/13615?action=diff&version=19">diff</a>)
</li>
</ul>
TicketcremonaWed, 04 Sep 2013 13:42:48 GMT
https://trac.sagemath.org/ticket/13615#comment:20
https://trac.sagemath.org/ticket/13615#comment:20
<p>
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.
</p>
<p>
Ready for a final review!
</p>
TicketdefeoWed, 04 Sep 2013 14:32:25 GMTattachment set
https://trac.sagemath.org/ticket/13615
https://trac.sagemath.org/ticket/13615
<ul>
<li><strong>attachment</strong>
set to <em>trac_13615_3rd_review.patch</em>
</li>
</ul>
TicketdefeoWed, 04 Sep 2013 14:35:17 GMTdescription changed
https://trac.sagemath.org/ticket/13615#comment:21
https://trac.sagemath.org/ticket/13615#comment:21
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/13615?action=diff&version=21">diff</a>)
</li>
</ul>
<p>
Here's one more review. I've corrected a few spelling mistakes, and modified <code>isogenies_sporadic_Q</code> to be slightly more readable and pythonic.
</p>
<p>
It is good to go for me. Feel free to give positive review if you accept my reviewer patch.
</p>
<p>
Apply only: trac_13615_combined.patch, trac_13615_3rd_review.patch
</p>
TicketcremonaWed, 04 Sep 2013 14:50:43 GMT
https://trac.sagemath.org/ticket/13615#comment:22
https://trac.sagemath.org/ticket/13615#comment:22
<p>
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.
</p>
TicketdefeoWed, 04 Sep 2013 15:38:30 GMT
https://trac.sagemath.org/ticket/13615#comment:23
https://trac.sagemath.org/ticket/13615#comment:23
<p>
Yes, definitely. But,
</p>
<ol><li>These j-invariants are big numbers, hard to compare visually. Before your last patch they used to be only in one place: <code>_isog_table</code>, after they were replicated in <code>_sporadic_Q_data</code> <strong>and</strong> <code>isogenies_sporadic_Q</code>, making it harder to verify that you did not leave out some j by mistake.
</li></ol><ol start="2"><li>Efficiency-wise, your code does 11 + 11 equality tests in <code>QQ</code>, mine does 11 * 11. An equality test in <code>QQ</code> takes ~3μs on my laptop, and indeed testing <code>isogenies_sporadic_Q</code> 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?
</li></ol>
TicketdefeoWed, 04 Sep 2013 15:42:31 GMTkeywords changed
https://trac.sagemath.org/ticket/13615#comment:24
https://trac.sagemath.org/ticket/13615#comment:24
<ul>
<li><strong>keywords</strong>
<em>sd52</em> added
</li>
</ul>
TicketcremonaWed, 04 Sep 2013 15:46:29 GMT
https://trac.sagemath.org/ticket/13615#comment:25
https://trac.sagemath.org/ticket/13615#comment:25
<p>
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.
</p>
<p>
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.
</p>
<p>
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.
</p>
TicketdefeoWed, 04 Sep 2013 16:29:00 GMT
https://trac.sagemath.org/ticket/13615#comment:26
https://trac.sagemath.org/ticket/13615#comment:26
<p>
If it's sheer speed you're looking after, you should revert to the old code. The time for <code>isogenies_sporadic_Q</code> 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).
</p>
<p>
Either you can keep the old <code>_isog_table</code> and implement <code>_sporadic_Q_data</code> just for test purposes (and why not make doctests #optional, in that case), or, if you want to improve startup time, you make <code>_sporadic_Q_data</code> return the whole dictionary, and apply the <code>@cached_function</code> decorator to it.
</p>
TicketcremonaWed, 04 Sep 2013 16:29:33 GMTattachment set
https://trac.sagemath.org/ticket/13615
https://trac.sagemath.org/ticket/13615
<ul>
<li><strong>attachment</strong>
set to <em>trac_13615_combined.patch</em>
</li>
</ul>
<p>
Replaces all previous patches
</p>
TicketcremonaWed, 04 Sep 2013 16:31:02 GMTdescription changed
https://trac.sagemath.org/ticket/13615#comment:27
https://trac.sagemath.org/ticket/13615#comment:27
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/13615?action=diff&version=27">diff</a>)
</li>
</ul>
<p>
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!
</p>
TicketcremonaWed, 04 Sep 2013 16:32:18 GMT
https://trac.sagemath.org/ticket/13615#comment:28
https://trac.sagemath.org/ticket/13615#comment:28
<p>
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...
</p>
TicketdefeoFri, 06 Sep 2013 23:05:25 GMTattachment set
https://trac.sagemath.org/ticket/13615
https://trac.sagemath.org/ticket/13615
<ul>
<li><strong>attachment</strong>
set to <em>trac_13615_combined_4th_review.patch</em>
</li>
</ul>
TicketdefeoFri, 06 Sep 2013 23:15:03 GMT
https://trac.sagemath.org/ticket/13615#comment:29
https://trac.sagemath.org/ticket/13615#comment:29
<p>
Apply only: trac_13615_combined_4th_review.patch
</p>
<p>
<code>_sporadic_Q_data</code> 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 <code>@cached_function</code>
</p>
<p>
This new patch removes the precomputed data from the code (most of it is moved in the doctest), and makes <code>_sporadic_Q_data</code> a cached function. <code>isogeny_sporadic_Q</code> now tests its input against a dictionary mapping j-invariants to degrees, and is thus much faster on non-sporadic curves.
</p>
<p>
Here is the timings I get on my laptop.
</p>
<pre class="wiki">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
</pre><p>
What do you think of it?
</p>
TicketdefeoFri, 06 Sep 2013 23:16:10 GMTdescription changed
https://trac.sagemath.org/ticket/13615#comment:30
https://trac.sagemath.org/ticket/13615#comment:30
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/13615?action=diff&version=30">diff</a>)
</li>
</ul>
<p>
Apply only: trac_13615_combined_4th_review.patch
</p>
TicketcremonaSat, 07 Sep 2013 13:41:28 GMT
https://trac.sagemath.org/ticket/13615#comment:31
https://trac.sagemath.org/ticket/13615#comment:31
<p>
Thanks a lot for your work on this. I'll look at it properly as soon as I can.
</p>
<p>
Some explanation: I generally prefer to do things algebraically, and when I first coded these <code>_sporadic_Q_data</code> 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.
</p>
TicketdefeoSat, 07 Sep 2013 13:46:52 GMT
https://trac.sagemath.org/ticket/13615#comment:32
https://trac.sagemath.org/ticket/13615#comment:32
<p>
I preserved all the data, except the 163 case, in the doctest. But if you like it, I have nothing against including 163 too.
</p>
TicketcremonaSat, 07 Sep 2013 14:07:29 GMT
https://trac.sagemath.org/ticket/13615#comment:33
https://trac.sagemath.org/ticket/13615#comment:33
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/13615#comment:32" title="Comment 32">defeo</a>:
</p>
<blockquote class="citation">
<p>
I preserved all the data, except the 163 case, in the doctest. But if you like it, I have nothing against including 163 too.
</p>
</blockquote>
<p>
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.
</p>
TicketcremonaSat, 07 Sep 2013 14:19:18 GMT
https://trac.sagemath.org/ticket/13615#comment:34
https://trac.sagemath.org/ticket/13615#comment:34
<p>
I'm just investigating this:
</p>
<pre class="wiki">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:
[]
</pre><p>
Previously the function <code>isogenies_sporadic_Q</code> 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 <code>ell_rational_field</code> where the failing doctest is.
</p>
TicketdefeoSat, 07 Sep 2013 14:21:42 GMT
https://trac.sagemath.org/ticket/13615#comment:35
https://trac.sagemath.org/ticket/13615#comment:35
<p>
My fault. I removed a test for the primality of l in <code>isogenies_sporadic_Q</code>.
</p>
TicketcremonaSat, 07 Sep 2013 14:36:48 GMT
https://trac.sagemath.org/ticket/13615#comment:36
https://trac.sagemath.org/ticket/13615#comment:36
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/13615#comment:35" title="Comment 35">defeo</a>:
</p>
<blockquote class="citation">
<p>
My fault. I removed a test for the primality of l in <code>isogenies_sporadic_Q</code>.
</p>
</blockquote>
<p>
No problem. I'm about to upload a small addition patch for this.
</p>
TicketcremonaSat, 07 Sep 2013 14:51:18 GMTdescription, author changed
https://trac.sagemath.org/ticket/13615#comment:37
https://trac.sagemath.org/ticket/13615#comment:37
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/13615?action=diff&version=37">diff</a>)
</li>
<li><strong>author</strong>
changed from <em>Kimi Tsukazaki, John Cremona</em> to <em>Kimi Tsukazaki, John Cremona, Luca de Feo</em>
</li>
</ul>
<p>
Done. It's slightly better than before since now <code>E.isogenies_prime_degree("rubbish")</code> calmly raises an error saying that "rubbish" is no prime, rather than an error saying that strings do not have an <code>is_prime</code> attribute. (But I did not add another doctest for that.)
</p>
<p>
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.
</p>
TicketdefeoSat, 07 Sep 2013 14:57:19 GMTstatus, author changed
https://trac.sagemath.org/ticket/13615#comment:38
https://trac.sagemath.org/ticket/13615#comment:38
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>author</strong>
changed from <em>Kimi Tsukazaki, John Cremona, Luca de Feo</em> to <em>Kimi Tsukazaki, John Cremona, Luca De Feo</em>
</li>
</ul>
<p>
Looks ok to me. Good job.
</p>
TicketdefeoSat, 07 Sep 2013 14:58:08 GMT
https://trac.sagemath.org/ticket/13615#comment:39
https://trac.sagemath.org/ticket/13615#comment:39
<p>
Apply only: trac_13615_combined_4th_review.patch, trac_13615_fix.patch
</p>
TicketcremonaSat, 07 Sep 2013 14:59:33 GMT
https://trac.sagemath.org/ticket/13615#comment:40
https://trac.sagemath.org/ticket/13615#comment:40
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/13615#comment:38" title="Comment 38">defeo</a>:
</p>
<blockquote class="citation">
<p>
Looks ok to me. Good job.
</p>
</blockquote>
<p>
Thanks -- and a good case of thorough and constructive reviewing! Sorry about /d/D/.
</p>
TicketdefeoSat, 07 Sep 2013 15:01:42 GMT
https://trac.sagemath.org/ticket/13615#comment:41
https://trac.sagemath.org/ticket/13615#comment:41
<p>
Patchbot is still not getting it. I don't know what else to do!
</p>
<p>
Apply trac_13615_combined_4th_review.patch
</p>
<p>
Apply trac_13615_fix.patch
</p>
TicketcremonaSat, 07 Sep 2013 17:10:40 GMTdescription changed
https://trac.sagemath.org/ticket/13615#comment:42
https://trac.sagemath.org/ticket/13615#comment:42
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/13615?action=diff&version=42">diff</a>)
</li>
</ul>
TicketcremonaSat, 07 Sep 2013 17:11:06 GMT
https://trac.sagemath.org/ticket/13615#comment:43
https://trac.sagemath.org/ticket/13615#comment:43
<p>
I changed the formatting of the patching instructions. Perhaps that will work.
</p>
TicketjdemeyerThu, 26 Sep 2013 15:47:44 GMTmilestone changed
https://trac.sagemath.org/ticket/13615#comment:44
https://trac.sagemath.org/ticket/13615#comment:44
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.12</em> to <em>sage-5.13</em>
</li>
</ul>
TicketjdemeyerSun, 29 Sep 2013 16:17:17 GMTstatus changed
https://trac.sagemath.org/ticket/13615#comment:45
https://trac.sagemath.org/ticket/13615#comment:45
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
There are problems while building the documentation:
</p>
<pre class="wiki">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.
</pre>
TicketjdemeyerSun, 29 Sep 2013 16:27:57 GMT
https://trac.sagemath.org/ticket/13615#comment:46
https://trac.sagemath.org/ticket/13615#comment:46
<p>
Note: the errors above usually arise if you do something like
</p>
<pre class="wiki">EXAMPLES::
Some explaining text::
sage: 1+1
2
</pre><p>
The above is <strong>wrong</strong>, the first line should have single colon.
</p>
TicketcremonaSun, 29 Sep 2013 16:53:08 GMT
https://trac.sagemath.org/ticket/13615#comment:47
https://trac.sagemath.org/ticket/13615#comment:47
<p>
Certainly -- and this will be fixed very soon! Don't let 5.13 out without this, please!
</p>
TicketcremonaMon, 30 Sep 2013 10:48:01 GMTattachment set
https://trac.sagemath.org/ticket/13615
https://trac.sagemath.org/ticket/13615
<ul>
<li><strong>attachment</strong>
set to <em>trac_13615_fix.patch</em>
</li>
</ul>
<p>
small fix for trac_13615_combined_4th_review.patch
</p>
TicketcremonaMon, 30 Sep 2013 10:50:08 GMTstatus changed
https://trac.sagemath.org/ticket/13615#comment:48
https://trac.sagemath.org/ticket/13615#comment:48
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
</ul>
<p>
I changed the second patch which fixes the three problems (which were, in fact all the same: an ALGORITHM block erroneously had :: instead of :).
</p>
<p>
I took the liberty of changing back to positive review.
</p>
TicketjdemeyerWed, 02 Oct 2013 06:35:02 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/13615#comment:49
https://trac.sagemath.org/ticket/13615#comment:49
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-5.13.beta0</em>
</li>
</ul>
TicketcremonaMon, 18 Nov 2013 09:21:22 GMT
https://trac.sagemath.org/ticket/13615#comment:50
https://trac.sagemath.org/ticket/13615#comment:50
<p>
We have a problem, which I am investigating:
</p>
<pre class="wiki">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.
</pre><p>
while in fact this curve does have 2 17-isogenies:
</p>
<pre class="wiki">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]
</pre><p>
This was found by Warwick undergraduate Warren Moore, and I am looking into it....
</p>
<p>
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.
</p>
<p>
See <a class="closed ticket" href="https://trac.sagemath.org/ticket/15434" title="defect: elliptic curve isogenies: follow-up to #13615 (closed: fixed)">#15434</a> for the extra patch!
</p>
Ticket