Elliptic curve isogenies over number fields II: implement Billerey's algorithm for reducible primes

[JohnCremona]

This follows in from #22343 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.

CC: @adeines @kedlaya

Component: elliptic curves

Keywords: isogenies

Author: John Cremona

Branch/Commit: 2423f7a

Reviewer: Frédéric Chapoton

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

[adeines]

Branch: u/aly.deines/elliptic_curve_isogenies_over_number_fields_ii__implement_billeray_s_algorithm_for_reducible_primes

[adeines]

Commit: bfe5ca4

[adeines]

comment:2

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.

Things left to do or fix:

• add documentation
• only works if the curve has integral discriminant
• incorporate into isogeny finding for EC's over number fields
• more examples, especially over larger fields
• timings against other methods
• probably more . . .

[adeines]

Changed keywords from none to isogenies

[JohnCremona]

comment:5

Thanks for the work so far. I'm working on this again now and will go through your to-do list.

[JohnCremona]

comment:6

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.

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.

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.

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.