Opened 6 years ago
Closed 6 years ago
#21776 closed defect (fixed)
Galois representations over number fields speedup
Reported by:  John Cremona  Owned by:  

Priority:  major  Milestone:  sage7.5 
Component:  elliptic curves  Keywords:  Galois representations 
Cc:  Merged in:  
Authors:  John Cremona  Reviewers:  Travis Scrimshaw, Frédéric Chapoton 
Report Upstream:  N/A  Work issues:  
Branch:  7ca67b0 (Commits, GitHub, GitLab)  Commit:  7ca67b08b99e9a538633bc2df9a388755b6e74a4 
Dependencies:  Stopgaps: 
Description
The code for computing Galois representations of elliptic curves over number fields (which is used in isogeny computation) uses the default iterator over primes of degree 1 in the number field. Two problems: first, the method K.primes_of_degree_one_iter() only gives primes up to some norm bound, and that is not always large enough if left at the default. Second, where the function is used only principal primes are wanted but the iterator starts at 2 wheras there are no principal primes of norm less than discriminant/4!
I put in a custom iterator which helps a lot.
I will upload a patch when I have recovered an example which fails badly.
Change History (18)
comment:1 Changed 6 years ago by
Branch:  → u/cremona/21776 

Commit:  → aa7c95398fb2bb476a29c484f40a66ddf8dbf6c1 
Status:  new → needs_review 
comment:2 Changed 6 years ago by
Two small things:
 for l in D: + for l in D.iterkeys():
This change is unnecessary as the iteration over a dictionary is the keys (and iterkeys
is going away in Python3).
Also, xrange
is going away in Python3, so you should revert that change because the from six.moves import range
already makes range
an iterator, not a list.
comment:4 Changed 6 years ago by
Commit:  aa7c95398fb2bb476a29c484f40a66ddf8dbf6c1 → 41c708dfd8b4246c4412fbb6fa0686101604f2d2 

Branch pushed to git repo; I updated commit sha1. New commits:
41c708d  #21776: minor changes after first review

comment:5 Changed 6 years ago by
You should add documentation to the new "deg_one_prime_iter" function.
comment:7 Changed 6 years ago by
Commit:  41c708dfd8b4246c4412fbb6fa0686101604f2d2 → f203c24d616692ae8b2d63a3b29c4450baee1c0e 

comment:9 Changed 6 years ago by
Branch:  u/cremona/21776 → u/tscrim/21776 

Commit:  f203c24d616692ae8b2d63a3b29c4450baee1c0e → 39d9afb0bf538473e9c8d2a2e84603a6c41111d5 
Reviewers:  → Travis Scrimshaw, Frédéric Chapoton 
Looking at the primes
documentation, it says you can pass oo
as the second argument. So I removed the maxnorm
argument. I also did a few cosmetic changes. If you agree with my changes, then you can set a positive review.
New commits:
cfd653a  Merge branch 'u/cremona/21776' of git://trac.sagemath.org/sage into u/tscrim/21776

39d9afb  Removing the maxnorm and some cosmetics.

comment:10 followup: 12 Changed 6 years ago by
it.next() is not python3 compatible, use next(it) instead
comment:11 Changed 6 years ago by
Commit:  39d9afb0bf538473e9c8d2a2e84603a6c41111d5 → 0881746045b963657e6aac2a9aeb0c50aec2656b 

Branch pushed to git repo; I updated commit sha1. New commits:
0881746  Fixing it.next() to next(it).

comment:12 Changed 6 years ago by
Replying to chapoton:
it.next() is not python3 compatible, use next(it) instead
I did not know that  and in fact one thing I had done was to make the reverse change, thinking it was somehow more efficient. Thanks.
I am happy with the changes since my commits. What next?
comment:14 Changed 6 years ago by
OK, I'll fix that and put it back into my branch... (building docs takes such a long time it discourages proper testing!)
comment:15 Changed 6 years ago by
Commit:  0881746045b963657e6aac2a9aeb0c50aec2656b → 7ca67b08b99e9a538633bc2df9a388755b6e74a4 

Branch pushed to git repo; I updated commit sha1. New commits:
7ca67b0  Add the forgotten colon.

comment:16 Changed 6 years ago by
I just took care of it. (Partial doc builds can help for this kind of testing.) Feel free to put your branch if you make other changes.
comment:18 Changed 6 years ago by
Branch:  u/tscrim/21776 → 7ca67b08b99e9a538633bc2df9a388755b6e74a4 

Resolution:  → fixed 
Status:  positive_review → closed 
New commits:
#21776: speed up elliptic curve galois reps & isogenies