Razvan Barbulescu

Sudarshan Shinde

A CLASSIFICATION OF ECM-FRIENDLY FAMILIES USING MODULAR CURVES

In this work, we establish a link between the classification of ECM-friendly curves and Mazur's program B, which consists in parameterizing all the families of elliptic curves with exceptional Galois image. Building upon two recent works which treated the case of congruence subgroups of prime-power level which occur for infinitely many j-invariants, we prove that there are exactly 1525 families of rational elliptic curves with distinct Galois images which are cartesian products of subgroups of prime-power level. This makes a complete list of rational families of ECM-friendly elliptic curves, out of which less than 25 were known in the literature. We furthermore refine a heuristic of Montgomery to compare these families and conclude that the best 4 families which can be put in a = -1 twisted Edwards' form are new.

Introduction

Integer factorization is an important problem in algorithmic number theory and cryptology. The factoring algorithms split into two classes: on the one hand those whose costs depend only on the size of the integer N to factor, like the quadratic sieve and the number field sieve (NFS) [START_REF] John | The lattice sieve[END_REF]LLJMP93] and on the other hand those whose costs depend on the size of the factors we are looking for, up to a polynomial factor in the bit size of N, as it is the case for the trial division and the elliptic curve method of factorization (ECM) [LJ87]. At the first sight, only the first class is relevant in cryptology because the numbers to factor in the RSA system are of the form N = pq where p and q are two primes of equal bit size. However, ECM is used in NFS and, in computations of cryptologic relevance, ECM takes an important part of the cost of NFS. Another important problem in cryptology is that of computing discrete logarithms, i.e. in a cyclic group G with generator g, given g x , find x. For this problem as well, the best known algorithm is a variant of NFS.

In brief, ECM works as follows: given an integer N with an unknown prime factor p, one first chooses a rational elliptic curve E and a point P ∈ E(Q) with denominators relatively prime to N. One then computes P M := [M] • P, while keeping the coordinates modulo N. If # E(F p ) divides M, then P M is the neutral element of E(F p ) or it is congruent to (0 : 0 : 0) mod p. The z-coordinate of P M in the Weierstrass equation being divisible by p, one finds a multiple of p by computing gcd(z, N).

The choice of M varies from one implementation to another, but as a first approximation, we take M = B! log 2 B for some integer B. The algorithm succeeds if # E(F p ) is B-smooth i.e. all its prime factors are less than B. By Hasse's theorem, we have # E(F p ) ≈ p. It is then natural to compare the chances of # E(F p ) being B-smooth with the chances of an integer of the same size as p being B-smooth.

In the version of ECM proposed by Lenstra [LJ87], one selects uniformly random integers x, y and a in [0, p -1] and sets E : y 2 = x 3 + ax + b such that (x, y) ∈ E(F p ). Lenstra [LJ87, Prop 2.7] proved that the proportion of elliptic curves selected in this manner for which # E(F p ) is B-smooth equals, up to a factor 1/O(log p), the proportion of B-smooth integers in [p -√ p, p + √ p].

In cryptologic applications of ECM, one uses elliptic curves from parameterized sets. We shall refer to these parameterized sets as families of elliptic curves. Soon after ECM was published, Montgomery [Mon87] introduced a parameterization, By 2 = x 3 + Ax 2 + x, which speeds up the point addition and doubling. Montgomery also suggested to use elliptic curves with 12 and 16 rational torsion points. Indeed, if an elliptic curve E has good reduction modulo p for a prime p coprime to cardinality of the torsion subgroup E(Q) tors , then E(Q) tors embeds in E(F p ). So, the torsion order # E(Q) tors divides # E(F p ) for p > 7. Experimentally, this increases the proportion of primes p where # E(F p ) is B-smooth.

Mazur's theorem states that there are 15 possible torsion structures over Q and the families corresponding to them have been considered for ECM [START_REF] Oliver | Finding suitable curves for the elliptic curve method of factorization[END_REF][START_REF] Bernstein | Ecm using edwards curves[END_REF][START_REF] Daniel J Bernstein | Starfish on strike[END_REF]. However, the torsion subgroup is not the complete story because two families can have the same torsion subgroup yet different proportions of primes modulo which the cardinality is B-smooth. Indeed, the Suyama family [Mon87, p. 262] has 6 rational torsion points but has better performance in ECM than a generic curve with the same torsion. Also note that, if E is a Suyama curve, then 12 divides # E(F p ) for all primes p of good reduction, whereas only the divisibility by 6 is guaranteed for an arbitrary curve with the same torsion.

Brier and Clavier [START_REF] Brier | New families of ecm curves for cunningham numbers[END_REF] found families defined over Q with large torsion over Q(ζ n ) where ζ n is a primitive n-th root of unity and n = 3, 4, 5. Heer, McGuire and Robinson [START_REF] Heer | JKL-ECM: an implementation of ECM using hessian curves[END_REF] presented more rational families with large torsion over Q(ζ 3 ) and noted experimentally that they are better in ECM than elliptic curves having the same torsion over Q.

Barbulescu, Bos, Bouvier, Kleinjung and Montgomery [BBB + 13] noted that the torsion subgroup over number fields do not explain the behaviour of curves in ECM. Indeed, they proposed subfamilies of the Suyama family which have the same torsion as the Suyama family over any fixed number field and yet they have better smoothness properties. Similarly, they found families of elliptic curves with torsion subgroup Z/2Z × Z/4Z having better properties than the generic curves having the same torsion. They proved that this difference is due to the Galois group of m-torsion field, Q(E[m]), which is generated by the coordinates of the m-torsion points of E over Q.

We use the notations of Serre [START_REF] Serre | Propriétés galoisiennes des points d'ordre fini des courbes elliptiques[END_REF]. Let P 1 and P 2 be such that E(Q)[m] = Z mZ P 1 + Z mZ P 2 . We call the mod m Galois representation of Gal(Q/Q) of E the map:

ρ E,m : Gal(Q/Q) → Aut(E[m]) ∼ = GL 2 (Z/mZ) ρ → ( a c b d ) ,
where a, b, c, d ∈ Z/mZ such that σ(P 1 ) = aP 1 + bP 2 and σ(P 2 ) = cP 1 + dP 2 . We refer to Imρ E,m as mod m Galois image and the integer m as the level of Imρ E,m . Furthermore, if ρ E,m is non-surjective, we say mod m Galois image is exceptional.

In a similar manner, for a prime , we define ρ E,

∞ : Gal(Q/Q) → Aut(E[ ∞ ]) ∼ = GL 2 (Z ) and ρ E : Gal(Q/Q) → Aut(E torsion ) ∼ = GL 2 ( Ẑ).
Serre's open image theorem [START_REF] Serre | Propriétés galoisiennes des points d'ordre fini des courbes elliptiques[END_REF] states that, for an elliptic curve E without complex multiplication, ρ E, is surjective for all but finitely many primes and there exists an integer m such that [GL 2 ( Ẑ) :

Imρ E ] = [GL 2 (Z/mZ) : Imρ E,m ].
Given a subgroup H of GL 2 ( Ẑ), Mazur's program B [SZ06, page 109] consists in classifying all elliptic curves E such that Imρ E ⊂ H, up to conjugacy. Shimura's theory [Shi71] states that the set of these elliptic curves can be parameterized by the modular curve X H . Sutherland and Zwyina [SZ17] computed the equations of modular curves X H for H ⊂ GL 2 (Z/mZ) when -I ∈ H and m is a prime-power. Rouse and Zureick-Brown [RZB15] obtained the complete classification when m is a power of 2.

In this work, we are interested in methods which, given an integer m, find all the possible images of ρ E,m and furthermore obtain families of curves E for these images. We present two methods. The first one in Section 2 is based on the computations of all the subfields of a function field. And, the second one in Section 3 is based on the theory of modular curves. In the same section, we recall the recent results on Mazur's program B and complete the work of Sutherland and Zywina by giving parameterizations of the families associated to subgroups of prime-power level which do not contain -I.

Then, in Section 4, we consider the subgroups H of GL 2 (Z/mZ) for any interger m which are isomorphic to the cartesian product of their projections modulo prime-power divisors of m (see Def. 4.1). We solve Mazur's program B for cartesian prodcuts which occur as Galois images for infinitely many elliptic curves with distinct j-invariants: Theorem 4.1 There are exactly 1525 subgroups of GL 2 ( Z) which are cartesian and occur as Galois images for infinitely many j-invariants.

Surprisingly, we obtain that the ECM-friendly families from the literature are in this list (see Section 4.3). In Section 5, we give a new point of view on a heuristic of Montgomery to rank ECM-friendly curves and conclude that the best 4 families which can be put in a = -1 twisted Edwards' form are new.

The subfields approach

Given an integer m, we want to parameterize, for each subgroup H of GL 2 (Z/mZ), the set of rational pairs (a, b) such that, for E : y 2 = x 3 + ax + b, we have Imρ E,m ⊂ H, up to conjugacy in GL 2 (Z/mZ). More generally, given a rational parameterization a = a(e) and b = b(e) of Galois group G, we want to further parameterize e = e(t) such that Imρ E,m ⊂ H for a subgroup of G. In this section, we give a solution based on the computation of the subfields of a function field. It is simple and feasible (For example, level 8 of Montgomery curves).

Let L be the m-torsion field of E. One computes a defining polynomial of L over K = Q(a, b) (resp. Q(e)) [BBB + 13, Section 2.2]. One then computes G = Gal(L/K). For each subgroup H of G, one computes a defining polynomial f H of the fixed subfield L H .

L H = K[X]/f H K L G H The pairs (a, b) ∈ K 2 for which G ⊂ H are such that ∃ t ∈ K, f H (a, b, t) = 0. (resp. the parameters e ∈ K for which G ⊂ H are such that ∃ t ∈ K, f H (a(e), b(e), t) = 0.)
Let C be a plane curve and K a number field and let g be its genus. If g ≥ 2, Faltings' theorem implies that there is no parameterization of the K-rational points of C, that is to say, the set of points is finite. If g = 1, we use an algorithm from [vH95] (implemented in u MAPLE's "algcurves" package) to put it in Weierstrass form. Note that if this algorithm fails to find a rational point on C, the user must provide such a point; we succeed in doing so in all the computations in this work.

Cremona's algorithm [START_REF] Je Cremona | Classical invariants and 2-descent on elliptic curves[END_REF] (implemented in SAGE) enables one to compute the rank of an elliptic curves and generators. Note that the search bounds of the algorithm can make the computations impractical; in this work, we succeed in either certifying that the rank is 0 or in finding generators of the Mordell-Weil group.

