Opened 5 years ago
Closed 5 years ago
#22343 closed enhancement (fixed)
Elliptic curve isogenies over number fields I: speed up Larsen's algorithm for reducible primes
Reported by:  cremona  Owned by:  

Priority:  minor  Milestone:  sage8.0 
Component:  elliptic curves  Keywords:  
Cc:  aly.deines, jpflori  Merged in:  
Authors:  John Cremona  Reviewers:  Frédéric Chapoton 
Report Upstream:  N/A  Work issues:  
Branch:  e32de47 (Commits, GitHub, GitLab)  Commit:  e32de4750929ff2829af980d8b25fe6c88972070 
Dependencies:  Stopgaps: 
Description
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.
Change History (14)
comment:1 Changed 5 years ago by
 Summary changed from Elliptic curve isogenies over number fields I: speed up Larsen's algorithm for redicible primes to Elliptic curve isogenies over number fields I: speed up Larsen's algorithm for reducible primes
comment:2 Changed 5 years ago by
 Cc jpflori added
comment:3 Changed 5 years ago by
comment:4 Changed 5 years ago by
 Branch set to u/cremona/22343
 Commit set to 904e6ff46367761f4a968c3ccd1f301a2ed3a6ae
 Priority changed from major to minor
 Status changed from new to needs_review
comment:5 Changed 5 years ago by
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).
comment:6 followup: ↓ 7 Changed 5 years ago by
 Commit changed from 904e6ff46367761f4a968c3ccd1f301a2ed3a6ae to 533dd93f556d70b92118c1bc04aa2e48d7922805
Branch pushed to git repo; I updated commit sha1. New commits:
533dd93  #22343 new doctest added

comment:7 in reply to: ↑ 6 Changed 5 years ago by
comment:8 Changed 5 years ago by
+[dochtml] [polynomia] docstring of sage.rings.polynomial.polynomial_element.Polynomial.adams_operator:1: WARNING: Inline interpreted text or phrase reference startstring without endstring. +[dochtml] [polynomia] docstring of sage.rings.polynomial.polynomial_element.Polynomial.compose_power:14: WARNING: Inline interpreted text or phrase reference startstring without endstring. +[dochtml] [polynomia] docstring of sage.rings.polynomial.polynomial_element.Polynomial.symmetric_power:1: WARNING: Inline interpreted text or phrase reference startstring without endstring. +[dochtml] Error building the documentation.
There is a + TESTS:
missing a double colon.
comment:9 Changed 5 years ago by
 Commit changed from 533dd93f556d70b92118c1bc04aa2e48d7922805 to 1817af4493beeb4e7af010950dd29d9f1cce7b36
Branch pushed to git repo; I updated commit sha1. New commits:
1817af4  #22343 fix syntax errors in docstrings

comment:10 Changed 5 years ago by
Thanks, I think that is fixed now. I wish testing docstring syntax were easier.
comment:11 Changed 5 years ago by
 Branch changed from u/cremona/22343 to public/22343
 Commit changed from 1817af4493beeb4e7af010950dd29d9f1cce7b36 to e32de4750929ff2829af980d8b25fe6c88972070
 Reviewers set to Frédéric Chapoton
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

comment:12 Changed 5 years ago by
 Milestone changed from sage7.6 to sage8.0
comment:13 Changed 5 years ago by
 Status changed from needs_review to positive_review
I do agree  thanks.
comment:14 Changed 5 years ago by
 Branch changed from public/22343 to e32de4750929ff2829af980d8b25fe6c88972070
 Resolution set to fixed
 Status changed from positive_review to closed
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.