Galois representations over number fields speedup

[JohnCremona]

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.

Component: elliptic curves

Keywords: Galois representations

Author: John Cremona

Branch/Commit: 7ca67b0

Reviewer: Travis Scrimshaw, Frédéric Chapoton

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

[JohnCremona]

Branch: u/cremona/21776

[JohnCremona]

Commit: aa7c953

[JohnCremona]

New commits:

aa7c953

#21776: speed up elliptic curve galois reps & isogenies

[tscrim]

comment:2

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.

[JohnCremona]

comment:3

Thanks, will do. I have no idea why I put in the iterkeys().

[sagetrac-git]

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

41c708d

#21776: minor changes after first review

[sagetrac-git]

Changed commit from aa7c953 to 41c708d

[fchapoton]

comment:5

You should add documentation to the new "deg_one_prime_iter" function.

[JohnCremona]

comment:6

OK, I am working on this.

[sagetrac-git]

Changed commit from 41c708d to f203c24

[sagetrac-git]

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

fa2596c	#21776: add docstring to new function
f203c24	#21776: add doctest too

[JohnCremona]

comment:8

Docstring and test added.

[tscrim]

Changed branch from u/cremona/21776 to u/tscrim/21776

[tscrim]

Changed commit from f203c24 to 39d9afb

[tscrim]

comment:9

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.

[tscrim]

Reviewer: Travis Scrimshaw, Frédéric Chapoton

[fchapoton]

comment:10

it.next() is not python3 compatible, use next(it) instead

[sagetrac-git]

Changed commit from 39d9afb to 0881746

[sagetrac-git]

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

0881746

Fixing it.next() to next(it).

[JohnCremona]

comment:12

Replying to @fchapoton:

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?

[fchapoton]

comment:13

doc does not build, EXAMPLES: should be EXAMPLES::

[JohnCremona]

comment:14

OK, I'll fix that and put it back into my branch... (building docs takes such a long time it discourages proper testing!)

[sagetrac-git]

Changed commit from 0881746 to 7ca67b0

[sagetrac-git]

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

7ca67b0

Add the forgotten colon.

[tscrim]

comment:16

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.

[fchapoton]

comment:17

ok, looks good enough.

[vbraun]

Changed branch from u/tscrim/21776 to 7ca67b0