If g = 0, we use an algorithm from [vH97] (implemented in using MAPLE's "algcurves" package) to parameterize it. Note that this algorithm too is not proven to find a rational point but in all the examples treated in this work, the algorithm succeeds.

Let us illustrate this method with the following example.

2.1.

K := Q(ζ 8 ) = Q(e)( √ -1, √ 2
). Using MAPLE's implementation of an algorithm in [VHKN13], we compute the quadratic subfields between K and L as shown in the following diagram.

L K 1 K 2 K 3 K 4 K 5 K 6 K 7 K( √ e) K( √ e 2 -1) K( √ e 2 + 1) K( √ e 3 -e) K( √ e 3 + e) K( √ e 4 -1) K( √ e 5 -e) K Figure 1. Subfields of L = Q(e)(E e [8]) over K = Q(ζ 8 )(e)
where E e : y 2 -x 2 = 1 -e 4 x 2 y 2 . The fields K 1 , . . . K 7 are the compositums of pairs of quadratic fields.

We then consider the curves C that define these quadratic subfields. For each of them, we note the genus of the associated plane curve. One of the curves has genus 2 so there are only finitely many points. For the curves with genus 1, we compute their Weierstrass forms using MAPLE's "algcurves" package based on [START_REF] Van Hoeij | An algorithm for computing an integral basis in an algebraic function field[END_REF]. However, using MAGMA, we see that all the genus 1 curves have rank 0 so the corresponding families are finite. We summarize it in the table below.

defining polynomial of C genus #C(Q(ζ 8 )) is infinite ? x 2 -e 0 yes x 2 -(e 2 + 1) 0 yes x 2 -(e 2 -1) 0 yes x 2 -(e 4 -1) 1 no x 2 -(e 3 + e) 1 no x 2 -(e 3 -e) 1 no x 2 -(e 5 -e) 2 no
We are thus left with the three curves of genus 0. For each curve, we start by finding a parameterization, then by computing the subfamilies.

(1) We parameterize the curve of equation x 2 -e = 0 by e(t) = t 2 . The fields of above Q( √ e) are defined by the relative polynomials x 2 -(t 4 + 1), x 2 -(t 4 -1) and x 2 -(t 8 -1). The first two define elliptic curves with rank 0 and the last one has genus 3.

(2) We parameterize the curve of equation x 2 -(e 2 + 1) = 0 by e(t) = t 2 -1 2t . The fields of above Q( √ e 2 + 1) are defined by the relative polynomials x 2 -t(t 2 + 1), x 2 -(t 4 + 6t 2 + 1) and x 2 -t(t 2 + 1)(t 4 + 6t 2 + 1). Once again, the first two define elliptic curves of rank 0 and the last one has genus 3.

(3) We parameterize the curve of equation x 2 -(e 2 -1) = 0 by e(t) = t 2 +1 2t . The fields of above Q( √ e 2 -1) are defined by the relative polynomials x 2 -t(t 2 -1), x 2 -(t 4 -6t 2 + 1) and x 2 -t(t 2 -1)(t 4 -6t 2 + 1). Here too, the first two define elliptic curves of rank 0 and the last one has genus 3.

We deduce that the only fields between K and L corresponding to families are K( √ e), K( √ e 2 + 1) and K( √ e 2 -1). Thus if a field F between Q(e) and L correspond to a rational family then the field F, K also correspond to a rational family. So, in order to compute the families defined over Q(e), we consider the subfields of K( √ e), K( √ e 2 + 1) and K( √ e 2 -1). For the first one, we consider the subfield between Q(e) and K( √ e)), as represented in the following subfields diagram.

K( √ e) Q(e)( √ e, √ 2) Q(e)( √ e, √ -2) Q(e)( √ -1, √ 2) Q(e)( √ -1, √ 2e) Q(e)( √ -e, √ 2) Q(e)( √ -2, √ -e) Q(e)( √ -1, √ e) Q(e)( √ -e) Q(e)( √ 2e) Q(e)( √ -2e) Q(e)( √ -2) Q(e)( √ e) Q(e)( √ -1) Q(e)( √ 2) Q(e)
Three of the defining polynomials of the quadratic subfields in the diagram correspond to curves with no rational points and the others are parameterized by e = t 2 , e = -t 2 , e = 2t 2 and e = -2t 2 . As the degree of e in E -1,-e 4 is even, there is only one family for e = t 2 and e = -t 2 . Thus in this case, we have 2 distinct subfamilies. We need not consider the fields of degree 4 because they contain at least one of √ -1, √ -2 and √ 2 which lead to polynomials systems without rational solutions.

Similarly, for the fields K( √ e 2 + 1) and K( √ e 2 -1), each gives 2 subfamilies given by e 2 +1 = t 2 , e 2 + 1 = 2t 2 and e 2 -1 = t 2 , e 2 -1 = 2t 2 . We have proven the following result.

Proposition 2.1. There are exactly 6 rational subfamilies of the family E -1,-e 4 .

Out of these families, four were presented in [BBB + 13] and the two described by 2(e 2 ± 1) = t 2 are new.

The Modular curves approach

An alternative approach to the one with subfields is due to the following theorem from Shimura's theory.

Theorem 3.1 ([Shi71]

). Let E be an elliptic curve such that j(E) ∈ {0, 1728}, N a positive integer and H a subgroup of GL 2 (Z/ N Z) such that -1 0 0 -1 ∈ H and det(H) = (Z/ N Z) * . Then there exists a polynomial X H (j, t)

such that Gal(Q(E[N])/Q) is conjugated to a subgroup of H if and only if ∃ t 0 ∈ Q such that X H (j(E), t 0 ) = 0.
In this section, the matrix -1 0 0 -1 plays an important role and we denote it by -I. For a modern description of the theory, we refer to [Zyw15, Sec 3]. The main ingredient of the computations is the field of modular functions of level N which we will discuss briefly.

Let H be the upper half complex plane i.e. the set of complex numbers with positive imaginary parts. Let F N be the set of meromorphic functions f on H which are invariant by linear fractional action of the principal congruence subgroup of level N such that the coefficients of q-expansion of f are in Q(ζ N ). Let j be the modular j-invariant. Then F N is a Galois extension of Q(j) with Galois group isomorphic to GL 2 (Z/ N Z)/{±1} [Shi71, Ch. 6, Sec. B], [Zyw15, Prop. 3.1]. Let F H N be the fixed field under the action of H ⊂ GL 2 (Z/ N Z)/{±1}. Finally, the modular curve of H is the plane curve associated with the defining polynomial of the function field extension F H N . The computation of X H is done in two steps:

(1) We compute a system of modular functions which generate the field F N ; this allows us to find a primitive element h of the extension

F H N /Q(ζ N , j).
(it is called hauptmodul when H has genus 0).

(2) We compute the minimal polynomial of h which defines the curve X H .

We refer to [SZ17, Sec 2] for a complete description of the method for prime-power level. Rouse and Zureick-Brown [RZB15] computed all the subgroups H ⊂ GL 2 (Z 2 ) which can occur as mod 2 ∞ Galois image for at least one elliptic curve E /Q without complex multiplication. They proved that there are 1208 groups which can occur as Imρ E,2 ∞ . Out of them, 1200 groups occur for infinitely many elliptic curves with distinct j-invariants and 8 for finitely many j-invariants. For this, they first deal (in Sec. 4) with 727 subgroups such that -I ∈ H and prove that for 194 of them X H (Q) is infinite. Then, (in Sec. 5) they compute parameterizations for the 1006 subgroups H that do not contain -I.

Sutherland and Zywina [SZ17] computed the complete list of subgroups H ⊂ GL 2 (Z ), for all primes , such that -I ∈ H, which can occur as mod ∞ Galois images for infinitely many elliptic curves with distinct j-invariants. A list of parameterizations of the corresponding modular curves X H is given in the online complement of their article. For each subgroup H containing -I, they found the list of subgroups H , up to conjugacy, with surjective determinant such that -I ∈ H and H = -I, H . An argument that we will see below guarantees that, for each j-invariant whose curves have the Galois image contained in H, there exists exactly one elliptic curve (up to isomorphism over Q) whose Galois image is contained in H , up to conjugacy in H. Hence, without computing parameterizations of the elliptic curves whose Galois images do not contain -I, Sutherland and Zywina concluded that there are exactly 47 (resp. 23, 15, 2, 11) proper subgroups of GL 2 (Z ) for = 3 (resp. 5, 7, 11, 13) which can occur as Galois images for infinitely many elliptic curves with distinct j-invariants, and none for other odd primes. Remark: Theorem 3.3 of [SZ17] is applicable to all totally real number fields and generalizes to arbitrary number fields with a uniform bound on subgroups of genus 0 and 1. Thus, over any number field, one can make a similar classification.

3.1. Parameterizations when -I ∈ H. Two curves with the same j-invariant can have different Galois images. For example, an elliptic curve has a rational point P of order 3 if, and only if, its mod 3 Galois image is contained, up to conjugacy, in the group of matrices ( 1 * 0 * ). Indeed, one can choose a basis of E[m] containing P. Then, as P is rational, it is fixed by every automorphism. This ensures that the first column of the image of any automorphism is ( 1 0 ). Consider the set of pairs (a, b) ∈ Q 2 such that for E : y 2 = x 3 + ax + b, there exists a rational x 3 such that Ψ 3 (x 3 ) = 0, where Ψ 3 is the third division polynomial of E. Then, among the set of curves dy 2 = x 3 + ax + b, which have the same j-invariant, only those such that (x 3 3 + ax 3 + b)/d is a rational square, have a rational point of order 3. Hence, when -I ∈ H, we have to parameterize the pairs (a, b) rather than the j-invariants.

The following result gives a method to parameterize the set of curves whose Galois image is in a subgroup H which does not contain -I. We put H = -I, H . If X H is a conic with a rational point then we parameterize it as j = j(t) and apply the following lemma for K = Q(t), a = -3j(j -1728) ∈ K and b = -2j(j -1728) 2 ∈ K.

Lemma 3.1 ([RZB15] Sec. 5). Let K = Q(t) (resp. Q). Let H ⊂ GL 2 (Z/ N Z) such that -I ∈ H. Let H ⊂ H such that -I ∈ H and H = -I, H . Let E : y 2 = x 3 + ax + b be an elliptic curve over K such that Imρ E,N = H. Then there exists a unique squarefree d in Z[x] (resp. in Z) such that Gal(K(E d [N])/K) ⊂ H, where E d : dy 2 = x 3 + ax + b.
Furthermore, the value of d is in the finite set of squarefree elements of Z[t] (resp. Z) whose prime factors divide either the numerator or the denominator of N •(4a 3 + 27b 2 ).

In the light of the above lemma, we have a method, presented in [RZB15], which allows us to parameterize the curves corresponding to the subgroups of a group H containing -I whose modular curve is a conic. Once we parameterize the pairs (a = a(t), b = b(t)) such that y 2 = x 3 + ax + b has the Galois image in H, we proceed in two steps:

(1) We compute the list of prime factors p 1 , . . . , p k of N •(4a 3 +27b 2 ) and enumerate the products d = (-1) e0 k i=1 p ei i where e 0 , . . . , e k ∈ {0, 1}. Test if the field K(E[N]) contains a root of x 2 -d to obtain the list of its quadratic subfields.

(2) We make the list of subgroups H of GL 2 (Z/ N Z) such that H, -I = H and det H = (Z/ N Z) * and -I ∈ H. For each d(t) corresponding to quadratic subfields, we eliminate all but one subgroup H by giving numerical values to t and computing the Galois image of d(t)y 2 = x 3 + ax + b.

Example 3.1. Consider the case of H = ( 0 1 2 1 ), ( 1 2 0 2 ) ⊂ GL 2 (Z/3Z). According to [SZ17, Tab. 1], the set of rational triples (d, a, b) such that for E : dy 2 = x 3 + ax + b, Imρ E,3 contained in H are such that there exist rationals t and λ such that a = -3λ 2 (t + 27)(t + 3) and b = -2λ 3 (t 2 + 18t -27)(t + 27). The prime factors of 3(4a 3 + 27b 2 ) are 2, 3, t and (t + 27). Out of the 32 squarefree possible values of d, the only squares in

Q(t)(E[3]) are d = (t + 27), d = -3(t + 27) and d = -3.
There are three subgroups of H of index 2, out of which two have surjective determinant and do not contain -I : H 1 = ( 2 1 0 1 ), ( 0 2 1 2 ) and H 2 = ( 1 2 0 1 ), ( 0 2 1 2 ) . For numerical values t 0 of t (e.g. t 0 = 5), we compute the image of ρ E d 1 (t=t 0 ) ,3 and ρ E d 2 (t=t 0 ) ,3 using the scripts in the online complement [BS19] and obtain that d 1 = t + 27 corresponds H 1 and d 2 = -3(t + 27) to H 2 . Lemma 3.1 allows to conclude that, if the Galois image of E d1 is not contained in H 2 for one numerical value it is not contained for any t ∈ Q.

The work of Zywina [Zyw15] presents parameterizations corresponding to the groups which do not contain -I, but only for prime levels. We completed the classification for the remaining primepower cases k where is odd. It is summarized in the following theorem. Note that two subgroups of H, corresponding to different quadratic subfields, can be conjugated. Theorem 3.2. Let be an odd prime. The set of subgroups H ∈ GL 2 (Z ) which occur as Galois image for infinitely many j-invariants such that -I ∈ H are the ones given in Tables 2 and3, p.

23.

It is remarkable that, for any prime-power, the subgroups that do not contain -I which occur for infinitely many j-invariants have genus 0 and have rational parameterizations so one can apply Lemma 3.1 to K = Q(t). The method in this section applies to subgroups of arbitrary genera and levels using Lemma 3.1 for K = Q.

Finding families corresponding to subgroups of arbitrary level

