Sage: Ticket #22345: Elliptic curve isogenies over number fields II: implement Billerey's algorithm for reducible primes
https://trac.sagemath.org/ticket/22345
<p>
This follows in from <a class="closed ticket" href="https://trac.sagemath.org/ticket/22343" title="enhancement: Elliptic curve isogenies over number fields I: speed up Larsen's ... (closed: fixed)">#22343</a> which is a dependency. We implement Billerey's algorithm for finding the set of reducible primes for an elliptic curve without CM over a number field. This is based on an implementation by Ciaran Schembri for a masters' project at Warwick.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/22345
Trac 1.1.6aly.deinesSat, 22 Jul 2017 16:55:55 GMTbranch set
https://trac.sagemath.org/ticket/22345#comment:1
https://trac.sagemath.org/ticket/22345#comment:1
<ul>
<li><strong>branch</strong>
set to <em>u/aly.deines/elliptic_curve_isogenies_over_number_fields_ii__implement_billeray_s_algorithm_for_reducible_primes</em>
</li>
</ul>
Ticketaly.deinesSat, 22 Jul 2017 16:59:59 GMTkeywords, commit set
https://trac.sagemath.org/ticket/22345#comment:2
https://trac.sagemath.org/ticket/22345#comment:2
<ul>
<li><strong>keywords</strong>
<em>elliptic</em> <em>curves</em> <em>isogenies</em> <em>number</em> <em>fields</em> added
</li>
<li><strong>commit</strong>
set to <em>bfe5ca4f9bdd21e47a9e87560b516f158cd9a58a</em>
</li>
</ul>
<p>
I started putting Cremona's code for Billerey's algorithm into appropriate places in Sage. I cleaned it up a bit and addes some documentations.
</p>
<p>
Things left to do or fix:
</p>
<ul><li>add documentation
</li><li>only works if the curve has integral discriminant
</li><li>incorporate into isogeny finding for EC's over number fields
</li><li>more examples, especially over larger fields
</li><li>timings against other methods
</li><li>probably more . . .
</li></ul>
Ticketaly.deinesSat, 22 Jul 2017 17:00:28 GMTmilestone changed
https://trac.sagemath.org/ticket/22345#comment:3
https://trac.sagemath.org/ticket/22345#comment:3
<ul>
<li><strong>milestone</strong>
changed from <em>sage-7.6</em> to <em>sage-wishlist</em>
</li>
</ul>
Ticketaly.deinesSat, 22 Jul 2017 17:02:16 GMTpriority changed
https://trac.sagemath.org/ticket/22345#comment:4
https://trac.sagemath.org/ticket/22345#comment:4
<ul>
<li><strong>priority</strong>
changed from <em>major</em> to <em>minor</em>
</li>
</ul>
TicketcremonaTue, 01 Aug 2017 10:56:57 GMT
https://trac.sagemath.org/ticket/22345#comment:5
https://trac.sagemath.org/ticket/22345#comment:5
<p>
Thanks for the work so far. I'm working on this again now and will go through your to-do list.
</p>
TicketcremonaWed, 02 Aug 2017 14:57:14 GMTstatus, commit, branch changed
https://trac.sagemath.org/ticket/22345#comment:6
https://trac.sagemath.org/ticket/22345#comment:6
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
changed from <em>bfe5ca4f9bdd21e47a9e87560b516f158cd9a58a</em> to <em>1a1e7a6b6cda1c22de1e6711bb4c320ac0506047</em>
</li>
<li><strong>branch</strong>
changed from <em>u/aly.deines/elliptic_curve_isogenies_over_number_fields_ii__implement_billeray_s_algorithm_for_reducible_primes</em> to <em>u/cremona/22345</em>
</li>
</ul>
<p>
I have rearranged the code quite a bit. The technical parts of Billerey I though were better kept separate and not as methods of the elliptic curve class itself, so I put them in gal_reps_number_field.py. (Alternatives were a new file, or on isogeny_class.py.) In isogeny_class.py I also refactored the code to produce a finite set of primes, separating out the cm case, and allowing the user a choice of 3 algorithms, Billerey, Larson or 'heuristic', the latter being non-rigorous, just testing all primes up a to a given bound to see if they passthe necessary local conditions. This is never the default and the docstring makes it clear that the output is not guaranteed complete.
</p>
<p>
This leaves a much simplified method reducible_primes() in the elliptic curves class itself, while the isogeny class code uses the new function to find the reducible primes, with Billerey the default algorithm.
</p>
<p>
I could put in more examples if desired. I have not done systematic timing tests, but note that until the work done on another ticket Larson's method could not handle fields of degree 5 and up at all.
</p>
<p>
While writing this I realised that I have not yet provided the possibility for E.isogeny_class() to use a non-default algorithm, and will add that, but I'll leave the ticket at "needs review" so that patchbots get working on it.
</p>
TicketcremonaWed, 02 Aug 2017 16:05:25 GMT
https://trac.sagemath.org/ticket/22345#comment:7
https://trac.sagemath.org/ticket/22345#comment:7
<p>
Some timings: with z=zeta_101 and E=[0,1,0,z,z], reducible_primes_naive(E) with default parameters (max_l=1000, num_P=100) returns [2, 607] in 2m, while reducible_primes_naive(E, max_l=2000, num_P=200) returns [2] in about the same time (starting from scratch; if you do the second right after the first it is faster since some previous work is cached).
Working on this example revealed something stupid only indirectly relevant to this ticket: computing the 2-isogeny takes for ever! The stupid reason is that after computing the isogenous curve it tries to compute its global_minimal model. Which involves computing the class group of K.....
That needs fixing somehow but on a different ticket.
</p>
TicketgitFri, 04 Aug 2017 14:12:31 GMTcommit changed
https://trac.sagemath.org/ticket/22345#comment:8
https://trac.sagemath.org/ticket/22345#comment:8
<ul>
<li><strong>commit</strong>
changed from <em>1a1e7a6b6cda1c22de1e6711bb4c320ac0506047</em> to <em>d3643b5fa076eb17231a1b4ca7d3a2a9e9bb5e05</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=d3643b5fa076eb17231a1b4ca7d3a2a9e9bb5e05"><span class="icon"></span>d3643b5</a></td><td><code>#22345 improved e.c. isogenies over number fields</code>
</td></tr></table>
TicketcremonaFri, 04 Aug 2017 14:17:52 GMT
https://trac.sagemath.org/ticket/22345#comment:9
https://trac.sagemath.org/ticket/22345#comment:9
<p>
The last commit makes several improvements after more testing. In Billerey's algorithm itself the improvement is to only use B. to find reducible primes greater than some lower bound (default 200) which never occur in practice, using the local test for smaller primes. Secondly, after noticing that some "easy" examples were taking forever on account of class group computations (which in turn are triggered by the conversion to global minimal models) I added a minimal_models flag which defaults to True to give the old behaviour but which can be set to False. New doctest to illustrate this are added. This flag had to be put into dozens of places from the top-level E.isogeny_class() down through various layers to the underlying isogeny code.
</p>
<p>
I am currently checking that all the additional docstrings compile OK...
</p>
TicketcremonaFri, 04 Aug 2017 14:18:06 GMTstatus changed
https://trac.sagemath.org/ticket/22345#comment:10
https://trac.sagemath.org/ticket/22345#comment:10
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
TicketgitFri, 04 Aug 2017 15:05:12 GMTcommit changed
https://trac.sagemath.org/ticket/22345#comment:11
https://trac.sagemath.org/ticket/22345#comment:11
<ul>
<li><strong>commit</strong>
changed from <em>d3643b5fa076eb17231a1b4ca7d3a2a9e9bb5e05</em> to <em>252f04856bc6c61a11ebf3cc85dd86b656771bdd</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=252f04856bc6c61a11ebf3cc85dd86b656771bdd"><span class="icon"></span>252f048</a></td><td><code>#22345 fixed some bad docstrings</code>
</td></tr></table>
TicketcremonaFri, 04 Aug 2017 15:05:38 GMTstatus changed
https://trac.sagemath.org/ticket/22345#comment:12
https://trac.sagemath.org/ticket/22345#comment:12
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketcremonaSun, 06 Aug 2017 15:49:45 GMTsummary changed
https://trac.sagemath.org/ticket/22345#comment:13
https://trac.sagemath.org/ticket/22345#comment:13
<ul>
<li><strong>summary</strong>
changed from <em>Elliptic curve isogenies over number fields II: implement Billeray's algorithm for reducible primes</em> to <em>Elliptic curve isogenies over number fields II: implement Billerey's algorithm for reducible primes</em>
</li>
</ul>
TicketjpfloriMon, 21 Aug 2017 16:43:00 GMT
https://trac.sagemath.org/ticket/22345#comment:14
https://trac.sagemath.org/ticket/22345#comment:14
<p>
Looks like this need rebasing, or is it only trac's git which is not smart enough?
</p>
TicketcremonaMon, 21 Aug 2017 18:26:43 GMT
https://trac.sagemath.org/ticket/22345#comment:15
https://trac.sagemath.org/ticket/22345#comment:15
<p>
I'll rebase. I thought it was based on a recent version but maybe not
</p>
TicketgitTue, 22 Aug 2017 07:45:44 GMTcommit changed
https://trac.sagemath.org/ticket/22345#comment:16
https://trac.sagemath.org/ticket/22345#comment:16
<ul>
<li><strong>commit</strong>
changed from <em>252f04856bc6c61a11ebf3cc85dd86b656771bdd</em> to <em>645c6b7c2904204b1c2e1bedff6264c99abed4ef</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=70b8f12e61587bcbec409a6e3a5bb8e3996f56fa"><span class="icon"></span>70b8f12</a></td><td><code>Merge branch 'develop' into 22345</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=645c6b7c2904204b1c2e1bedff6264c99abed4ef"><span class="icon"></span>645c6b7</a></td><td><code>#22345 rebase + small speedup</code>
</td></tr></table>
TicketcremonaTue, 22 Aug 2017 07:52:15 GMT
https://trac.sagemath.org/ticket/22345#comment:17
https://trac.sagemath.org/ticket/22345#comment:17
<p>
That took longer than expected. The rebase was easy but when I tested all of schemes/elliptic_curves there was a long time warning coming from a test in kraus.py, relating to an earlier fix for <a class="closed ticket" href="https://trac.sagemath.org/ticket/20737" title="defect: Use of representative_prime may fail in finding semi-global minimal ... (closed: fixed)">#20737</a>, marked as 15s but taking a minute (in semi_global_minimal_model()). I am not sure where the regression came from (not at all to do with this ticket, which in fact makes it possible for semi_global_minimal_model() not to be called when computing isogenies, precisely for the reason that it can take too long when the class group is large). I did two things which help: first, use prime_range() instead of primes() in the primes_of_bounded_norm methods for number fields, and secondly to use a larger bound when searching for a prime in an ideal class -- since if it fails it doubles the bound, which is of course wasteful since the small ones are re-tested. If the resulting time (25s for me for this test) is deemed too long we can mark it 'not tested', but it is there precisely because this case is a hard one.
</p>
TicketkedlayaWed, 23 Aug 2017 22:51:17 GMTcc changed
https://trac.sagemath.org/ticket/22345#comment:18
https://trac.sagemath.org/ticket/22345#comment:18
<ul>
<li><strong>cc</strong>
<em>kedlaya</em> added
</li>
</ul>
Ticketaly.deinesThu, 24 Aug 2017 23:22:33 GMTbranch changed
https://trac.sagemath.org/ticket/22345#comment:19
https://trac.sagemath.org/ticket/22345#comment:19
<ul>
<li><strong>branch</strong>
changed from <em>u/cremona/22345</em> to <em>u/aly.deines/22345</em>
</li>
</ul>
TicketcremonaThu, 05 Oct 2017 18:50:47 GMTcommit changed
https://trac.sagemath.org/ticket/22345#comment:20
https://trac.sagemath.org/ticket/22345#comment:20
<ul>
<li><strong>commit</strong>
changed from <em>645c6b7c2904204b1c2e1bedff6264c99abed4ef</em> to <em>51c21c3b4ca9c55e5d8f7d8d9a924e7627fc766e</em>
</li>
</ul>
<p>
Aly can you explain the branch change you made on Aug 24 which I only just noticed? I cannot read your branch (it shows on trac but not as a link) so I don't know what you changed.
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=51c21c3b4ca9c55e5d8f7d8d9a924e7627fc766e"><span class="icon"></span>51c21c3</a></td><td><code>Merge branch 'u/cremona/22345' of git://trac.sagemath.org/sage into t/22345/22345</code>
</td></tr></table>
TicketchapotonThu, 07 Dec 2017 15:28:34 GMTstatus changed
https://trac.sagemath.org/ticket/22345#comment:21
https://trac.sagemath.org/ticket/22345#comment:21
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
branch does not apply
</p>
TicketcremonaTue, 10 Jul 2018 08:50:00 GMTstatus, commit, branch changed
https://trac.sagemath.org/ticket/22345#comment:22
https://trac.sagemath.org/ticket/22345#comment:22
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
changed from <em>51c21c3b4ca9c55e5d8f7d8d9a924e7627fc766e</em> to <em>94f711426d546c9d28503f3ff82e85d7257e3ce7</em>
</li>
<li><strong>branch</strong>
changed from <em>u/aly.deines/22345</em> to <em>u/cremona/22345</em>
</li>
</ul>
<p>
I have merged in 8.3.rc0, fixed conflicts and checked that all tests pass. I hope I will not have to do this again a year from now!
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=94f711426d546c9d28503f3ff82e85d7257e3ce7"><span class="icon"></span>94f7114</a></td><td><code>Merge branch 'develop' into 22345</code>
</td></tr></table>
TicketchapotonTue, 10 Jul 2018 18:48:34 GMTdescription, branch, commit changed; reviewer set
https://trac.sagemath.org/ticket/22345#comment:23
https://trac.sagemath.org/ticket/22345#comment:23
<ul>
<li><strong>reviewer</strong>
set to <em>Frédéric Chapoton</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/22345?action=diff&version=23">diff</a>)
</li>
<li><strong>branch</strong>
changed from <em>u/cremona/22345</em> to <em>public/ticket/22345</em>
</li>
<li><strong>commit</strong>
changed from <em>94f711426d546c9d28503f3ff82e85d7257e3ce7</em> to <em>2423f7aa9cd4523bc82a4627513acbcf13b786ae</em>
</li>
</ul>
<p>
Please look at my commit, fixing some details about py3:
</p>
<ul><li>using <code>r"""</code> for documentation containing latex operators
</li></ul><ul><li>do not use <code>.next</code>
</li></ul><p>
If you agree with my changes, you can set to positive.. But I do not claim anything about checking the math, so you may want to wait for an expert's opinion.
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=2423f7aa9cd4523bc82a4627513acbcf13b786ae"><span class="icon"></span>2423f7a</a></td><td><code>trac 22345 some details (py3 compatibility, please)</code>
</td></tr></table>
TicketcremonaTue, 10 Jul 2018 19:03:38 GMTstatus changed
https://trac.sagemath.org/ticket/22345#comment:24
https://trac.sagemath.org/ticket/22345#comment:24
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
I am happy with your changes. Thanks. I have discussed the ideas here with people who have not actually looked at the code in detail. I think the only reasonable thing to do is to get it merged so that it gets used (if there is anyone out there interested). I have used this a lot in computing isogeny classes of curves for the LMFDB, which is how I found out that the old code in Sage was completely useless over number fields of degree >4.
</p>
TicketchapotonWed, 11 Jul 2018 18:50:44 GMTmilestone changed
https://trac.sagemath.org/ticket/22345#comment:25
https://trac.sagemath.org/ticket/22345#comment:25
<ul>
<li><strong>milestone</strong>
changed from <em>sage-wishlist</em> to <em>sage-8.3</em>
</li>
</ul>
TicketvbraunSat, 11 Aug 2018 16:55:06 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/22345#comment:26
https://trac.sagemath.org/ticket/22345#comment:26
<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>branch</strong>
changed from <em>public/ticket/22345</em> to <em>2423f7aa9cd4523bc82a4627513acbcf13b786ae</em>
</li>
</ul>
Ticket