Computing images of Galois representations attached to elliptic curves

Andrew V. Sutherland

Published 2015-04-28Version 1

Let E be an elliptic curve without complex multiplication defined over a number field K. Let G_E(\ell) denote the image of the Galois representation induced by the action of the absolute Galois group of K on the \ell-torsion subgroup of E. We present two probabilistic algorithm to simultaneously determine G_E(\ell) up to local conjugacy for all primes \ell by sampling images of Frobenius elements. In each case we determine G_E(\ell) up to one of at most two isomorphic conjugacy classes of subgroups of GL_2(\ell), each of which occurs for an elliptic curve that is isogenous to E and has the same semisimplification. Under the generalized Riemann hypothesis, both algorithms run in time polynomial in the bit-size n of an integral Weierstrass equation for E. Our first algorithm is a Las Vegas algorithm with expected running time polynomial in n, while the second is a Monte Carlo algorithm with one-sided error whose running time is quasi-linear in n. We have applied our Monte Carlo algorithm to all the non-CM elliptic curves in Cremona's tables and the Stein-Watkins database, some 140 million curves with conductors ranging up to 10^{12}, thereby obtaining a conjecturally complete list of 63 exceptional Galois images G_E(\ell) that arise for non-CM elliptic curves E/Q. We also give several examples of exceptional Galois images for non-CM elliptic curves defined over various quadratic fields K that do not occur for non-CM elliptic curves over Q.