A theorem of Cox and Parry [START_REF] David | Genera of congruence subgroups in q-quaternion algebras[END_REF] gives an explicit upper bound on the level of a subgroup in terms of its genus. This allowed Cummins and Pauli [CP03] to obtain the complete list of subgroups of PSL 2 (Z) of genus g ≤ 24.

For each such subgroup Γ, one can compute the list of subgroups Γ of GL 2 (Z) such that Γ ∩ PSL 2 (Z) = Γ. (see the proof of [Sut15, Prop. 3.6].) The method in [RZB15] permits to compute X H for any H. In this section, we propose an elementary method which is restricted to a certain class of subgroups which plays an important role in ECM (see Section 5.5).

Definition 4.1. Given a tuple of matrices (M

i ) i∈I of i∈I GL 2 (Z/ ki i Z), we define their cartesian product × i∈I M i as the matrix M of GL 2 (Z/ i∈I ki i Z) whose coefficients are the lifts of corre- sponding coefficients of M i . A subgroup H of GL 2 (Z/ i∈I ki i Z) is called cartesian if it is equal to × i∈I H i = {× i∈I M i |M i ∈ H i }, where H i is the projection of H modulo ki i . An example of a non-cartesian subgroup is {I, -I} ⊂ GL 2 (Z/15Z).
4.1. The case H 1 × H 2 . We consider three cases depending on whether -I belongs to both or either or neither of H 1 and H 2 .

The case where -I ∈ H 1 and -I ∈ H 2 . We start with the 17 maximal subgroups of 1A 0 -1a (See the scripts in [Sut15]): 16 groups of genus 0 and a group of genus 1, all of which contain -I. For any pair of maximal subgroups H 1 and H 2 of levels n 1 and m 2 , at least one of them has genus 0, say H 1 . Let j = j 1 (t 1 ) be a parameterization of X H1 . Then X H2 (j 1 (t 1 ), t 2 ) is a plane curve which characterizes elliptic curves with Galois image in H 1 × H 2 . To parameterize it, we proceed as in Section 2.

Example 4.1. Let H 1 = 2B 0 -2a and H 2 = 3A 0 -3a with j 1 (t) = (t-256) 3 t 2 and j 2 (t) = t 3 . We consider the curve X H1×H2 defined by the numerator of j 1 (x) -j 2 (y) which is -x 2 y 3 -x 3 + 768 x 2 -196608 x + 16777216. Using the "algcurves" package of MAPLE, we obtain that this curve is of genus 0 and it can be parameterized by choosing

x = t 3 , y = -t 3 -256 t 2
. Thus, if j-invariant of an elliptic curve E is of the form

-(t 3 -256) 3 t 6 , we have Imρ E,2 ⊂ H 1 and Imρ E,3 ⊂ H 2 .
For the 16 maximal subgroups, there are 112 possible cartesian products X H1×H2 such that H 1 and H 2 have relatively prime levels. Out of them, 20 have genus 0, 28 have genus 1. If for some H 1 and H 2 , we succeed in parameterizing the curve X H1×H2 , then we proceed in the similar manner, by taking the maximal subgroups of H 1 and H 2 . We obtain 163 products of genus 1 and 46 products of genus 0. Out of them, all the products of genus 0 have infinitely many rational points whereas 35 products of genus 1 have positive rank.

Given a product H 1 × H 2 of genus 1, let us assume that there are infinitely many elliptic curves with distinct j-invariants with Galois image contained in H 1 × H 2 . One can then ask whether the Galois image is actually equal to H 1 × H 2 for infinitely many of those curves. In the prime-power case, this is not necessarily true [RZB15, Remark 6.3]. We find 8 similar cases when the level is composite:

X

5 -3A 0 -3a, X 5 -3C 0 -3a, X 5 -3D 0 -3a, X 5 -3D 0 -3aT1 3A 0 -3a-5A 0 -5a, X 5 -9B 0 -9a, X 5 -9B 0 -9aT1, X 5 -9B 0 -9aT2.
This gives us 81 -8 = 73 distinct families of elliptic curves with distinct exceptional Galois images for two coprime prime-power levels such that their associated Galois images contain -I. The case where -I ∈ H 1 and -I ∈ H 2 . We first consider the group H 2 = H 2 , -I and compute X H1×H 2 . As above, we consider the genus of this curve and parameterize it to get a model E H1× H2 . By Lemma 3.1, there exists a quadratic twist of E H1×H 2 such that its mod m 2 Galois image is contained in H 2 . For 81 infinite families, we find 110 such families. Out of them, 85 are of genus 0 and 25 are of genus 1. The case where -I ∈ H 1 and -I ∈ H 2 . Let H 1 = H 1 , -I and y 2 = x 3 + a(t)x + b(t) be its model of j-invariant j 1 (t). Also let d 1 (t)y 2 = x 3 + a(t)x + b(t) be a model for H 1 . We define H 2 , d 2 (t) in a similar manner. For a given rational t 1 , Lemma 3.1 applied to a curve of j-inavariant j 1 (t 1 ) and K = Q states the existence of a unique elliptic curve up to isomorphism over Q whose Galois image is contained in H 1 . Equivalently, there exists a unique rational δ 1 up to a square such that the curve δ 1 y 2 = x 3 + a(j)x + b(j) has Galois image contained in H 1 . By the unicity of δ 1 , we have d 1 (t 1 ) = δ 1 up to a square. This shows that

X H1×H2 := {(t 1 , t 2 ) ∈ X H 1 ×H 2 | d 1 (t 1 ) d 2 (t 2 ) = }, corresponds to the pair H 1 × H 2 .
We thus consider the equation d 1 (t)/d 2 (t) = x 2 . If the plane curve defined by this equation has infinitely many points then we obtain a required model. Out of 60 pairs, there are 48 curves of genus 0, none of genus 1 and 12 curves of genus greater than 1. Let us illustrate it with an example.

Example 4.2. Let H

1 = 2A 0 -4a and H 2 = 7B 0 -7a. Let H 1 = 2 3 3 1 , 1 3 0 3 ⊂ H 1 ⊂ GL 2 (Z/4Z) and H 2 = 4 0 0 2 , 1 0 0 2 , 1 0 0 3 , 1 0 5 1 ⊂ H 2 ⊂ GL 2 (Z/7Z
). Let us note that neither H 1 nor H 2 contains -I . We first compute a model for E H1×H2 using the case where -I is in both the groups. As both of them contain -I, only j-invariant suffices to parameterize these curves. We get the following parameterization for the j-invariant.

j(t) = -1494501t 4 + 1198050t 3 + 359905t 2 + 48020t + 2401 3 30301t 4 + 24370t 3 + 7337t 2 + 980t + 49 (5t + 1) 2 t 14 .
We then fix a model E t with this j-invariant and then compute d 1 (t) and d 2 (t) by the method as explained in Example 3.1. We obtain d 1 (t) = 2t(5t + 1) and d 2 (t) = -1. Note that, these twists are not unique and they depend on the model E t . In order to compute a model for E H 1 ×H 2 , we cannot twist E t by d 1 (t) and d 2 (t), as the ratio of d 1 (t) and d 2 (t) is not a square. So, we consider the curve 2t(5t + 1) + x 2 defined by the equation

d 1 (t)/d 2 (t) = x 2
. This is a genus 0 curve which we parameterize by t(s) = -s 2 5 s 2 +50 . Finally, we specialize E t at t = -s 2 5 s 2 +50 and then twist it by -1 to obtain the model.

4.2.

The case H 1 ×H 2 ×H 3 . According to the results in the tables of Cummins and Pauli [CP03], we must have { 1 , 2 , 3 } = {2, 3, 5} or {2, 3, 7}. Since we consider first the case of maximal subgroups, we have to test only the case where the levels of H 1 , H 2 and H 3 are equal to 2, 3, 5 respectively or 2, 3, 7 respectively. In each case, we consider only those triples of groups H 1 , H 2 , H 3 where the genus of X Hi×Hj is either 0 or 1.

• The case of levels 2, 3 and 5: We start with triples H 1 , H 2 and H 3 of levels 2, 3 and 5 respectively such that each H i is maximal and all three curves defined by X Hi×Hj for all distinct i, j have infinitely many rational points. There are precisely 3 such triples: (2B 0 -2a, 3A 0 -3a, 5B 0 -5a), (2A 0 -8b, 3A 0 -3a, 5A 0 -5a) and (2A 0 -8b, 3A 0 -3a, 5C 0 -5a).

-The first two cases are simple to treat as there is at least a pair with genus 0, say X H1×H2 . In this case, let j = j 1,2 (t) be its parameterization and j 3 (s) be a parameterization of X H3 . We consider the curve defined by j 1,2 (t) -j 3 (s) = 0 and verify that it is of genus higher than 1. -In the case H 1 = 2A 0 -8b, H 2 = 3A 0 -3a, H 3 = 5C 0 -5a, all the curves X Hi×Hj , with 1 ≤ i = j ≤ 3 have genus 1 and rank 1. We consider the j-invariant associated with

X H1×H3 which is j 1,3 (x, y) = - 8000 (40 x 2 -10 xy+y 2 ) 3 (2 x+y)y 3 (20 x 2 -y 2 ) 5
, where (x, y) are points on the elliptic curve E : y 2 -5xy + 125 4 y = x 3 + 15 2 x 2 + 2625 16 x. On the other hand, X H2 is also of genus 0 and its j-invariant can be parameterized by j 3 (s) = s 3 . If there are infinitely many points on X H1×H2×H3 then j 1,3 (x, y) must be a cube infinitely many often. It is equivalent to saying 20 x 2 -y 2 (2 x + y) must be a cube infinitely often. We thus consider Res x t 3 -20 x 2 -y 2 (2 x + y), E . This curve is of genus 5. Thus in all these case, we have the resulting curves of higher genus. Thus there are no new families, and we do not need to consider non-maximal subgroups. • In the case of levels 2, 3 and 7, for each triple of maximal subgroups, at least two fa : There is no trimilies intersect in a finite number of points, hence the intersection of three families is always finite. The above computations and the scripts in the online complement [BS19] prove the following results.

Theorem 4.1. There are exactly 1525 subgroups of GL 2 ( Z) which are cartesian and occur as Galois images for infinitely many j-invariants.

The list of these models is in online complement [BS19].

4.3. Discussion on the families in the literature. To our knowledge, there are 23 families of elliptic curves which were reported to be used in ECM computations. In this section, we compare the list of families Theorem 4.1 with the previously known ones.

In short, the families used in ECM are motivated by the torsion properties and by the average number of full multiplications needed for doubling-and-adding on the elliptic curve. A recent study [START_REF] Bouvier | Faster cofactorization with ECM using mixed representations[END_REF] makes a state-of-the-art presentation of the implementation techniques and concludes that it is important that 1) the elliptic curve can be put on a particular form (Montgomery, Edwards, Hessian) and that 2) one can generate many curves of the family which have a rational point of coordinates of less than 32 bits. Of course any family can be put in short Weierstrass form. To have a better cost, one uses either the twisted Edwards form or the twisted Hessian form which is not possible for all elliptic curves. The twisted Edwards' curves are birationally equivalent to Montgomery curves [BBJ + 08, Theorem 3.2] and have two subfamilies which have an even better cost: the case a = -, which is abusively also called twisted Edwards and has the best arithmetic cost, and the case a = which is simply called Edwards form. A direct computation (Appendix B) shows that an elliptic curve can be put in twisted Edwards/ Montgomery form if and only if it belongs to the family X 13 using [RZB15] notations. The corresponding group contains -I and has index 2 subgroups not containing -I of the same level which also correspond to infinite families: we identify these families with the cases a = and a = -(see row 2 and row 3 of Table 4).

Bernstein et al. [START_REF] Daniel J Bernstein | Twisted Hessian curves[END_REF] proved that an elliptic curve can be put in twisted Hessian form if and only if it is isogenous to a curve having a rational point of order 3. Hence, in order to parameterize twisted Hessian curves, we parameterize curves with mod 3 Galois image contained in the group of upper triangular matrices (see row 4 in Table 4).

