Elliptic curve isogenies over number fields I: speed up Larsen's algorithm for reducible primes

[JohnCremona]

This ticket is part 1 of 2. When running Larsen's algorithm over fields of degree 5 or more, E.reducible_primes() takes for ever for at least two reasons: (1) computation of the Galois closure; (2) arithmetic over that closure. I have an improvement which avoids working in the closure at all, using instead some polynomial utilities based on resultants.

On this ticket I will add the polynomial utilities and the improved version of the function _supersingular_reducible_primes.

On a second ticket I will add an implementation of a different method, due to Bilieray, for finding the reducible primes.

CC: @adeines @jpflori

Component: elliptic curves

Author: John Cremona

Branch/Commit: e32de47

Reviewer: Frédéric Chapoton

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

[JohnCremona]

comment:3

I have a branch now testing which should be ready for review soon. It is much faster over degree 5 and 6 fields with large Galois closure (e.g. for an S5 quintic it goes from taking hours to just fast) but is possibly slower when the Galois group is small (e.g. when the base field is already Galois). In addition, there is a step in the original implementation which I do not understand mathematically -- in the unusual case where anauxiliary imaginary quadratic field comes into play, I can see that it is a subfield of Kgal (the Galois closure) but not of K itself. There is only one doctest for this case, when K=Kgal (=imagainary quadratic) anyway. If there is ever an example where the quadratic is not a subfield of K, the code will break -- this is also true of the current code though.

[JohnCremona]

Branch: u/cremona/22343

[JohnCremona]

New commits:

7fbcc38	added a few new polynomial utility methods including symmetric power
bf3ac90	renamed power_roots() method to adams_operator()
904e6ff	#22343 changes to _semistable_reducible_primes() for elliptic curves over number fields

[JohnCremona]

Commit: 904e6ff

[JohnCremona]

comment:5

The first two commits add some methods for univariate polynomials, not specific to elliptic curves. The third rewrites the code in the _semistable_reducible_primes() function. My intention is to leave the algorithm essentially unchanged while making it possible to run over fields where the Galois closure is large -- in the new version it is not necessary to compute the Galois closure at all.

If it would be helpful, I could provide a longer explanation of what I changed and why this is equivalent to the old version, but the fact that no doctests needed changing is a good sign! I could add an example over a degree 5 field with Galois group S5, which is now possible (and quite fast).

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

533dd93

#22343 new doctest added

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 904e6ff to 533dd93

[JohnCremona]

comment:7

Replying to @sagetrac-git:

Branch pushed to git repo; I updated commit sha1. New commits:

533dd93

#22343 new doctest added

The new doctest runs in <1s (using %timeit) while using Sage 7.5 it is still running after [90 minutes] 54 hours...

[fchapoton]

comment:8

+[dochtml] [polynomia] docstring of sage.rings.polynomial.polynomial_element.Polynomial.adams_operator:1: WARNING: Inline interpreted text or phrase reference start-string without end-string.
+[dochtml] [polynomia] docstring of sage.rings.polynomial.polynomial_element.Polynomial.compose_power:14: WARNING: Inline interpreted text or phrase reference start-string without end-string.
+[dochtml] [polynomia] docstring of sage.rings.polynomial.polynomial_element.Polynomial.symmetric_power:1: WARNING: Inline interpreted text or phrase reference start-string without end-string.
+[dochtml] Error building the documentation.

There is a + TESTS: missing a double colon.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 533dd93 to 1817af4

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

1817af4

#22343 fix syntax errors in docstrings

[JohnCremona]

comment:10

Thanks, I think that is fixed now. I wish testing docstring syntax were easier.

[fchapoton]

Reviewer: Frédéric Chapoton

[fchapoton]

comment:11

I have made a cosmetic cleanup of your code and doc. In particular, note that

• one should rather avoid using $
• TESTS:: are not displayed in the doc

If you agree with my changes, you can set to positive review

---

New commits:

96b9126	Merge branch 'u/cremona/22343' in 8.0.b1
e32de47	trac 22343 code and doc cosmetic cleanup

[fchapoton]

Changed branch from u/cremona/22343 to public/22343

[fchapoton]

Changed commit from 1817af4 to e32de47

[JohnCremona]

comment:13

I do agree -- thanks.

[vbraun]

Changed branch from public/22343 to e32de47