We distinguish the case of families having a point of infinite order, i.e. given a family of rational parameterization E : y 2 = x 3 + a(t)x + b(t) we call subfamily a subset of the family where t is parameterized by a plane curve of genus 0 or 1 so that there exists a point of E which does not have order ≤ 16 except for a finite explicit set. For example, Montgomery [Mon87] attributes to Suyama a family as well as a subfamily having a point of infinite order, the subfamily being much more known than the family. (see row 5 and row 18 in Table 4). more Also, Gélin et al. [START_REF] Gélin | Parametrizations for families of ecm-friendly curves[END_REF] proposed subfamilies with points of infinite order on the families of [BBB + 13]. We do not discuss further the case of subfamilies with points of infinite order because they are not known to modify the behaviour of ECM and because they produce curves of large coefficients. Instead, several authors make lists of elliptic curves from families which have small coefficients and compute directly a rational point [START_REF] Bouvier | Faster cofactorization with ECM using mixed representations[END_REF][START_REF] Heer | JKL-ECM: an implementation of ECM using hessian curves[END_REF][START_REF] Daniel J Bernstein | Starfish on strike[END_REF].

Table 4 makes a list of the families in the literature and identifies their [RZB15] and [Sut15] labels. To prove the equivalence, one tests by direct computations that the curves of one family are birationally equivalent to a curve of the other (verification scripts are provided in the Appendix B).

A criterion to compare families of ECM-friendly curves

As discussed in Appendix A, an important application of ECM consists in using the same elliptic curve to test smoothness of many integers. In this context, several articles [START_REF] Daniel J Bernstein | Starfish on strike[END_REF]

#{p ∼ n | # E(F p ) is B -smooth} #{p | p ∼ n} ≈ #{x ∼ ne β(E,n,B) | x is B -smooth} #{x | x ∼ ne β(E,n,B) } ,
where the expression p ∼ n denotes that p ∈ [n -2 √ n, n + 2 √ n] and the sign ≈ denotes the equality up to a difference of 1/#{x | x ∼ ne β(E,n,B) }. This notation comes to correct the common heuristic which states that a cardinality of E(F p ) is as smooth as a random integer of the same size.

Table 1 below shows the values of β for the curve E of equation y 2 = x 3 +3x+5 and various values of log 2 n and B. We did a similar experiment for a curve from 200 random families of Theorem 4.1, which suggests that β E,n,B converges uniformly when n and B go to infinity.

The graph also indicates that β = lim β(E, n, B) and α(E) have a linear relationship.

Open question 5.1. Let E be an elliptic curve without complex multiplication. Decide whether there exists a real number β(E) such that

Prob(# E(Fp) is B-smooth | p ∼ n) ∼n Prob(m is B-smooth | m ∼ ne β(E) ),
where ∼ n denotes the asymptotic equivalence, p ∼ n denotes that p ∈ [n -2 √ n, n + 2 √ n], Prob on the left side denotes the Chebotarev density and Prob on the right side denotes the proportion of B-smooth integers in the interval.

Answering the above question goes beyond the scope of this article. Nevertheless, this offers a new point of view on a tool that Peter Montgomery used in experiments to compare elliptic curves. Indeed, Montgomery [Mon92, pages 75-76] considered the value

log(2) • val 2 (E) + log(3) • val 3 (E),
where val 2 and val 3 denote the average value of val 2 (# E(F p )) and val 3 (# E(F p )) when p runs through all the primes of good reduction up to a bound n. These are similar to the first terms of a numeric series that rigorously defines α, as we explain in the next subsection.

Murphy [START_REF] Antony | Polynomial selection for the number field sieve integer factorisation algorithm[END_REF] introduced a tool α which answers the above question for the values taken by polynomials:

α = prime log( ) • ( 1 -1 -val ),
where val is the average value of the valuation in of the set of integers that we study, the average being defined rigorously in the sequel of this section. Indeed, Barbulescu and Lachand in Theorem 1.1 of [START_REF] Barbulescu | Some mathematical remarks on the polynomial selection in nfs[END_REF] proved that β(F) = α(F) for any quadratic polynomial F of primitive fundamental negative discriminant.

5.1. Formal definition of α. We say that a set S of primes admits a Chebotarev density δ, and we write Prob(S) = δ, if lim n→∞

#(S∩Π(n)) #Π(n)
exists and is equal to δ. Here Π(n) denotes the set of primes less than n. For an elliptic curve E and a prime , we define the average valuation at of # E(F p ), where p is a random prime by

val (E) = n≥1 n • Prob({p prime | val (# E(F p ) = n)}).
The convergence of the series defining val (E) is proven in [BBB + 13, Th 2.16], the proof allowing to compute it explicitly using Imρ E, ∞ . Definition 5.1. Given an elliptic curve E and a prime , we put

α (E) = log( )(val (n) -val (E)) and α(E) = prime α (E).
Let us prove the convergence of this series.

Theorem 5.1. For any elliptic curve E /Q without complex multiplication, the series l α l (E) converges.

Proof. By Serre's open image theorem, any elliptic curve without complex multiplication has a finite set of primes such that the mod ∞ Galois image is not surjective in GL 2 (Z ). Hence, the series which defines α has the same nature of convergence as the series corresponding to a curve which would have a surjective Galois image at all primes. From [BBB + 13, Th 2.16], applied for n = 1, we have val (

E) = -1 Prob(E(F p )[ ] Z/ Z) + ((2 +1)) ( -1)( +1) Prob(E(F p )[ ] Z/ Z × Z/ Z). If
a matrix other than I has a non-trivial fixed subspace, it is of the form 1 0 0 a or 1 a 0 1 where a is non-zero. By counting stabilizers, we obtain that in GL 2 (F ) there are ( + 1)( -2) matrices conjugated to 1 0 0 a , 2 -1 conjugated to 1 a 0 1 and, by [BBB + 13, Prop 2.3], we obtain then

val (E) = ( 3 + 2 -2 -1) ( +1) 2 ( -1) 3 . Hence, α (E) = log( )( 1 -1 -val (E)) = O( log( ) 2
), which is the term of a convergent series.

Note that, if a curve E has surjective Galois image at all primes, which is the case for all curves except a finite set of families described by curves, α(E) ≈ -0.8119977339443, which is negative and suggests that the cardinality of an elliptic curve has slightly more chances of being smooth than a random integer of the same size.

Computation of α.

For each family of Theorem 4.1, we compute the value of α.

Example 5.1.

(1) Let us consider the family X 193n of [RZB15] which has E(Q) tors Z/2Z × Z/8Z (row 13 of Table 4). We see that the index of mod 2 i Galois image in GL 2 (Z/2 i Z) is constant for all i ≥ 3. We describe it by saying Serre's exponent is 3 and by [BBB + 13, Th 2.16], we find that val 2 changes from the value when ρ E,2 ∞ is surjective, i.e. 14 9 , to its new value 16 3 . Furthermore, for any generic curve in this family, for all primes different than 2, the corresponding Galois image is surjective. Thus,

α Z/2Z×Z/8Z = α generic + 14 9 - 16 3 log 2 ≈ -3.4355.
(2) Let us consider the Suyama-11 family, which is parameterized in [BBB + 13, Sec. 3.5.1]. For these curves, val 2 changes from 14 9 to 11 3 and val 3 changes from 87 128 to 27 16 . And, for any generic curve in this family, for all primes different than 2 and 3, the corresponding Galois image is surjective. Thus, Given an elliptic curve without complex multiplication, one can use the modular curves to determine it Galois image. Then α(E) is equal to the pre-computed value of the family of E. We can now test the efficiency of α by comparing the smoothness probabilities of # E(F p ) when p is a random prime of a given size n and that of a random integer of size ne α(E) .

Example 5.2. In the following tables, the first two columns give the proportions of B-smooth integers of size n, ne α . We compare them with the proportion of primes p ∼ n such that # E(F p ) is B-smooth. The last two columns indicate relative errors. Where the relative error of a with respect to b is |a-b| |b| . The followings averages are taken over several randomly chosen curves in each family with 2 different values of B and n = 2 25 .

( Often in ECM, one uses curves with better arithmetic i.e. the curves for which the point addition and multiplication are less time consuming, for example, Montgomery curves or twisted Edwards' curves with a = -1. We consider intersecting the families with better values of α with the ones with better arithmetic.

Example 5.3 (A new family). It is known that the family of elliptic curves with torsion subgroup Z/2Z × Z/8Z and the family of twisted Edwards' curves with a = -1 do not intersect. There are however four which have the same value of α as the one with torsion subgroup Z/2Z×Z/8Z and which are also of the form twisted Edwards' with a = -1. One of them is X 192i in [RZB15] and can be transformed into twisted Edwards' form by choosing

a = -1, d = - t 2 + 4 4 64 (t 2 -4) 2 t 2 .
The other familes are X 189d , X 207n and X 211m .

5.4. α(E) over number fields. So far, we have considered rational elliptic curves E and their values of α(E). These curves fare better when we try to factor a random integer N. However, if more information is available about N, one might want to use it in order to factor N. For example, if we know by some oracle that -3 is a square modulo N, we consider families with better values of α over Q( √ -3). Indeed these family can be defined over Q( √ -3), however we restrict ourselves to the families defined over Q. In this case, one must modify the definition of α from its original version of Section 5.1.

Let K be a number field, E, a rational elliptic curve and , a prime. We define the average valuation at of # E(F p ) when p is a random prime which splits completely in K by

val ,K (E) = n≥1 nProb({p prime which splits completely in K | val (# E(F p ) = n)}).
The existence and the computation of val ,K (E) follows from Theorem [BBB + 13, Th 2.16]. We now define α relative to K. Definition 5.2. Given an elliptic curve E /Q, a prime and a number field K, we put

α ,K (E) = log( )(val ,K (n) -val (E)) and α K (E) = prime α (E).
Example 5.4. Let E : y 2 + xy + y = x 3 + 9481x + 89898842 and K = Q(ζ 3 ), the cyclotomic field of degree 3. For E, the mod 2 and mod 3 images of Galois are X 6 and 3D 0 -3aT1 in There are families of curves with α larger than -0.81 (e.g. X 2b -5A 0 -5a). This implies that any random elliptic curve performs better than the curves from these families. The complete list of 1525 families and the corresponding values of α is available at [BS19]. 5.5. Going beyond α. Although α is very easy to compute, one can define more precise tools, e.g.

E(E) = m B-smooth integer ≤ n Prob(m divides# E(F p ) • Prob(x | m is B-smooth),
where x denotes a random integer of the size of n. A key difference between α and E is that α depends on the probabilities of # E(F p ) being divisible by prime-powers but not on that of being divisible by composite numbers. This difference is due to the fact that we have families with Galois images which are cartesian products. The question remains to solve Mazur's program B for the subgroups which are non-cartesian. When mod m Galois image is non-cartesian, divisibility properties can change. For example, two curves can have the same mod 2 and mod 3 Galois images and thus the same value of α yet have different probabilities that 6 divides # E(F p ) as illustrated in the example below.

Example 5.5. Let us consider the curves E 1 : y 2 = x 3 -75x -2950 and E 2 : y 2 = x 3 + 45x -366 which have the mod 2 and mod 3 Galois images. The following table gives compares probabilities of divisibility by 2, 3 and 6 for E 1 and E 2 . These probabilities are computed using mod 6 Galois images for E 1 and E 2 and then using Theorem 2.7 of [BBB + 13].

Curve P(2|#(E(F p )) P(3|#(E(F p ))

P(6|#(E(F p )) α E 1 2/3 3/4 1/2 -1.39 E 2 2/3 3/4 7/12> 2/3• 3/4 -1.39
If the Chebotarev density were a probability, one would say that the fact of being divisible by 2 and that of being divisible by 3 are correlated.

Conclusion and future work

The goal of this work was to classify infinite families of ECM-friendly elliptic curves. The exhaustive method of finding these families and the experimental tool α enables us to conclude that there do not exist other ECM-friendly curves over Q than 1525 families provided and several new families are better.

One can obtain the complete list of genus 0 and genus 1 modular curves of prime-power level. This list is independent of the number fields over which the elliptic curves are defined. Hence the list of ECM-friendly families is contained in a finite set independent of the number field.

One can also consider modular curves of higher genus and finitely many elliptic curves arising from them for ECM as a natural extension of this work. This can be interesting for implementation of ECM. This raises the question of efficiently computing X H for subgroups H of higher level.

A different question is that of a rigorous analysis of the smoothness properties of # E(F p ) which make use of α.

The next stage of NFS consists in solving a linear system to find a tuple (u φ ) φ collected such that x 1 := φ φ(α) u φ and x 2 := φ φ(β) u φ are squares. Finally, one computes two polynomials r 1 and r 2 in Z[x] such that r 1 (α) 2 = x 1 and r 2 (β) 2 = x 2 and obtain the solution y 2 1 ≡ y 2 2 (mod N ) where y 1 = r 1 (m) mod N and y 2 = r 2 (m) mod N , where m id the common root of f and g modulo N .

If gcd(y 1 -y 2 , N ) ∈ {1, N }, one finds a factor, otherwise one goes back to the beginning of the algorithm (in practice one computes many solutions (y 1 , y 2 ) simultaneously).

When computing discrete logarithms in the multiplicative group of F p n for a prime p, the best asymptotic complexity is obtained by the extended tower number field sieve [START_REF] Kim | The extended tower number field sieve: A new complexity for the medium prime case[END_REF], which is a variant of NFS. The first step is to select a factor η of n and a polynomial h(t) ∈ Z[t] of degree η which is irreducible modulo p. Let ι be a root of H in its number field. Then one selects two polynomials f and g in Z[t, x] such that, if ω is a root of H in F p [t]/ h , the polynomial f (ω, x) and g(ω, x) have a common irreducible factor ϕ ∈ F p (ω)[x] of degree κ := n/η. If we call α and β roots of f and g respectively in their number fields, we obtain the following diagram:

Q(ι) Q(ι, α) Q(ι, β)
Q Once H, f and g have been selected, the algorithm continues by enumerating a large number of pairs a(t), b(t) ∈ Z[t] and collecting all but a negligible proportion of the pairs a and b for which N Q(ι,α) (a(ι) -αb(ι)) and N Q(ι,β) (a(ι) -βb(ι)) are B-smooth for B = L p n (1/3, 3 8/9). In the next step, one factors a(ι) -αb(ι) and respectively a(ι) -βb(ι) into prime ideals and writes a linear system whose coefficients are the valuations of prime ideals and the unknowns are in bijection with the prime ideals of norm less than B. The solution allows us to obtain the discrete logarithm of any element in a time which is negligible with respect to the cost of collecting the pairs a(t) and b(t).

As in the factoring variant of NFS, the smoothness tests are done with ECM. We note that in the case of discrete logarithm we have a larger number of methods to select the polynomials f and g. For example, in the case of the generalized Joux and Lercier method [START_REF] Joux | Improvements to the general number field for discrete logarithms in prime fields[END_REF][START_REF] Barbulescu | Improving NFS for the discrete logarithm problem in non-prime finite fields[END_REF], one can set f to be any irreducible polynomial in Z[x] having an irreducible factor ϕ of degree κ. For example, in [START_REF] Barbulescu | Discrete logarithms in GF(p 2 ) -160 digits[END_REF], the authors used f (x) = φ 8 (x) so that for any pair (a, b), N Q(α) (a -αb) = a 4 + b 4 , so half of the integers to factor in NFS can be tackled with elliptic curves defined over Q(ζ 8 ), where ζ 8 is a primitive 8th root of unity. Moreover, when h

= h 0 + h 1 t + h 2 x t for h 0 , h 1 , h 2 ∈ Z, N Q(ι,α) (a(ι)-αb(ι)) = N Q(ι) (a -ιb ) = h 0 v 2 +h 1 uv +h 2 u 2 , where u-ιv = N Q(ι,α)/Q(ι) (a(ι)-αb(ι)).
To sum up, an improvement of ECM adapted to integers of the form h 2 u 2 + h 1 uv + h 0 v 2 would translate in an improvement of the relation collection of NFS and this can change the systems based on discrete logarithm in fields F p 2n . An improvement on ECM in the general case would have consequences on the system based on factoring and discrete logarithm. Hence, for cryptologic applications, it is then important to find all the infinite families of elliptic curves defined over given number fields which have exceptional Galois images for some torsion, and to verify experimentally if they can bring a speed-up of ECM. rows 6. to 11. These rows consider families which parameterize the elliptic curves having a point of order n for n = 5, 7, 8, 9, 1011, 12. The correspondence with the parameterizations of [RZB15] and [Sut15] is done to the matrix groups which are { 1 * 0 * ∈ GL 2 (Z/nZ)}.

row 12. To our knowledge, this family is not reported to be used in ECM computations, it is listed here for reference in the following rows. row 13. Montgomery noted that every elliptic curve with torsion Z/2 × Z/8 can be put in Montgomery form, and it can therefore be put in twisted Edwards form. This shows that the parameterizations of [START_REF] Oliver | Finding suitable curves for the elliptic curve method of factorization[END_REF], [START_REF] Lawrence | An FFT extension of the elliptic curve method of factorization[END_REF] and [START_REF] Bernstein | Ecm using edwards curves[END_REF] describe the same set of elliptic curves. The following script checks that the family of Section 2.3.2 in [START_REF] Heer | JKL-ECM: an implementation of ECM using hessian curves[END_REF] is the same family in disguise. rows 14. In Sections 3.1, 3.5 and 3.7 of [START_REF] Brier | New families of ecm curves for cunningham numbers[END_REF] we have respectively parameterizations of the curves such that E[n](Q(ζ 3 )) Z/nZ × Z/nZ for n = 3, 4 and respectively 5. The Galois image in GL 2 (Z/nZ) has order ϕ(n) and surjective determinant, so the corresponding group is { α 0 0 1 | a ∈ (Z/nZ) * }. We identify these groups as corresponding to 3D 0 -3aT1, X 58i and respectively 5H 0 -5aT1. row 15. In the previous paragraph, we explained how to identify the Galois image. The following script checks that the family in Section 3.2 of [START_REF] Brier | New families of ecm curves for cunningham numbers[END_REF] an the family in Section 3.5.1 of [START_REF] Heer | JKL-ECM: an implementation of ECM using hessian curves[END_REF] coincide. row 16. The following script checks that the family of Section 3.5 of [START_REF] Brier | New families of ecm curves for cunningham numbers[END_REF] and Section 3 of [START_REF] Daniel J Bernstein | Starfish on strike[END_REF]. It is interesting to note that this family is not equal to that of row 12. Indeed, the condition a =which was imposed in order to improve the arithmetic cost, also improved the torsion properties. row 17. Section 3.7 of [START_REF] Heer | JKL-ECM: an implementation of ECM using hessian curves[END_REF] and Table 3 give the same parameterization of the pairs a(t), b(t): a = -27t 20 -6156t 15 -13338t 10 + 6156t 5 -27 and b = 54t 30 -28188t 25 -540270t 20 -540270t 10 + 28188t 5 + 54. row 18. and 19. The families Suyama-11 and Suyama-9/4 are obtained from Suyama by imposing additional conditions. For Suyama-11 the condition on a Montgomery curve M A,B is (A + 2)/ B = -, which in Edwards coordinates E a,d is a = -. Hence, Suyama-11 is the intersection of X 13f and 3B 0 -3aT2. Similarly, the family Suyama-9/4 is obtained from Suyama by the additional condition on M A,B is B = , or equivalently in Edwards coordinates E a,d the condition is a -d = . The unique twist of X 13 such that a -d is a square for all elements of the parameterization is X 13d . Hence, Suyama-9/4 is the intersection of X 13d and 3B 0 -3aT2. rows 20. to 23. Section 2.1 identified the families of these rows as corresponding to parameterizations of some subgroups H. to identify the label we tested several numerical curves in the families of [BBB + 13] and computed the Galois group of Gal(Q(E[8])/Q).

IMJ-PRG, (Sorbonne Univ., Univ. Paris Diderot, CNRS), Inria, Paris E-mail address: razvan.barbulescu@imj-prg.fr sudarshan.shinde@imj-prg.fr

label parameterization 3B0-3aT1 3B0-3aT2 a = -3(t + 3)(t -27) 3 , b = -2(t 2 + 18t -27)(t -27) 4 3D0-3aT1 a = -3(t 2 -6t + 36)(t + 6)t, b = -2(t 2 -6t -18)(t 4 + 6t 3 + 54t 2 -108t + 324) 9B0-9aT1 9B0-9aT2 a = -3(t 3 + 9t 2 + 27t + 3)(t + 3), b = (-2t 6 -36t 5 -270t 4 -1008t 3 -1782t 2 -972t + 54) 9C0-9aT1 9C0-9aT2 a = -3(t 3 + 3)(t 2 -3t + 9) 3 (t + 3) 3 , b = -2(t 6 + 18t 3 -27)(t 2 -3t + 9) 4 (t + 3) 4 9H0-9aT1 a = -3(t 3 + 9)(t 3 + 3)(t 2 + 3t + 3)(t 2 -3t + 3)(t 2 + 3), b = -2(t 12 + 18t 9 + 162t 6 + 486t 3 + 729)(t 4 + 3t 2 + 9)(t 2 -3) 9H0-9bT1 9H0-9bT2 a = -3(t 6 -18t 5 + 171t 4 + 180t 3 -297t 2 -162t + 189)(t 3 + 9t 2 -9t -9)(t 3 -3t 2 -9t + 3), b = -2(t 12 + 126t 10 -1944t 9 + 6723t 8 + 23328t 7 -21708t 6 -58320t 5 + 34263t 4 + 54432t 3 -24786t 2 -17496t + 9477)(t 6 -18t 5 -45t 4 + 180t 3 + 135t 2 -162t -27) 9H0-9cT1 a = 144(t 6 + 9t 5 + 9t 4 -90t 3 + 27t 2 + 81t + 27)(t + 3)(t + 1)(t -1)(t -3)t, b = 16(t 12 + 18t 11 + 126t 10 -18t 9 -2025t 8 -972t 7 + 13284t 6 -2916t 5 -18225 t 4 -486t 3 + 10206t 2 + 4374t + 729)(t 2 + 6t -3)(t 2 -6 t -3)(t 2 -3) 9I0-9aT1 9I0-9aT2 a = -3(17t 9 + 9t 8 -144t 6 -918t 5 + 810t 4 -3672t 3 -648t 2 -4131t -27)(t 3 + 3t 2 -9t -3), b = 142t 18 + 684t 17 -162t 16
-10944t 15 -10152t 14 + 24624t 13 -131976t 12 + 393984t 11 + 834948t 10 -1128600t 9 + 1628100t 8 -7978176t 7 + 12435768t 6 -4210704t 5 + 14154264t 4 + 12410496t 3 + 8314974t 2 + 498636t -1458 9I0-9bT1 9I0-9bT2 a = -144(t 3 + 9t 2 -9t + 15)(t 3 + 9t + 6)(t 3 -3)(t + 1)(t -1), b = 16(t 6 + 12t 5 + 27t 4 + 48t 3 -9t 2 -108t -99) (t 6 + 12t 5 -9t 4 + 12t 3 -9t 2 + 9)(t 6 -6t 5 + 63t 4 -132t 3 + 207t 2 -54t -207) 9I0-9cT1 9I0-9cT2 a = -3(t 9 -9t 8 + 27t 7 -48t 6 + 54t 5 -45t 4 + 27t 3 -9t 2 + 1)(t 3 -3t 2 + 1), b = -2t 18 + 36t 17 -270t 16 + 1140t 15 -3114t 14 + 5940t 13 -8256t 12 + 8460t 11 -6480t 10 + 4064t 9 -2718t 8 + 2160t 7 -1470t 6 + 612t 5 -54t 4 -84t 3 + 36t 2 -2 9J0-9aT1 9J0-9aT2 a = -3(t 9 -9t 7 + 6t 6 + 18t 5 -9t 4 -27t 3 + 27t 2 -9t + 1)(t 3 + 3t 2 -6t + 1) 3 (t 2 -t + 1), b = -2(t 18 -18t 16 + 24t 15 + 81t 14 -198t 13 -30t 12 + 540t 11 -828t 10 + 884t 9 -729t 8 -180t 7 + 1491t 6 -1944t 5 + 1341t 4 -552t 3 + 135t 2 -18t + 1)(t 3 + 3t 2 -6t + 1) 4 9J0-9bT1 9J0-9bT2 a = -3(t 9 -9t 8 -1800t 6 -54t 5 + 5022t 4 -216t 3 -5184t 2 -243t + 1971) (t 3 -9t 2 -9t + 9) 3 (t 2 + 3), b = -2(t 18 -18t 17 + 81t 16 + 4176t 15 -37692t 14 -12312t 13 -559980t 12 -208656t 11 +2381886t 10 -184140t 9 -4348242t 8 + 1154736t 7 + 6764148t 6 + 635688t 5 -8021916t 4 -2321136t 3 + 5447817t 2 + 931662t -1363959)(t 3 -9t 2 -9t + 9) 4 9J0-9cT1 9J0-9cT2 a = -3(5t 3 -9t 2 -9t -3)(t 3 + 9t 2 + 27t + 3)(t 3 -9t + 12)(t 2 + 3)(t + 3) 3 (t -3) 3 t 3 , b = 2(11t 6 -6t 5 -63t 4 + 156t 3 -99t 2 -54t -9)(t 6 + 6t 5 -9t 4 -12t 3 -225t 2 + 486t + 9) (t 6 + 6t 5 -48t 3 -63t 2 -54t -18)(t + 3) 4 (t -3) 4 t 4 27A0-27aT1 27A0-27aT2 a = -3(t 9 + 9t 6 + 27t 3 + 3)(t 3 + 3), b = -2t 18 -36t 15 -270t 12 -1008t 9 -1782t 6 -972t 3 + 54 ??

Table 2. Curves with exceptional Galois images in GL 2 (Z 3 ) associated to groups which do not contain -I. For each subgroup H containing -I we call label H T1, label H T2, . . . the subgroups of H of index 2, up to conjugacy, which do not contain -I. The parameterization (a,b) corresponds to T1 and the parameterization (9a, -27b) corresponds to T2. If H has a unique index two subgroup, up to conjugacy, then the parameterization (9a, -27b) is a second family of Galois group T1.

label parameterization 5D0-5aT1 5D0-5aT2 a = -27t 4 -6156t 3 -13338t 2 + 6156t -27, b = 54(t 4 -522t 3 -10006t 2 + 522t + 1)(t 2 + 1) 5D0-5bT1 5D0-5bT2 a = -27t 4 + 324t 3 -378t 2 -324t -27, b = 54(t 4 -18t 3 + 74t 2 + 18t + 1)(t 2 + 1) 5H0-5aT1 5H0-5aT2 a = -27(t 8 + t 7 + 7t 6 -7t 5 + 7t 3 + 7t 2 -t + 1) (t 8 -4t 7 + 7t 6 -2t 5 + 15t 4 + 2t 3 + 7t 2 + 4t + 1)(t 4 + 3t 3 -t 2 -3t + 1), b = 54(t 8 + 6t 7 + 17t 6 + 18t 5 + 25t 4 -18t 3 + 17t 2 -6t + 1) (t 8 -4t 7 + 17t 6 -22t 5 + 5t 4 + 22t 3 + 17t 2 + 4t + 1) (t 8 -t 6 + t 4 -t 2 + 1)(t 4 -2t 3 -6t 2 + 2t + 1)(t 2 + 1) 25B0-25aT1 25B0-25aT2 a = -27t 20 -324t 15 -378t 10 + 324t 5 -27, b = 54(t 20 + 18t 15 + 74t 10 -18t 5 + 1)(t 8 -t 6 + t 4 -t 2 + 1)(t 2 + 1) 25B0-25bT1 25B0-25bT2 a = -27t 20 -6480t 19 -58320t 18 -181440t 17 -473040t 16 -816156t 15 -1561680t 14 -1645920t 13 -2157840t 12 -1121040t 11 -1633338t 10 + 1121040t 9 -2157840t 8 +1645920t 7 -1561680t 6 + 816156t 5 -473040t 4 + 181440t 3 -58320t 2 + 6480t -27, b = -54(t 20 -510t 19 -13590t 18 -32280t 17 -82230t 16 -153522t 15 -302910t 14 -273540t 13 -412830t 12 -268230t 11 -262006t 10 + 268230t 9 -412830t 8 + 273540t 7 -302910t 6 + 153522t 5 -82230t 4 + 32280t 3 -13590t 2 + 510t + 1) (t 8 + 6t 7 + 17t 6 + 18t 5 + 25t 4 -18t 3 + 17t 2 -6t + 1)(t 2 + 1) 7B0-7aT1 7B0-7aT2 a = -27(t 2 + 13t + 49) 3 (t 2 + 5t + 1), b = 54(t 4 + 14t 3 + 63t 2 + 70t -7)(t 2 + 13t + 49) 4 7E0-7aT1 7E0-7aT2 a = -27(t 6 + 229t 5 + 270t 4 -1695t 3 + 1430t 2 -235t + 1)(t 2 -t + 1), b = 54t 12 -28188t 11 -483570t 10 + 2049300t 9 -3833892t 8 + 7104348t 7 -13674906t 6 + 17079660t 5 -11775132t 4 + 4324860t 3 -790074t 2 + 27540t + 54 7E0-7bT1 7E0-7bT2 a = -432(t 6 -11t 5 + 30t 4 -15t 3 -10t 2 + 5t + 1)(t 2 -t + 1), b = 3456t 12 -62208t 11 + 404352t 10 -1223424t 9 + 1969920t 8 -1679616t 7 +943488t 6 -767232t 5 + 601344t 4 -158976t 3 -51840t 2 + 20736t + 3456 7E0-7cT1 7E0-7cT2 a = -189(5t 2 -t -1)(3t 2 -9t + 5)(t 2 -t + 1)(t 2 -3t -3), b = -2646(9t 4 -12t 3 -t 2 + 8t -3)(3t 4 -4t 3 -5t 2 -2t -1)(t 4 -6t 3 + 17t 2 -24t + 9) 13B0-13aT1 13B0-13aT2 a = -3(t 8 + 235t 7 + 1207t 6 + 955t 5 + 3840t 4 -955t 3 + 1207t 2 -235t + 1) (t 4 -t 3 + 5t 2 + t + 1) 3 , b = -2(t 12 -512t 11 -13079t 10 -32300t 9 -104792t 8 -111870t 7 -419368t 6 + 111870t 5 -104792t 4 + 32300t 3 -13079t 2 +512t + 1)(t 4 -t 3 + 5t 2 + t + 1) 4 (t 2 + 1) 13B0-13bT1 13B0-13bT2 a = -27(t 8 -5t 7 + 7t 6 -5t 5 + 5t 3 + 7t 2 + 5t + 1)(t 4 -t 3 + 5t 2 + t + 1) 3 , b = 54(t 12 -8t 11 + 25t 10 -44t 9 + 40t 8 + 18t 7 -40t 6 -18t 5 + 40t 4 + 44t 3 + 25t 2 + 8t + 1) (t 4 -t 3 + 5t 2 + t + 1) 4 (t 2 + 1)

Table 3. Curves with exceptional Galois image in GL 2 (Z ) for = 5, 7, 13 corresponding to groups which do not contain -I. For each subgroup H containing -I we call label H T1, label H T2, . . . the subgroups of H of index 2, up to conjugacy, which do not contain -I. Set = 1 if -1 is a square mod , -1 otherwise. The parameterization (a,b) corresponds to T1 and the parameterization ( 2 a, 3 b) corresponds to T2. If H has a unique index two subgroup, up to conjugacy, then the parameterization ( 2 a, 3 b) is a second family of Galois group T1.

α

   = α generic +

d e f

  Kubert ( b , c ) : r e t u r n E l l i p t i c C u r v e ( [ ( 1 -c ) ,-b,-b , 0 0 ] ) d e f A t k i n M o r a i n 8 2 ( a l p h a ) : d = a l p h a * ( 8 * a l p h a +2) / ( 8 * a l p h a ˆ2 -1) b = ( 2 * d-1) * ( d-1) c = ( 2 * d-1) * ( d-1)/d r e t u r n Kubert ( b , c ) d e f H e e r M c G u i r e R o b i n s o n 2 3 2 ( t ) : nu = ( t ˆ4-6 * t ˆ2+1) / ( 4 * ( t ˆ2+1) ˆ2 ) b = nuˆ2 -1/16 r e t u r n Kubert ( b , 0 ) Q.< t> = QQ [ ] ; K = Q. f r a c t i o n f i e l d ( ) ; t = K( t ) a s s e r t A t k i n M o r a i n 8 2 ( t ) . i s i s o m o r p h i c ( H e e r M c G u i r e R o b i n s o n 2 5 1 ( 4 * t +1) )

  d e f H e e r M c G u i r e R o b i n s o n 2 3 1 ( t ) : mu = ( 2 * t ˆ3+1) / ( 3 * t ˆ2 ) a = -27 * mu * (muˆ3+8) b = 5 4 * (muˆ6-20 * muˆ3 -8) r e t u r n E l l i p t i c C u r v e ( [ a , b ] ) d e f B r i e r C l a v i e r 3 2 ( lam , t a u ) : a = ( -3) * lam ˆ4 * ( t a u ˆ12-8 * t a u ˆ9+240 * t a u ˆ6 -464 * t a u ˆ3+16) b = ( -2) * lam ˆ6 * ( t a u ˆ18 -12 * t a u ˆ15 -480 * t a u ˆ12+3080 * t a u ˆ9 -12072 * t a u ˆ6+4128 * t a u ˆ3+64) r e t u r n a , b d e f t w i s t e d B r i e r C l a v i e r ( t a u ) : Qt = t au . p a r e n t ( ) ; Q3.< s3> = Q u a d r a t i c F i e l d ( -3) ; Qt3.< t> = Q3 [ ] ; t a u = Qt3 ( t a u ) a , b = B r i e r C l a v i e r 3 2 ( s 3 / ( 3 * t a u ) , t a u ) Kt = Qt . f r a c t i o n f i e l d ( ) ; a = Kt ( a ) ; b = Kt ( b ) r e t u r n E l l i p t i c C u r v e ( [ a , b ] ) Q.< t> = QQ [ ] a s s e r t t w i s t e d B r i e r C l a v i e r ( t ) . i s i s o m o r p h i c ( H e e r M c G u i r e R o b i n s o n 2 3 1 (-1/ t ) )

  d e f B r i e r C l a v i e r 3 5 ( t ) : a = -27 * ( t ˆ8+14 * t ˆ4+1) b = 5 4 * ( t ˆ12 -33 * t ˆ8-33 * t ˆ4+1) r e t u r n E l l i p t i c C u r v e ( [ a , b ] ) d e f B e r n s t e i n B i r k n e r L a n g e 3 ( e ) : d e f MontgomeryToWeierstrass (A, B) : r e t u r n E l l i p t i c C u r v e ( [ 0A/B, 0 1/B ˆ2 , 0 ] ) d e f t w i s t e d E d w a r d s T o W e i e r s t r a s s ( a , d ) : r e t u r n MontgomeryToWeierstrass ( 2 * ( a+d ) / ( a-d ) , 4 / ( a-d ) ) r e t u r n t w i s t e d E d w a r d s T o W e i e r s t r a s s (-1,-e ˆ4 ) . s h o r t w e i e r s t r a s s m o d e l ( ) Q.< t>=QQ [ ] ; K = Q. f r a c t i o n f i e l d ( ) ; t = K( t ) B r i e r C l a v i e r 3 5 ( t ) . i s i s o m o r p h i c ( B e r n s t e i n B i r k n e r L a n g e 3 ( t ) )

  The case of twisted Edwards' curves. [Section 3.4.1 in [BBB + 13]] We consider a subfamily of twisted Edwards' curves E a,d : ax 2 + y 2 = 1 + dx 2 y 2 given by a = -1 and d = -e 4 . We set L = Q(e)(E -1,-e 4 [8]). Using MAPLE, we obtain that [L : Q(e)] = 32. We are interested in finding all the subfamilies of E -1,-e 4 i.e. all the parameterizations e = e(t) for which the degree of L is less than 32. We note that the existence of Weil pairing implies that Q(ζ

8 ) ⊂ L

[START_REF] Joseph H Silverman | The Arithmetic of Elliptic Curves[END_REF] III.8

]. Thus to simplify the computations, we proceed in two steps: first we compute equations for the subfields containing

Table 1 .

 1 Values of β(E, n, B) for E : y 2 = x 3 + 3x + 5 and various values of log n and B.primes p less than a bound X for which # E(F p ) is B-smooth, where X and B are given parameters. In the rest of this section we study if one can compare this proportion for two elliptic curves, regardless of the two parameters X and B.Given an elliptic curve E and two integers n and B, let β(E, n, B) be a real number such that

	, [HMR16],

Table 2 .

 2 On the other hand, p splits completely in K if, and only if, p ≡ 1 mod 3. The best 50 values of α over Q and Q(ζ n ) for n = 3, 4, 5, where ζ n is a primitive n-th root of unity, for the rational families correspond to the families given in Tables 5, 6, 7 and 8 respectively.

	For E, val 2,K changes from 14 9 (generic value) to 8 3 and val 3,K changes from 87 128 (generic value) to 21 8 . Thus,
	α K (E) = α generic +	14 9	-	8 3	log 2 +	87 128	-	21 8	log 3 ≈ -3.7193.

Appendix A: Cryptologic utilization of ECM

In cryptology, ECM is used as an algorithm to test B-smoothness : given an integer N , find all its prime factors less than B. Under a conjecture about the existence of smooth integers in short intervals [Cro07, Conj 1], H. Lenstra Jr. proved that, if N has a prime factor less than B, ECM will find it with probability at least 1/2 in time M (N )L B (1/2, √ 2) 1+o(1) , where M (N ) = O((log N ) 2 ) is the cost of the arithmetic operations in Z/N Z where the L notation is as follows:

Smoothness tests play a key role in cryptology. Indeed, when factoring integers with NFS, one selects two distinct number fields Q[x]/f (x) and Q[x]/g(x) such that f and g have a common root m modulo N ; we call α (resp. β) a root of f (resp. g) in its number field. The next stage of NFS consists of enumerating polynomials φ(x) ∈ Z[x] and collecting all but a negligible proportion of those φ such that

The textbook implementation of NFS is without ECM as a subroutine. However in practice we use a hybrid version The smoothness tests are done using ECM both in the complexity analysis and in practice, e.g. in the open source implementation CADO-NFS [BGK + ].

Appendix B: identifying families of ECM-friendly families

In this appendix, we give the scripts of verifications of Table 4

)}, which corresponds to the elliptic curves having a rational point of order 4. Theorem 3.3 of [BBJ + 08] states that an elliptic curve can be put in twisted Edwards' form such that a = if and only if it has a rational point of order 4. X 13h does have a point of order 4 and can be put in twisted Edwards' form with a = . row 4. Theorem 5.4 of [START_REF] Daniel J Bernstein | Twisted Hessian curves[END_REF] ensures that a curve is isogenous to a twisted Hessian curve if and only if it is isogenous to a curve having a point of order 3. The family 3B 0 -3a corresponds to the group { * * 0 * ∈ GL 2 (Z/3Z)}, which characterizes the curves which are isogenous to curve with a point of order 3. row 5. On page 262 of [Mon87] we read the description of the Suyama family as the Montgomery curves M A,B for which there exist

3 ) and B = (x 3 -1) 2 /(4x 3 y 2 3 ). These equations are equivalent to Ψ M A,B , 3(x 3 ) = 0 and By 2 3 = x 3 3 + Ax 2 3 + x 3 and are further equivalent to the fact that M A,B has a torsion point of order 3. Hence, the SUyama family is equivalent to the intersection of X 13 (Montgomery form) and 3B 0 -3aT2 (point of order 3). On page 263 of the same article, one has a parameterization of a subset of the Suyama family which has a point of infinite order, this family also being called Suyama.

#

Family label in our tables comment ⊂

Section 2 of [BCKL15] 3B 0 -3a isogenous to a curve with a point of order 3 5 Section 10.3.

-3.1514 X13c-3B0-3aT1 -3.1442 X13c-3B0-3aT2 -3.1442 X13e-3B0-3aT1 -3.1442 X13e-3B0-3aT2 -3.1442 X13g-3B0-3aT1 -3.1442 X13g-3B0-3aT2 -3.1442 X8c-3B0-3aT1 -3.1442 X8c-3B0-3aT2 -3.1442 X6-3D0-3aT1 -3.1013 X6-9B0-9aT1 -3.1013 X6-9B0-9aT2 -3.1013 X16-3D0-3aT1 -3.0977 X16-9B0-9aT1 -3.0977 X16-9B0-9aT2 -3.0977 X17-3D0-3aT1 -3.0977 X17-9B0-9aT1 -3.0977 X17-9B0-9aT2 -3. -3.6616 X10d-3B0-3aT1 -3.4980 X10d-3B0-3aT2 -3.4980 X13d-3B0-3aT1 -3.4980 X13d-3B0-3aT2 -3.4980 X13f-3B0-3aT1 -3.4980 X13f-3B0-3aT2 -3.4980 X13h-3B0-3aT1 -3.4980 X13h-3B0-3aT2 -3.4980 X8d-3B0-3aT1 -3.4980 X8d-3B0-3aT2 -3.4980 -3.4305 X13d-3B0-3aT1 -3.3825 X13d-3B0-3aT2 -3.3825 X13f-3B0-3aT1 -3.3825 X13f-3B0-3aT2 -3.3825 X13h-3B0-3aT1 -3.3825 X13h-3B0-3aT2 -3.3825 X8d-3B0-3aT1 -3.3825 X8d-3B0-3aT2 -3.3825 X13-3B0-3aT1 -3.1514 X13-3B0-3aT2 -3.1514 X8-3B0-3aT1 -3.1514 X8-3B0-3aT2 -3.1514 X13c-3B0-3aT1 -3.1442 X13c-3B0-3aT2 -3.1442 X13e-3B0-3aT1 -3.1442 X13e-3B0-3aT2 -3.1442 X13g-3B0-3aT1 -3.1442 X13g-3B0-3aT2 -3.1442 X8c-3B0-3aT1 -3.1442 X8c-3B0-3aT2 -3.1442 X6-3D0-3aT1 -3.1013 X6-9B0-9aT1 -3.1013 X6-9B0-9aT2 -3.1013 X16-3D0-3aT1 -3.0977 X16-9B0-9aT1 -3.0977 X16-9B0-9aT2 -3.0977


Eike Neumann

come

Parametrised second-order complexity theory with applications to the study of interval computation

Parametrised second-order complexity theory with applications to interval computation

Eike Neumann

Aston University Birmingham, UK Florian Steinberg 1

INRIA Sophia Antipolis, France

A full version of this paper is available on the arXiv [START_REF] Neumann | Parametrised second-order complexity theory with applications to the study of interval computation[END_REF]. This abstract is kept fairly brief and assumes familiarity with many of the notions central to its topic. A nice and exhaustive introduction to the topic can be found in [START_REF] Kawamura | Computational Complexity in Analysis and Geometry[END_REF]. Other sources for lookup of details are [START_REF] Schröder | Bounded time computation on metric spaces and Banach spaces[END_REF] and the full version of this paper.

Computable analysis is an extension of the theory of computation over the natural numbers to continuous data, such as real numbers and real functions, based on the Turing machine model of computation. Computability of real numbers is studied already in Turing's paper [START_REF] Mathison | On computable numbers, with an application to the Entscheidungsproblem[END_REF] on the halting problem. Any algorithm based on computable analysis can be implemented directly on a physical computer. It consists of a rigorous specification of input and output, so that it precisely describes the steps that have to be taken to obtain the desired result to a given accuracy. Software packages based on computable analysis include iRRAM [START_REF] Th | iRRAM -Exact Arithmetic in C++[END_REF], Ariadne [START_REF] Benvenuti | Reachability computation for hybrid systems with Ariadne[END_REF], AERN [START_REF] Konečný | A Haskell library for Approximating Exact Real Numbers (AERN)[END_REF], and RealLib [START_REF] Lambov | The basic feasible functionals in computable analysis[END_REF].

For the study of practical algorithms it is clear that computational complexity should play a central role. Whilst the notion of computability over continuous data is robust, well understood, and universally accepted in the computable analysis community, computational complexity in analysis is far less developed and even some basic definitions are the subject of ongoing debate. One of the main reasons for such a notion not being available until recently was the lack of an accepted notion of feasibility for second-order functionals. A candidate solution had been proposed by Mehlhorn already in 1975 [11], but it remained a point of debate for a long time to which extent this class fully captures the intuitive notion of feasibility [START_REF] Cook | Computability and Complexity of Higher Type Functions[END_REF]. A characterization of this class by means of resource bounded oracle Turing machines due to Kapron and Cook [START_REF] Kapron | A new characterization of type-2 feasibility[END_REF] opened the field up for applications. Based on this characterization, Kawamura and Cook introduced a framework for complexity of operators in analysis [START_REF] Kawamura | Complexity theory for operators in analysis[END_REF].

However, there remains a gap between theory and practice. Within the framework of Kawamura and Cook it is impossible to model the behaviour of software based on computable analysis such as the libraries mentioned above. The reason for this is that all these implementations are based on interval arithmetic or extensions thereof, such as Taylor models. The encodings that underlie these approaches are known to exhibit highly pathological behaviour within the framework of Kawamura and Cook [START_REF] Kawamura | Function spaces for second-order polynomial time[END_REF][START_REF] Steinberg | Computational Complexity Theory for Advanced Function Spaces in Analysis[END_REF] and the encodings that are used as substitutes do not reflect the behaviour of the software appropriately. For instance, in the Kawamura-Cook model any encoding of the space of continuous functions which renders evaluation polytime computable also allows for the computation of some modulus of continuity of a given function in polynomial time. In iRRAM this requires an exponential exhaustive search [START_REF] Brauße | A minimal representation for continuous functions[END_REF]. The present work is an attempt to bridge this gap by extending the framework of Kawamura and Cook in order to develop a meaningful complexity 1

Second-order complexity theory

Let M ? be an oracle machine, where an oracle is an element of Baire space B := Σ * Σ * . For a fixed oracle ϕ such that the machine converges on all inputs, let M ϕ denote the function it computes. Every such machine computes a partial operator on Baire space via ϕ → M ϕ . In second-order complexity theory, the oracle ϕ is considered an input of the computation and a function bounding the time consumption is allowed to depend on the size of the oracle. The size of an oracle is the worst-case length-increase from input to output and denoted by |ϕ| : N → N. A time bound for an oracle machine should thus be of type

N N × N → N.
The class of second-order polynomials is the smallest class of functions N N × N → N containing all constant functions returning a polynomial, closed under point-wise addition and multiplication and closed under application of the functional argument. A partial operator F : ⊆ B → B is polytime computable, if there is an oracle machine M ? that computes F and a second-order polynomial P which bounds its running time. It was proved by Kapron and Cook [START_REF] Kapron | A new characterization of type-2 feasibility[END_REF] that a total operator is polytime computable in this sense if and only if the corresponding functional is basic feasible or polytime in the sense of Mehlhorn [11].

For more general spaces representations are used: A representation ξ of a set X is a partial surjective function ξ : ⊆ B → X. Here, Baire space may be replaced with spaces of functions on easily encodable sets like N → Q. A represented space is a pair X = (X, ξ X ) of a set and a representation of that set. For x ∈ X, the elements of ξ -1 X (x) are called the

names of x. A realiser of f : X → Y is some operator F : ⊆ B → B that maps names of x to names of f (x), i.e., ξ Y (F (ϕ)) = f (ξ X (ϕ)
) for all ϕ from the domain of ξ X . A function between represented spaces is called computable if it has a computable realiser. It is called polytime computable if it has a polytime computable realiser.

Complexity on the reals

Define the Cauchy representation of R as follows: A function ϕ : N → D from the naturals to the dyadic rational numbers is a name of a real number x if and only if |ϕ(n) -x| ≤ 2 -n for all n ∈ N. While the Cauchy representation is straightforward to realize on a physical computer, a naive implementation can suffer exponential overhead in many calculations if aliased branches of a computation tree need to be evaluated twice to the same accuracy. Any serious implementation has to rely on caching-and memoisation-techniques, which introduces conceptual complexity, and tends to lead to high memory consumption. The algorithms in rigorous numerical analysis and exact real computation are usually based on interval methods. Let ID denote the set of closed intervals with dyadic rational endpoints.

Definition 1. A sequence (I n ) n∈N ⊆ ID is a ξ Ri -name of x ∈ R if it is monotone, i.
e. I n+1 ⊆ I n for all n, and such that {x} = n∈N I n .

The use of the interval representation is avoided in real complexity theory as it does not lead to a good notion of complexity: Every real number has names that keep the sequence of intervals constant for an arbitrary long time and these names are of slowly increasing size. As a consequence, the represented space has very pathological complexity theoretical properties. Parametrised spaces Let ξ : ⊆ B → X be a representation. A parameter for ξ is a single-valued total map µ from dom(ξ) to N N with monotone values. A triple (X, ξ, µ) is called a preparametrised space. A familiar class of parameters are restrictions of the size function ϕ → |ϕ|. For any representation, the restriction of the size function to its domain is a parameter and is called the standard parameter for the representation. Definition 2. Let (X, ξ X , µ X ) and (Y, ξ Y , µ Y ) be preparametrised spaces. A function f : X → Y is called computable in polynomial time if there is an oracle machine M ? that fulfills the following three conditions: Firstly it computes a realizer of f . Secondly, there exists a second-order polynomial P that bounds its running time, i.e., time M ? (ϕ, a) ≤ P (µ X (ϕ), |a|). And finally there exists another second-order polynomial Q that bounds its parameter blowup, i.e., µ

Y (M ϕ )(n) ≤ Q(µ X (ϕ), n).
We call a realiser F : ⊆ B → B computed by a machine as in Definition 2 a witness for the polytime computability of f . In the case where both spaces come with the standard parameter, a realiser F is a witness for the polytime computability of the function f if and only if it is polytime computable in the usual sense: The second condition from the previous definition turns into the usual time constraint and the third one becomes automatic, as writing the output takes time.

Definition 2 does not guarantee the identity to be polytime computable.

Definition 3. A preparametrised space X = (X, ξ X , µ X ) is called a parametrised space, if the identity function id X : X → X, x → x is polytime computable.
If the parameter is a restriction of the size function, the identity on Baire space is always a witness for the polytime computability of the identity. Definition 3 implicitly connects the parameter to the size function: While for an arbitrary name there need not be any relation between its parameter and its size, another name of the same element whose size is bounded polynomially in its parameter may be found in polytime by applying a witnesses for the polytime of the identity function. The definition thus requires the existence of an efficient normalisation procedure which reduces the size of excessively large names. This connection is in particular important as it guarantees the stability under small changes in the model of computation.

Theorem 4. Let X, Y and Z be parameterised spaces and f : X → Y and g : Y → Z polytime functions. Then the composition g • f : X → Z is also polytime.

A product of parametrised spaces can be constructed in a straightforward way.

A parametrised space of real numbers

Let diam denote the diameter of an interval and lb the binary logarithm function. Recall the interval representation ξ Ri of the real numbers from Definition 1. For a ξ Ri -name (I n ) n∈N of x ∈ R, define the parameter µ Ri by

µ Ri ((I n ) n∈N )(n) := min{N | diam(I N ) ≤ 2 -n } + lb(|x| + 1) .
This parameter mainly encodes the rate of convergence of the sequence of intervals and we call the triple R i = (R, ξ Ri , µ Ri ) the parametrised space of interval reals. Small parameter blowup for a realiser of a function f : R i → R i means that the rate of convergence of the output sequence is similar to that of the input sequence.

D I C E 2 0 1 8 XX:4

Parameterised second-order complexity Lemma 5 (R i R c ). The reals with Cauchy representation and standard parameter and the space of interval reals are polytime isomorphic as parametrised spaces.

The following is a property that distinguishes R i from the Cauchy reals and is therefore not preserved under isomorphism. Theorem 6. Whenever f : R i → R i is polytime computable, then f can be computed by an oracle machine M ? such that there eixsts a C ∈ N and a second-order polynomial P satisfying time

M ? (ϕ, a) ≤ C • |a| + C and µ i (M ϕ )(n) ≤ P (µ X (ϕ), n).
The proof uses a construction that was invented to show that the interval representation, when equipped with the restriction of the size function, is complexity theoretically ill-behaved [START_REF] Schröder | Spaces allowing type-2 complexity theory revisited[END_REF][START_REF] Kawamura | Function spaces for second-order polynomial time[END_REF][START_REF] Steinberg | Computational Complexity Theory for Advanced Function Spaces in Analysis[END_REF]. In contrast to the size, the parameter contains meaningful information about a name. Thus, the construction that used to remove computational cost with respect to the size, now trades time needed to produce approximations against convergence behaviour. This eliminates the use of higher-order bounds in the time constraint while maintaining a reasonable convergence behaviour.

A parametrised space of continuous functions

Let I = [0, 1] denote the closed unit interval. Define the interval function representation ξ if as follows: ψ : ID → ID is a name of f ∈ C(I) if for any monotone sequence of intervals J n that intersects to a singleton set {x}, the sequence ψ(J n ) is monotone and intersects to {f (x)}. That is, if the operator (J n ) n∈N → (ψ(J n )) n∈N is a realiser of f with respect to the interval representation. Let µ if be defined by

µ if (ψ)(n) := min N ∈ N | ∀J ∈ ID : diam(J) ≤ 2 -N ⇒ diam(ψ(J)) ≤ 2 -n + lb( ξ if (ψ) ∞ + 1)
. That is: the parameter is an appropriate bound on the modulus of continuity and the supremum norm of the encoded function. We call the space C(I) i = (C(I), ξ if , µ if ) the parametrised space of interval functions.

Lemma 7. Evaluation as function from C(I) i × I to R i is polytime computable.

The parametrised representation (ξ if , µ if ) is the "correct" representation for C(I), viewed as a function space, as it contains the least amount of information among those representations which render evaluation polytime computable.

Theorem 8 (Minimality). A parametrised representation (ξ, µ) of C(I) renders evaluation polytime computable if and only if it is polytime translatable to

(ξ if , µ if ).
Theorem 9. Arithmetic operations and composition are polytime on C(I) i .

Comparison to Kawamura and Cook

The most used and best developed framework for complexity considerations in computable analysis is the framework of Kawamura and Cook. This framework is based on secondorder complexity theory as presented in the first section. Kawamura and Cook add the assumption of length-monotonicity. We call a parametrised space with a length-monotone representation and the standard parameter a Kawamura-Cook space. These spaces can also be characterised as follows:

Theorem 10. A parametrised space is polytime isomorphic to a Kawamura-Cook space if and only if it is polytime isomorphic to a space whose parameter is polytime.

Within their framework, Kawamura and Cook have introduced the a representation δ of C(I). Kawamura and Cook have proven this representation to be minimal with the property that evaluation is possible in polytime within the class of Kawamura-Cook spaces. This representation is currently the standard representation for complexity theoretical considerations about continuous functions for this reason. The reason for the non-existence of a backwards translation is that computing a modulus of continuity takes exponential time with respect to the interval representation. From the minimality of the Kawamura-Cook representation it follows that the space of interval functions not isomorphic to any Kawamura-Cook space.

Future work

All of [START_REF] Kawamura | Function spaces for second-order polynomial time[END_REF], [START_REF] Schröder | Spaces allowing type-2 complexity theory revisited[END_REF] and [START_REF] Steinberg | Computational Complexity Theory for Advanced Function Spaces in Analysis[END_REF] use constructions that produce representation with highly pathological properties. For parametrised spaces these constructions can be adjusted and turn into useful tools. Theorem 6 is a special case of this and a detailed description of the general case will be part of future work. Recently there has been some interest in exponentiable objects in the category of represented spaces and polytime functions [START_REF] Kawamura | Function spaces for second-order polynomial time[END_REF][START_REF] Férée | Higher order complexity in analysis[END_REF]. We hope that the study of parametrised spaces can shed some light on this, as these seem to allow for more natural exponential constructions.

Theorem 11 .

 11 The representation δ can be translated to interval function representation in polynomial time. No polytime translation in the other direction exists.

 [START_REF] Benvenuti | Reachability computation for hybrid systems with Ariadne[END_REF]This author was partially funded by the ANR project FastRelax(ANR-14-CE25-0018-01) of the French National Agency for Research.

© Eike Neumann and Florian Steinberg; licensed under Creative Commons


Christine Gassner
email: gassnerc@uni-greifswald.de

Arno Pauly
email: a.m.pauly@swansea.ac.uk

Florian Steinberg
email: florian.steinberg@inria.fr

Christine Gaßner

Comparing integrability and measurability in different models of computation

Computable analysis uses representations to encode elements of abstract mathematical structures by objects that can be operated on by digital computers [START_REF] Weihrauch | Computable analysis[END_REF][START_REF] Pour-El | Computability in analysis and physics[END_REF]. For many spaces that are of importance in applications, canonical representations are available. These representations are usually justified by minimality results. Often, spaces can be viewed from several perspectives and thus different representations are eligible. For instance, the space of continuous functions on the unit interval can either be viewed as a function space and equipped with the minimal representation such that evaluation is computable, or as a metric space with respect to the supremum norm and equipped with an appropriate Cauchy representation. In this example, the computability structures coincide, which can be interpreted as a stability result for the computability structure on the continuous functions. In other cases, where the spaces already differ topologically, it can not be expected that the computability structures coincide and one may ask for the degree of incomputability of the translations [START_REF] Pauly | Comparing Representations for Function Spaces in Computable Analysis[END_REF].

We start by comparing the natural computability structure on the space of continuous functions to the structure it inherits from the space of integrable functions as a subspace. While the inclusion mapping, and with it the translation from a continuous to an integrable function, is computable, recovering a continuous function from its description as integrable function is not computable. We prove that this task is exactly as difficult as computing the limit operator. The difficulty of computational tasks is compared by means of Weihrauch reductions and the limit operator is the operator that assigns to a converging sequence in Baire space its limit. Weihrauch reductions are standard for such comparisons in computable analysis and the limit operator is one of the standard objects to gauge incomputability against [START_REF] Brattka | Weihrauch Complexity in Computable Analysis[END_REF].

We go on to investigate the class of Borel functions of lowest non-trivial complexity: The ∆ 0 2 -measurable functions. These functions can be represented as the space C([0, 1], [0, 1] ∇ ) of piecewise continuous functions as shown in [START_REF] Pauly | Non-deterministic Computation and the Jayne Rogers Theorem[END_REF][START_REF] Pauly | Towards Synthetic Descriptive Set Theory: An instantiation with represented spaces[END_REF]. We prove that the assignment of a piece-wise continuous function to the corresponding integrable function is again Weihrauch equivalent to the limit operator. As integrable functions are identified when they coincide almost everywhere, this assignment is not an inclusion and the result does not allow a direct interpretation as comparison of two representations of the same space.

The techniques employed in proving the above statements can be adapted to address the effective relationship between measurability and integrability and draw connections between computable analysis and more algebraic modes of computation [START_REF] Blum | On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines[END_REF]. To illustrate this, we compare semidecidable sets in the BSS-model with the semidecidable subsets of R in computable analysis.

Computable analysis makes the open subsets of the reals a represented space O(R) by coding them as countable unions of rational intervals. The semidecidable sets are exactly the sets that are effectively open, i.e. of the form n∈N (a n , b n ), where (a n ) n∈N and (b n ) n∈N are computable sequences of rationals. In the BSS-model, the semidecidable sets are the semialgebraic sets S R , Computing measures as a primitive operation i.e. countable unions of sets defined via polynomial equalities and inequalities. It is know that effectively open sets are BSS-semidecidable [START_REF] Zhong | Recursively enumerable subsets of R q in two computing models[END_REF]. We make this result uniform and prove that the inclusion mapping from O(R) to S R is computable. To do so, we code a BSS-semidecidable set by providing the code of a BSS-machine that semidecides it together with the constants of the machine given as a finite tuple of real numbers in the standard representation from computable analysis. We also prove that taking the interior as an operation from BSS-semidecidable sets to O(R) is Weihrauch equivalent to translating descriptions of subsets of N given as Π 1 1 (N)-sets into descriptions as open sets.