Jean-Charles Faugère
email: jean-charles.faugere@inria.fr

Louise Huot
email: louise.huot@lip6.fr

Antoine Joux
email: antoine.joux@m4x.org

Guénaël Renault
email: guenael.renault@lip6.fr

Vanessa Vitse
email: vanessa.vitse@ujf-grenoble.fr

Symmetrized Summation Polynomials: Using Small Order Torsion Points to Speed up Elliptic Curve Index Calculus

Keywords: ECDLP, elliptic curves, decomposition method, index calculus, Semaev polynomials, multivariate polynomial systems, invariant theory

Decomposition-based index calculus methods are currently efficient only for elliptic curves E defined over non-prime finite fields of very small extension degree n. This corresponds to the fact that the Semaev summation polynomials, which encode the relation search (or "sieving"), grows over-exponentially with n. Actually, even their computation is a first stumbling block and the largest Semaev polynomial ever computed is the 6-th. Following ideas from Faugère, Gaudry, Huot and Renault, our goal is to use the existence of small order torsion points on E to define new summation polynomials whose symmetrized expressions are much more compact and easier to compute. This setting allows to consider smaller factor bases, and the high sparsity of the new summation polynomials provides a very efficient decomposition step. In this paper the focus is on 2-torsion points, as it is the most important case in practice. We obtain records of two kinds: we successfully compute up to the 8-th symmetrized summation polynomial and give new timings for the computation of relations with degree 5 extension fields.

Introduction

In the past decade, the resolution of the discrete logarithm problem (DLP) on elliptic curves defined over extension fields has made important theoretical advances. Besides transfer attacks such as GHS [START_REF] Gaudry | Constructive and destructive facets of Weil descent on elliptic curves[END_REF], a promising approach is the decomposition-based index calculus method pioneered by Gaudry and Diem [START_REF] Gaudry | Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem[END_REF][START_REF] Diem | On the discrete logarithm problem in elliptic curves[END_REF], following ideas from Semaev [START_REF] Semaev | Summation polynomials and the discrete logarithm problem on elliptic curves[END_REF]. As in any index calculus, this method is composed of two main steps: the relation search during which relations between elements of a factor base are collected, and the linear algebra stage during which the discrete logarithms are extracted using sparse matrix techniques. Since this second step is not specific to curve-based DLP, this article mainly focuses on the relation search.

In the standard decomposition method, the relations are obtained by solving, for given points R ∈ E(F q n ) related to the challenge, the equation

R = P 1 + • • • + P n , P i ∈ F (1)
where F ⊂ E(F q n ) is the factor base (this is the so-called point decomposition problem). The resolution of this problem relies critically on the Weil restriction structure of E relative to the extension F q n /F q . In almost all preceding works [START_REF] Gaudry | Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem[END_REF][START_REF] Joux | Elliptic curve discrete logarithm problem over small degree extension fields[END_REF][START_REF] Faugère | Using symmetries in the index calculus for elliptic curves discrete logarithm[END_REF], the usual factor base is defined as F = {P ∈ E(F q n ) : x(P ) ∈ F q }, where x(P ) stands for the abscissa of P , possibly after a change of equation of E. Then (1) translates algebraically using the Semaev polynomial Sem n+1 ∈ F q n [X 1 , . . . , X n+1 ] as Sem n+1 (x 1 , . . . , x n , x(R)) = 0

where the unknowns are x i = x(P i ) ∈ F q . It is worth noticing that the resolution of this equation is the keystone of the relation search step. Thus, computing Semaev polynomials for larger values of n or finding ways to increase the efficiency of this resolution will undoubtedly enhance the practical impact of decomposition attacks and is the main goal of this paper. Equation ( 2) is equivalent through a restriction of scalars to a multivariate polynomial system of n equations and n variables over F q , see [START_REF] Gaudry | Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem[END_REF]. The resolution of many instances of the multivariate polynomial systems arising from (2) (using for example Gröbner bases) is by far the main bottleneck of this index calculus approach. Recently Faugère et al. [START_REF] Faugère | Using symmetries in the index calculus for elliptic curves discrete logarithm[END_REF] have proposed to speed up the relation search using a 2-torsion point T naturally present on elliptic curves in the Edwards or Jacobi models. Their approach is based on the observation that in these models, the translation by T corresponds to a simple symmetry of the curve. This implies that the corresponding multivariate polynomial systems also admit an additional symmetry, allowing an easier resolution.

In this work, this approach is taken a step further as we investigate how to take advantage of the existence of some small order torsion points. To achieve this, we generalize ideas from Diem [START_REF] Diem | On the discrete logarithm problem in elliptic curves[END_REF] who replaces the map x : E → F q n by morphisms ϕ : E → P 1 of degree two. More precisely, we highlight new morphisms ϕ which let us take into account the existence of a torsion point T of small order m. The main idea relies on the construction of morphisms ϕ of degree divisible by m that satisfy the equivariance property ϕ • τ T = f T • ϕ for some homography (i.e. an automorphism of P 1 ) f T ∈ PGL 2 (F q ), where τ T stands for the translation-by-T map P → P + T . A first important practical consequence of this setting is that the corresponding summation polynomials admit an additional invariance property, besides the classical one under any permutation of the variables: this comes from the fact that if (P 1 , . . . , P n ) ∈ F n is a solution to the point decomposition problem [START_REF] Bosma | The Magma algebra system. I. The user language[END_REF], then (P 1 + [k 1 ]T, . . . , P n + [k n ]T ) is also a solution as soon as i k i = 0 [m]. Using invariant theory, it is possible to express the summation polynomials in term of fundamental invariants. This new representation of the summation polynomials makes them very sparse and much easier to compute, and in particular we succeeded in computing new summation polynomials. This sparsity also leads to a significant simplification of the multivariate systems arising from the analog of (2). A second consequence is that the associated factor base F = {P ∈ E : ϕ(P ) ∈ P 1 (F q )} becomes invariant under translations by multiples of T : this allows a division of the size of the factor base by the order m of T , thus speeding up by a factor m 2 the linear algebra step.

We begin in the next section by defining the summation polynomials associated to arbitrary morphisms ϕ : E → P 1 and explaining their use for index calculus. In section 3, we investigate the equivariance property satisfied by ϕ and explain the expected benefit when the small order points are accounted for. Then we focus in Section 4 on the fundamental case of degree 2 morphisms and their equivariance property with respect to translations by order 2 points. We finally give explicit examples of symmetrized summation polynomials and applications to the point decomposition problem on elliptic curves defined over degree 5 extension fields.

Summation polynomials and index calculus

Let E be a given elliptic curve defined over an extension F q n of degree n > 2 of F q , and let ϕ : E → P 1 be a morphism defined over F q n . We recall that in order to perform a decomposition-based index calculus, we consider the factor base F = {P ∈ E : ϕ(P ) ∈ P 1 (F q )} which has approximately q elements, and try to find relations (decompositions) of the form R = P 1 + • • • + P n , P i ∈ F where R is a given point related to the challenge. Alternatively, it is possible to consider other type of relations, for instance of the form R = P 1 + • • • + P n-1 (see [START_REF] Joux | Elliptic curve discrete logarithm problem over small degree extension fields[END_REF]) or of the form P 1 + • • • + P n+2 = O (see [START_REF] Joux | Cover and Decomposition Index Calculus on Elliptic Curves made practical. Application to a seemingly secure curve over F p 6[END_REF]). To do so, we introduce the summation polynomials related to ϕ (which can be seen as a generalization of the one described in [START_REF] Diem | On the discrete logarithm problem in elliptic curves[END_REF]): Definition 1 Let E |K be an elliptic curve defined over a field K and ϕ :

E → P 1 be a non constant morphism. A polynomial S ∈ K[X 1 , . . . , X n ] is called an n-th summation polynomial associated to ϕ if it satisfies S(a 1 , . . . , a n ) = 0 ⇔ ∃P i ∈ E( K), ϕ(P i ) = a i and n i=1 P i = O . ( 3
)
Note that in the following, we will always explicitly identify P 1 (K) with K ∪ {∞}, so that it makes sense to consider ϕ(P ) as an element of K (unless P is a pole of ϕ). Also note that this definition, and in fact a large part of what follows, is actually independent of the index calculus context. A first result is that summation polynomials always exist and are uniquely determined by the considered morphism.

Proposition 2 For a given non-constant morphism ϕ : E → P 1 defined over a field K, the set of polynomials satisfying (3) is of the form {cP k ϕ,n : c ∈ K * , k ∈ N * } where P ϕ,n ∈ K[X 1 , . . . , X n ]. The polynomial P ϕ,n is irreducible, unique up to multiplication by a constant, symmetric when n ≥ 3, and is called the n-th summation polynomial associated to ϕ.

Proof. Let ψ : E n-1 → K n be the rational map such that ψ(P 1 , . . . , P n-1 ) = (ϕ(P 1 ), . . . , ϕ(P n-1 ), ϕ(-P 1 -• • • -P n-1 )). Then clearly ψ(E n-1 ) is irreducible since E n-1 is irreducible, and has dimension n -1 since ϕ is surjective. This classically implies the existence of an irreducible polynomial P ϕ,n , unique up to a multiplicative constant, such that ψ(E n-1 ) = V (P ϕ,n ), and it is easy to check that it satisfies (3).

To prove that P ϕ,n is symmetric, we consider the morphism c from the group of permutations of n elements S n to K * , such that c(σ) is the constant satisfying P σ ϕ,n (X 1 , . . . , X n ) = c(σ)P ϕ,n (X 1 , . . . , X n ). This morphism is well-defined since P σ ϕ,n (X 1 , . . . , X n ) = P ϕ,n (X σ(1) , . . . , X σ(n) ) is clearly an irreducible solution of (3). It is well-known that the only morphisms from S n to a commutative group are the identity map or the signature map; this means that P ϕ,n is symmetric or alternating. But this last case is incompatible with (3) as soon as n ≥ 3: indeed, let a, a 3 . . . , a n-1 ∈ K and B = {P 1 + • • • + P n-1 : ϕ(P 1 ) = ϕ(P 2 ) = a, ϕ(P i ) = a i for i ≥ 3}. This set is obviously finite, of cardinality bounded by deg(ϕ) n-1 . However if P ϕ,n is alternating, then P ϕ,n (a, a, a 3 , . . . , a n-1 , a n ) is always zero, and (3) implies that for all a n ∈ K, there exist P ∈ B and P n ∈ E( K) such that ϕ(P n ) = a n and P + P n = O; thus B is infinite, which is a contradiction.

It is always possible to compute summation polynomials inductively as it is done for the classical Semaev polynomials by using resultants. For ϕ(P ) = x(P ) (in a Weierstrass model) we recover of course the polynomials introduced by Semaev [START_REF] Semaev | Summation polynomials and the discrete logarithm problem on elliptic curves[END_REF]. Heuristically, it is possible to estimate the degree of P ϕ,n in each variable (which is clearly the same for all variables by symmetry). Let (a 1 , . . . , a n-1 ) ∈ Kn-1 . The set of solutions of P ϕ,n (a 1 , . . . , a n-1 , X n ) = 0 can be obtained as in the following diagram, by considering the preimage A of {(a 1 , . . . , a n-1 )} by ϕ n-1 and taking its image by ϕ • (-).

{(P1, . . . , Pn-1) ∈ E( K) n-1 : ϕ(Pi) = ai} {-(P1 + • • • + Pn-1) : ϕ(Pi) = ai} {an : Pϕ,n(a1, . . . , an-1, an) = 0} {(a1, . . . , an-1)} - ϕ ϕ × • • • × ϕ
If ϕ is separable, then for most (n -1)-tuples (a 1 , . . . , a n-1 ), the cardinality of A = {(P 1 , . . . , P n-1 ) ∈ E( K) n-1 : ϕ(P i ) = a i } is (deg ϕ) n-1 . The map -: E n-1 → E is of course not injective, but heuristically, if ϕ is a morphism with no special property, the restriction ofto A should be injective in general and the same holds for ϕ restricted to -(A). For a random map ϕ, the expected degree of P ϕ,n in each variable should be (deg ϕ) n-1 . This is in any case an upper bound on the degree of P ϕ,n . In the applications we need to be able to solve (4) easily, and so we want the degree of P ϕ,n to be rather small; therefore most of this article focuses on the case where deg ϕ = 2.

We detail two important cases where the degree is actually smaller than the bound given above.

1. The first case is when ϕ(P ) = ϕ(-P ) and occurs in particular for Semaev polynomials (i.e. when ϕ(P ) = x(P )). Then it is clear that (P 1 , . . . , P n-1 ) ∈ A if and only if (-P 1 , . . . ,

-P n-1 ) ∈ A, thus -(A) is stable under [-1] ∈ End(E) and ϕ |-(A) is 2-to-1.
An upper bound on the degree P ϕ,n is then (deg ϕ n-1 )/2. 2. The second case is when ϕ factors through an isogeny ψ : E → E , i.e. ϕ = ϕ • ψ where ϕ : E → P 1 . Then it is easy to check that P ϕ,n = P ϕ ,n , and an upper bound on the degree is given by (deg ϕ ) n-1 . In this second case, it is actually equivalent to perform the decomposition attack on E using ϕ or on E using ϕ . For this reason, we will usually only consider morphisms that do not factor through an isogeny.

For index calculus purposes, in order to compute a decomposition R = P 1 + • • • + P n , P i ∈ F, we use the (n + 1)-th summation polynomial P ϕ,n+1 associated to ϕ and try to find a solution (a 1 , . . . , a n ) ∈ (F q ) n of the equation

P ϕ,n+1 (a 1 , . . . , a n , ϕ(-R)) = 0 . (4)
We then look for points P 1 , . . . , P n ∈ E(F q n ) such that ϕ(P i ) = a i and

P 1 + • • • + P n = R.
To solve the equation ( 4), we take the scalar restriction with respect to a linear basis of the extension F q n /F q , leading to a multivariate polynomial system defined over F q .

3 Action of torsion points

Equivariant morphisms

We investigate in this section how the existence of a rational m-torsion point on an elliptic curve E can speed up the decomposition attack. Let T ∈ E[m]; as mentioned in the introduction, our goal is to construct equivariant morphisms ϕ : E → P 1 , i.e. such that there exists f T ∈ Aut(P 1 ) satisfying ϕ(P

+ T ) = f T (ϕ(P )) for all P ∈ E: ϕ • τ T = f T • ϕ. Let d be the order of f T ; clearly d divides m. If d is strictly smaller than m, then ϕ • τ [d]T = f •d T • ϕ = ϕ.
This implies that ϕ can be factorized through the quotient isogeny π :

E → E/ [d]T as ϕ = ϕ • π.
In particular, the relation search on E using ϕ and T is equivalent to the relation search on

E = E/ [d]T using ϕ and π(T ) ∈ E [d],
which does not fully exploit the property of T being a m-torsion point. This condition that the homography f T has order m implies some restriction about the degree of ϕ.

Proposition 3 Let T ∈ E[m] be a m-torsion point and f T ∈ Aut(P 1 ) a homography of order m. Suppose there exists ϕ :

E → P 1 such that ϕ • τ T = f T • ϕ.
Then m divides the degree of ϕ.

Proof. Let us denote e ψ (P ) the ramification index of a curve morphism ψ : C 1 → C 2 at a point P ∈ C 1 . Then for any point P ∈ E, we have e ϕ•τ T (P ) = e τ T (P ) • e ϕ (τ T (P )) = e ϕ (P +T ) and e ϕ•τ T (P ) = e f T •ϕ (P ) = e ϕ (P )•e f T (ϕ(P )) = e ϕ (P ) since f T and τ T are isomorphisms. In particular ϕ has the same ramification index at P and its translates P + T, . . . , P + [m -1]T . We consider now a fixed point z ∈ P 1 of f T (which always exists in an extension of K). Then ϕ -1 ({z}) is stable under translation by T , so that for each point P in ϕ -1 ({z}), its m translates P, P + T, . . . , P + [m -1]T also belong to ϕ -1 ({z}) and have the same ramification index. Since deg(ϕ) = P ∈ϕ -1 (z) e ϕ (P ), the degree of ϕ is necessarily a multiple of m.

More generally, if E(K) has a subgroup G of small order, we would like to find an equivariant morphism ϕ : E → P 1 such that for any T ∈ G, there exists

f T ∈ Aut(P 1 (K)) PGL 2 (K) such that ϕ • τ T = f T • ϕ.
Then the map χ : T → f T is a group morphism from G to PGL 2 (K) that we want to be injective by the above remark (since otherwise ϕ would factorize through E/ker(χ)). Unfortunately the set of possible subgroups relevant for our purpose is very restricted.

Proposition 4 Let G be a finite subgroup of E(K) and χ : G → PGL 2 (K) an injective group morphism. Then G is of one of the following forms:

1.

G = E[2], 2. G = T where T ∈ E[m] with m coprime to char(K), 3. G = E[char(K)].
Proof. Since χ is injective, the commutative group G is isomorphic to a subgroup of PGL 2 (K). It follows from the list in [START_REF] Serre | Propriétés galoisiennes des points d'ordre fini des courbes elliptiques[END_REF] that the only finite commutative subgroups of PGL 2 (K) of order prime to the characteristic are either cyclic or isomorphic to Z/2Z × Z/2Z; furthermore, it is easy to see that PGL 2 (K) has no element whose order is a strict multiple of the characteristic. Thus the only subgroups of E(K) that are of interest for our construction are either E [START_REF] Diem | On the discrete logarithm problem in elliptic curves[END_REF] or cyclic, generated by a point of order char(K) or prime to char(K).

In what follows, we only deal with the case where the homography f T has order exactly m. Besides small torsion points, we would also like to take into account the automorphisms of the curve E; for most curves this only means the involution [-1] : P → -P . The group of permutations of E generated by the translation by T and [-1] is isomorphic to the dihedral group D m = Z/mZ Z/2Z, so an equivariant morphism ϕ (if it exists) would give rise to an action on P 1 , i.e. a group morphism from D m to PGL 2 (K). As noted above, this map should be injective when restricted to the subgroup Z/mZ generated by τ T , since otherwise ϕ can be factorized through an isogeny. For m > 2, it is an easy exercise to show that such a group morphism is necessarily injective; in contrast, for m = 2 it is possible to impose the additional property ϕ(-P ) = ϕ(P ) for all P ∈ E. Note that in the finite field case, PGL 2 (F q ) has a subgroup isomorphic to D m if and only if m|(q -1) or m|(q + 1) or m = char(F q ) when m > 2.

Reducing the factor base

We consider an elliptic curve E defined over F q n with an m-torsion point T and denote by ∼ the equivalence relation given by P ∼ P if and only if P -P ∈ T . Assume that there exists an equivariant morphism ϕ : E → P 1 (F q n ) such that the associated homography f T is in PGL 2 (F q ). Then the associated choice of factor base F = {P ∈ E(F q n ) : ϕ(P ) ∈ P 1 (F q )} is invariant with respect to the translation by T , i.e. if P ∼ P and P ∈ F then P ∈ F. Therefore, it is possible to divide the size of the factor base by m, by considering a reduced factor base F that includes only one element for each equivalence class of elements of F.

This modifies slightly the relation search. Each decomposition

R = P 1 + • • • + P n , P i ∈ F can be rewritten as R = (Q 1 + [k 1 ]T ) + • • • + (Q n + [k n ]T ) with 0 ≤ k i < m and where Q i ∈ F satisfies Q i ∼ P i . We then just store the essentially equivalent relation [m]R = [m]Q 1 + • • • + [m]Q n .
The important fact is that subsequently we only need about #F/m relations to compute the discrete logarithms, and that the dimension of the relation matrix used in the resulting linear algebra step is also divided by m providing a speed-up by a factor m 2 . On the other hand, this decreases the probability that a random point R decomposes by a factor m n-1 (there are more tuples in each preimage of the map F n → E, (P 1 , . . . , P n ) → i P i , so there are less points in the image), but this is more than compensated by the improved resolution of the associated polynomial systems as explained below.

Of course, if ϕ is also equivariant with respect to the automorphism [-1] then it is possible to further reduce the factor base by 2. If m = 2 and E has full 2-torsion it is often possible to construct a morphism ϕ equivariant with respect to [-1] and translations by any 2-torsion points, thus allowing a division by 8 of the size of the factor base.

Symmetries of summation polynomials

We have seen in Prop.2 that the summation polynomials are always symmetric for n ≥ 3. In particular, they can be expressed in terms of elementary symmetric polynomials e 1 , . . . , e n in the variables X 1 , . . . , X n . This allows a reduction of the size and the total degree of the summation polynomials, thus simplifying their computation (for instance, it is possible to compute resultants of already partially symmetrized polynomials as was done in [START_REF] Joux | Elliptic curve discrete logarithm problem over small degree extension fields[END_REF]). More importantly, this reduction has an impact on the resolution of the multivariate polynomial systems: instead of solving (4), we rather consider the (partially) symmetrized equation P ϕ,n+1 (e 1 , . . . , e n , ϕ(-R)) = 0, e 1 , . . . , e n ∈ F q . Of course, this adds a simple desymmetrization step in order to recover the corresponding solutions of (4) whenever they exist.

This approach can be extended when ϕ is equivariant with respect to translation by an m-torsion point T . Let (a 1 , . . . , a n ) be a solution of P ϕ,n (a 1 , . . . , a n ) = 0, so that there exist points P 1 , . . . , P n ∈ E( K) such that ϕ(P i ) = a i and P i = O. Then for any k 1 , . . . , k n such that m| k i , we have

(P i + [k i ]T ) = O. Thus P ϕ,n (f k1 T (a 1 ), . . . , f kn T (a n )) = 0. In particular P ϕ,n (f k1 T (X 1 ), . . . , f kn T (X n ))
is also a solution of (3), except that it is a rational function instead of a polynomial if f T is not an affine homography. We will see that P ϕ,n , or an associated rational fraction Q ϕ,n , is actually often invariant under this transformation; more formally, and taking into account Prop.2, it is invariant under an action of the group G = (Z/mZ) n-1 S n . Then P ϕ,n , resp. Q ϕ,n , belongs to the invariant ring K[X 1 , . . . , X n ] G or the invariant field K(X 1 , . . . , X n ) G . In particular, it can be expressed in terms of generators of the invariant ring or field allowing a further reduction of the size and the total degree of the systems; this will be detailed in the next section for m = 2. For index calculus purpose when K = F q n , it is necessary that these invariant generators lie in F q (X 1 , . . . , X n ). This means that the action of G restricts to an action on F q (X 1 , . . . , X n ).

Summation polynomials associated to degree two morphisms

We consider the simplest case where ϕ has degree 2 (note that in this case ϕ is necessarily separable).

Proposition 5 Let E be an elliptic curve defined over a field K with Weierstrass coordinate functions x, y such that [K(E) : K(x)] = 2, and let ϕ : E → P 1 be a morphism of degree 2. Then there exist an homography h ∈ PGL 2 ( K) and a point

Q ∈ E( K) such that ϕ = h • x • τ -Q , i.e. ϕ(P ) = h(x(P -Q)).
Proof. Let R be the set of ramification points of ϕ, that is the set of points P ∈ E such that the ramification index e ϕ (P ) is strictly greater than 1. We easily deduce from the Hurwitz formula that the set R is non empty. For a given ramification point Q ∈ E, we consider an homography ψ ∈ Aut(P 1 ) sending the point ϕ(Q) to the point at infinity

[1 : 0] of P 1 . Let τ Q : E → E denote the translation by Q, then the morphism ϕ = ψ • ϕ • τ Q is ramified at O = [0 : 1 : 0].
In particular, since ϕ has degree 2, ϕ has a unique pole at O of order 2, so that there exist a, b ∈ K such that ϕ = ax + b. This shows that there exists an homography h ∈ Aut(P 1 ) such that ϕ(P ) = h(x(P -Q)).

To compute the associated summation polynomial, it is easy to check that the numerator of the rational fraction Sem n+1 (h

-1 (X 1 ), . . . , h -1 (X n ), x([n]Q))
where Sem n+1 stands for (n+1)-th Semaev polynomial, satisfies the property (3). In the case where Q = O or more generally Q ∈ E[n], the above expression can be simplified by considering the numerator of Sem n (h -1 (X 1 ), . . . , h -1 (X n )). The degree of P ϕ,n in each variable is then equal to 2 n-1 if Q / ∈ E[n] and 2 n-2 otherwise. For index calculus, it is clear that ϕ should be of the form h • x: not only is the degree of P ϕ smaller, but we also have ∀P ∈ E, ϕ(-P ) = ϕ(P ). As mentioned above, this allows to reduce by a further 2 the size of the factor base.

Speeding up the relation search using one 2-torsion point

It turns out that every degree 2 morphism satisfies an equivariance property with respect to 2-torsion points; this is specific to the degree 2 case.

Lemma 6 Let E be an elliptic curve defined over K with a 2-torsion point T , and let ϕ : E → P 1 be a morphism of degree 2. Then there exists f T ∈ PGL 2 (K) such that ϕ(P + T ) = f T (ϕ(P )) for all P ∈ E.

Proof. In the special case of ϕ = x where x is a Weierstrass coordinate function such that [K(E) : K(x)] = 2, the existence is given directly by the addition formula on E. Let g T ∈ PGL 2 (K) be this homography such that x(P + T ) = g T (x(P )) for all P ∈ E. For a more general morphism ϕ

= h • x • τ -Q , the homography f T = h • g T • h -1 satisfies the property.
In the remainder of this section, we denote by T a rational 2-torsion point, ϕ : E → P 1 a degree 2 rational map such that ϕ(P ) = ϕ(-P ), and f T the involution of P 1 such that ϕ(P + T ) = f T (ϕ(P )) for all P ∈ E.

Let W = {(P 1 , . . . , P n ) :

P i = O} ⊂ E n .
This sub-variety has many symmetries besides the action of the symmetric group. As mentioned above, we consider the group G 2 = (Z/2Z) n-1 S n , (called dihedral Coxeter group in [START_REF] Faugère | Using symmetries in the index calculus for elliptic curves discrete logarithm[END_REF]). It is an abstract reflexion group, corresponding to the Coxeter diagram D n , and its elements will be denoted by (( 1 , . . . , n ), σ) ∈ {0; 1} n × S n where 1 + • • • + n = 0 mod 2 (i.e. we explicitly identify G 2 with a subgroup of the group (Z/2Z) n S n of isometries of the hypercube). The group G 2 acts on E n by (( 1 , . . . , n ), σ)

• (P 1 , . . . , P n ) = ([ 1 ]T + P σ(1) , . . . , [ n ]T + P σ(n) ) and leaves W globally invariant.
The image of W by ϕ n is V = V (P ϕ,n ) ⊂ (P 1 ) n , the set of zeroes of the summation polynomial associated to ϕ. This set is also left globally invariant by the rational action of G 2 on (P 1 ) n given by (( 1 , . . . , n ), σ) • (a 1 , . . . , a n ) = (f 1 T (a σ(1) ), . . . , f n T (a σ(n) )). This means that for any g ∈ G 2 , P g ϕ,n (X 1 , . . . , X n ) = P ϕ,n (f 1 T (X σ(1) ), . . . , f n T (X σ(n) )) is still a solution of (3), except that it is a rational fraction and no longer a polynomial unless f T is affine. In particular, the summation polynomials associated to ϕ have additional symmetries, that are simple to handle only when f T is affine, i.e. when we stay within the framework of polynomials and invariant rings.

Proposition 7 Assume the involution f T ∈ PGL 2 (K) affine. Then for n ≥ 3 the n-th summation polynomial P ϕ,n is invariant under the action of G 2 i.e. for all g = ( , σ) ∈ G 2 , P ϕ,n (X 1 , . . . , X n ) = P ϕ,n (f 1 T (X σ(1) ), . . . , f n T (X σ(n) )). Proof. A special case of this proposition has already been proved in [START_REF] Faugère | Using symmetries in the index calculus for elliptic curves discrete logarithm[END_REF]; for the sake of completeness, we rephrase the demonstration in our more general setting. Since P g ϕ,n is again an irreducible summation polynomial associated to ϕ, there exist c(g) ∈ K * such that P g ϕ,n = c(g)P ϕ,n . This gives us a morphism c :

G 2 = (Z/2Z) n-1 S n → K * and from Prop.2 c(S n ) = 1. Let u = ((1, 1, 0, . . . , 0), e)
where e ∈ S n is the neutral element, and v = (0, (1 2 3)). It is clear that G 2 is generated by u together with S n , so that the image of c is completely determined by the value of u. Since u 2 = 1, we have c(u) = ±1. Now an easy computation shows that (uv

) 3 = 1, so 1 = c(uv) 3 = c(u) 3 c(v) 3 = c(u) 3 = c(u).
This means that P ϕ,n ∈ K[X 1 , . . . , X n ] G2 , the ring of invariants of G 2 . Since the action of G 2 is generated by pseudo-reflections, the Chevalley-Shephard-Todd theorem states that K[X 1 , . . . , X n ] G2 is itself a polynomial ring when the characteristic of K is greater than n; we will show later that it is in fact true in any characteristic. But first, we give a condition on E and T to assure the existence of a degree 2 morphism ϕ such that the corresponding homography f T is affine. Moreover when this condition is satisfied, we can take without loss of generality f T equal to x → -x in odd characteristic or x → x + 1 in characteristic 2.

Proposition 8 Let E be an elliptic curve defined over a field K. (i) If char(K) = 2, then there exist T ∈ E(K) [START_REF] Diem | On the discrete logarithm problem in elliptic curves[END_REF] and ϕ : E → P 1 a degree 2 morphism such that ϕ(P + T ) = -ϕ(P ) and ϕ(-P ) = ϕ(P ) if and only if there exist T ∈ E [START_REF] Faugère | Using symmetries in the index calculus for elliptic curves discrete logarithm[END_REF] such that x(T ) ∈ K. In this case T = [START_REF] Diem | On the discrete logarithm problem in elliptic curves[END_REF]T and the curve E has an equation of the form y 2 = x 3 + ax 2 + bx where T = (0, 0) and b is a square in K; moreover, ϕ is of the form If char(K) = 2 and j(E) = 0, there is no non-trivial 2-torsion point.

Proof. (i) Suppose there exists a 2-torsion point T ∈ E(K) [START_REF] Diem | On the discrete logarithm problem in elliptic curves[END_REF], then up to a translation we can assume that T = (0, 0) and that E has an equation of the form y 2 = x 3 + ax 2 + bx. From the addition formula, we get x(P + T ) = g T (x(P )) = b/x(P ). Let ϕ be a degree 2 morphism such that ϕ(-P ) = ϕ(P ). From Prop.5, there exists h ∈ PGL 2 (K) such that ϕ = h • x, and ϕ(P + T ) = f T (ϕ(P )) where f T = h • g T • h -1 . Thus we are looking for an homography h ∈ PGL 2 (K) conjugating g T to z → -z. By considering the associated matrices or the set of fixed points, it is easy to see that there exists such an h ∈ PGL 2 (K) if and only if b is a square, and that all such h are of the form h

(x) = λ x- √ b x+ √ b -1 . Now, if b is a square in K, then any of the points T ∈ E( K) of abscissa ± √ b satisfies [2]T = T ,
and are thus in E(K). Reciprocally, if there exists T ∈ E [START_REF] Faugère | Using symmetries in the index calculus for elliptic curves discrete logarithm[END_REF] such that x(T ) ∈ K, then [START_REF] Diem | On the discrete logarithm problem in elliptic curves[END_REF]T is in E(K) [START_REF] Diem | On the discrete logarithm problem in elliptic curves[END_REF], and up to a translation E has an equation as above with b square in K.

(ii) It is already well-known that in characteristic 2 an elliptic curve has a nontrivial 2-torsion point if and only if j(E) = 0. If E has an equation of the form y 2 + xy = x 3 + ax 2 + b and T = (0, √ b), the addition formula gives x(P + T ) = g T (x(P )) = √ b/x(P ). Now in characteristic 2, there always exists h ∈ PGL 2 (K) that conjugates the homography g T (x) = √ b

x to x → x + 1, and it is easy to see that all such h are of the form x → b 1/4 x+b 1/4 + λ, λ ∈ K.

The first part of Prop.8 generalizes the results given in [START_REF] Faugère | Using symmetries in the index calculus for elliptic curves discrete logarithm[END_REF], where the morphism ϕ is obtained as a projection onto a coordinate for curves in twisted Edwards form. The fact that the morphism ϕ depends of a parameter λ ∈ K is important for index calculus applications, since it allows to define different factor bases depending on the choice of λ.

Remark 9 Lemma 6 shows that every degree 2 morphism satisfies an equivariance property ϕ(P + T ) = f T (ϕ(P )); the above proposition only describes the cases for which f T is as simple as possible. In odd characteristic, about half of the curves with a 2-torsion point have a coefficient b that is a square, and thus satisfies directly the hypotheses of the proposition. However if the curve has full 2-torsion (i.e. a 2 -4b is a square) then it is 2-isogenous to a curve with a rational 4-torsion point, again satisfying the hypotheses. Overall, this proposition applies in odd characteristic to about 3/4 of curves with a 2-torsion point.

Action of the full 2-torsion.

In this subsection, K is a field of characteristic different from 2. Let E be an elliptic curve having a complete rational 2-torsion (in the finite field case, this is equivalent up to a 2-isogeny to the cardinality of E being divisible by 4). Let T 0 , T 1 and T 2 = T 0 + T 1 be the three non-trivial 2-torsion points of E. According to Lem.6, for any degree 2 morphism ϕ, there exist homographic involutions f 0 ,

f 1 and f 2 = f 0 • f 1 such that ∀P ∈ E, ∀i ∈ {0; 1; 2}, ϕ(P + T i ) = f i (ϕ(P )).
In the same way as before, we can consider the action on (P 1 ) n of the reflexion group G 4 = (Z/2Z × Z/2Z) n-1 S n seen as a subgroup of (Z/2Z × Z/2Z) n S n which is given by

(( 1 , . . . , n ), ( 1 , . . . , n ), σ)•(a 1 , . . . , a n ) = (f 1 0 •f 1 1 (a σ(1) ), . . . , f n 0 •f n 1 (a σ(n) )) .
This means that for any g ∈ G 4 , the rational fraction

P g ϕ,n (X 1 , . . . , X n ) = P ϕ,n (f 1 0 • f 1 1 (X σ(1) ), . . . , f n 0 • f n 1 (X σ(n) ))
satisfies again [START_REF] Fgb | A Library for Computing Gröbner Bases[END_REF]. But it is no longer possible that P g ϕ,n is a polynomial for all g ∈ G 4 . Indeed, f 0 , f 1 and f 2 must commute because of the commutativity of the group law on E, but it is easy to check that two distinct affine involutions cannot commute. Thus the best we can hope is that one of the three involutions is affine, without loss of generality equal to z → -z; then the two remaining involutions are necessarily of the form z → c/z and z → -c/z since they all commute. We give below a condition for the best case where c = 1.

Proposition 10 Let E be an elliptic curve in twisted Legendre form

y 2 = cx(x- 1)(x -λ). Let ∆ 0 = λ, ∆ 1 = (1 -λ) and ∆ 2 = -λ(1 -λ).
Then there exists a degree 2 morphism ϕ such that ϕ(-P ) = ϕ(P ) and the associated involutions are {f 0 ;

f 1 ; f 2 } = {z → -z; z → 1 z ; z → -1
z } if and only if there are at least two squares among {∆ 0 ; ∆ 1 ; ∆ 2 }.

Invariant fields and invariant rings

We have seen that when the action of the 2-torsion points is taken into account in the choice of the morphism ϕ, the associated summation polynomial P ϕ,n and rational fraction Q ϕ,n belong respectively to the invariant ring K[X 1 , . . . , X n ] G2 and the invariant field K(X 1 , . . . , X n ) G4 . Hilbert's finiteness theorem implies that the invariant ring K[X 1 , . . . , X n ] G2 is finitely generated, and Galois theory states that K(X 1 , . . . , X n ) G4 is a subfield of K(X 1 , . . . , X n ) with corresponding extension degree |G 4 | = 4 n-1 n!. The goal of this section is to determine generators for these two structures.

We recall that the action of G 2 on K[X 1 , . . . , X n ] and K(X 1 , . . . , X n ) is given by permutations of variables and any even change of signs, while the action of G 4 on K(X 1 , . . . , X n ) also includes taking the inverse of an even number of variables. As already mentioned, the group G 2 is a normal subgroup of G 2 = (Z/2Z) n S n , as is (Z/2Z) n , and the action of G 2 trivially extends to an action on G 2 by allowing any number of sign changes. This means that we have the following diagram of Galois extensions:

K(X 1 , . . . , X n ) K(X 1 , . . . , X n ) (Z/2Z) n K(X 1 , . . . , X n ) G2 K(X 1 , . . . , X n ) G 2 2 n 2 n-1 n! n! 2 It is easy to verify that K(X 1 , . . . , X n ) (Z/2Z) n is equal to K(X 2 1 , . . . , X 2
n ) in odd or zero characteristic and equal to K(X 2 1 +X 1 , . . . , X 2 n +X n ) in characteristic 2, since the latter is clearly invariant and has the correct extension degree. Let

Y i = X 2 i + X i if char(K) = 2 or Y i = X 2 i otherwise. Then K(X 1 , . . . , X n ) G 2 = K(Y 1 , . . . , Y n ) Sn since G 2 /(Z/2Z
) n S n , so this invariant field consists of symmetric rational fractions in the Y i , which is known to be generated by the elementary symmetric polynomials

s 1 = Y 1 + • • • + Y n , . . . , s n = Y 1 • • • Y n . Now let e 1 = X 1 +• • •+X n in characteristic 2 and e n = X 1 • • • X n otherwise;
we have e 2 1 + e 1 = s 1 , resp. e 2 n = s n . Then K(e 1 , s 2 , . . . , s n ), resp. K(s 1 , . . . , s n-1 , e n ), is invariant under G 2 and a degree 2 extension of K(s 1 , . . . , s n ) = K(X 1 , . . . , X n ) G 2 , hence is equal to the invariant field K(X 1 , . . . , X n ) G2 . Finally, since s 1 , . . . , s n and e 1 (resp. e n ) belong to K[X 1 , . . . , X n ], we have the following proposition

Proposition 13 K[X 1 , . . . , X n ] G2 = K[e 1 , s 2 , . . . , s n ] in characteristic 2, K[s 1 , . . . , s n-1 , e n ] otherwise.
We can use the same argument for the action of G 4 on K(X 1 , . . . , X n ), which extends to an action of

G 4 = (Z/2Z × Z/2Z) n S n , by considering the normal subgroups G 4 and (Z/2Z × Z/2Z) n . K(X 1 , . . . , X n ) K(X 1 , . . . , X n ) (Z/2Z×Z/2Z) n K(X 1 , . . . , X n ) G4 K(X 1 , . . . , X n ) G 4 4 n 4 n-1 n! n! 4
The leftmost field K(X 1 , . . . , X n ) (Z/2Z×Z/2Z) n is easily seen to be equal to K(Z 1 , . . . , Z n ) where Z i = X 2 i + X -2 i , and the bottom field K(X 1 , . . . , X n ) G 4 is then generated by the elementary symmetric polynomials

σ 1 = Z 1 + • • • + Z n , . . . , σ n = Z 1 • • • Z n .
Finding generators for the invariant field of G 4 is less obvious. Let s i be the i-th elementary symmetric polynomial in X 2 1 , . . . , X 2 n (with the convention that s 0 = 1),

w 0 = n/2 i=0 s 2n /(X 1 • • • X n ) and w 1 = (n-1)/2 i=1 s 2n+1 /(X 1 • • • X n ).
Then it is only a matter of computation to check that w 0 and w 1 are indeed invariant under the action of G 4 ; actually, replacing an odd number of variables by their inverse exchanges w 0 and w 1 . Moreover, direct computations show that w 0 and w 1 are roots of the polynomial

Z 4 -   n/2 i=0 2 2i σ n-2i   Z 2 +   (n-1)/2 i=0 2 2i σ n-(2i+1)   2 ∈ K(X 1 , . . . , X n ) G 4 [Z]
so they are algebraic of degree 4 over K(X 1 , . . . , X n ) G 4 . This shows the following proposition Proposition 14 K(X 1 , . . . , X n ) G4 = K(σ 1 , . . . , σ n , w 0 ) = K(σ 1 , . . . , σ n , w 1 ) = K(σ 1 , . . . , σ n , w 0 , w 1 ).

These families of generators are of course not algebraically independent. We can in fact choose n generators among them: either removing from the first two families any generator of the form σ n-2i , or removing in the last family any two generators of the σ i 's. From an algorithmic point of view, it is not clear which set of generators is the most efficient for computations of summation polynomials. Then the first summations polynomials associated to ϕ, expressed in term of the generators e 1 , s 2 , . . . , s n of the invariant ring K[X 1 , . . . , X n ] G2 , are equal to

Examples and applications

P ϕ,3 = s 3 + Ls 2 + L 2 (e 2 1 + e 1 ) + L 3 + γ(e 1 + λ) 2 , P ϕ,4 = e 2 1 (s 4 + Ls 3 + L 2 s 2 + L 3 (e 2
1 + e 1 ) + L 4 ) + (s 3 + (e 2 1 + e 1 )L 2 + e 2 1 γ) 2 , where L = λ 2 +λ. The next polynomials become too large to be reproduced with λ and γ as formal parameters, so we give them for λ = 0. Note that it is possible to recover the general expression for a different value of λ by replacing X i by X i +λ, which corresponds to replacing e 1 by e 1 +nλ and s k by k j=0 n-j k-j L k-j s j . For n = 5, we obtain ]. We observe that when λ = 0 or 1, the polynomials P ϕ,3 , P ϕ,4 and P ϕ,5 only involve even exponents of the n -1 first variables. This fact is true in general: for L = 0, P ϕ,n (e 1 , s 1 , . . . , s n ) = Pϕ,n (e 2 1 , s 2 2 , . . . , s 2 n-1 , s n ), which simplifies the inductive computation of these polynomials in characteristic 2.

P ϕ,5 =
We sum up in Table 1 the number of monomials of Semaev polynomials and our symmetrized summation polynomials (for λ = 0), as well as the timings of their computation. For n ≤ 7, we used resultants of partially symmetrized polynomials followed by a symmetrization at each step. The computation was intractable in this way for n = 8. Thus, we implemented a dedicated interpolation algorithm to compute this new record. Here we briefly describe this computation. The 8-th symmetrized polynomial is the result of the symmetrized version of the relation P ϕ,8 (X 1 , . . . , X 8 ) = Res X (P ϕ,6 (X 1 , . . . , X 5 , X), P ϕ,4 (X 6 , . . . , X 8 , X) , but with P ϕ,4 and especially P ϕ,6 already in partially symmetrized form. We thus begin by evaluating P ϕ,8 (e 1 , s 2 , . . . , s 8 ) on a very large sample of points, which can be done by computing the above resultant with all variables (except X) instantiated. However, in order to apply fast sparse evaluation-interpolation techniques [START_REF] Zippel | Interpolating polynomials from their values[END_REF], we have to precisely control the instantiations of e 1 , s 2 , . . . , s 8 ; thus we cannot simply evaluate the X i to deduce a sample point, but have to do the converse instead. Moreover, because of the huge size of the sample, each of these evaluations has to be done as efficiently as possible. Actually, since we work with symmetrized polynomials, each instantiation corresponds to the computation of the values of the generators of the invariant ring in X 1 , . . . , X 5 and X 6 , . . . , X 8 respectively, from an instantiation of e 1 , s 2 , . . . , s 8 . Such a computation is not at all straightforward; it can be done by solving a polynomial system but, even by using the most efficient existing implementations, the timings are too slow to obtain P ϕ,8 in a reasonable time. Thus, we investigated new methods to solve this problem and finally reduced it, by using the underlying symmetries, to the almost instantaneous resolution of a univariate polynomial. This efficient resolution is mainly based on a careful study of the factorization of this polynomial and a clever choice of the sample points, which let us avoid half of the most time-consuming steps of the algorithm. The sparse-interpolation step is less tricky but we need also a careful implementation in order to obtain the required efficiency. The complete computation of the 8-th symmetrized summation polynomial was achieved in about 40.5 CPU.hours using Magma [START_REF] Bosma | The Magma algebra system. I. The user language[END_REF], whereas previous attempts using the direct approach were all stopped after at least one month of computations.

Odd characteristic Let E : y 2 = cx(x-1)(x-λ) be an elliptic curve in twisted Legendre form over an odd characteristic field K. As in Prop.10, we assume that λ and 1-λ are squares, so that there exists t ∈ K such that

√ λ = (1-t 2 )/(1+t 2 ) and √ 1 -λ = 2t/(1+t 2
). Let T 0 = (0, 0) and T 1 = (1, 0); then a map ϕ : E → P 1 satisfying ϕ(-P ) = ϕ(P ), ϕ(P + T 0 ) = -ϕ(P ) and ϕ(P + T 1 ) = 1/ϕ(P ) is given by

ϕ(P ) = √ λ + 1 √ 1 -λ x(P ) - √ λ x(P ) + √ λ .
We can compare the summation polynomials P ϕ,n symmetrized with respect to G 2 (corresponding to the action of a single 2-torsion point T 0 ), the associated rational fractions Q ϕ,n symmetrized with respect to G 4 (corresponding to the action of the complete 2-torsion), and the classical Semaev polynomials, expressed with the elementary symmetric polynomials e 1 , . . . , e n in the variables X 1 , . . . , X n . For n = 3 and 4, we have Sem 3 = e 2 2 -4e 1 e 3 + 2e 2 λ -4e 3 (λ + 1) + λ 2 , P ϕ,3 = t 3 e 2 3 + 2(1 -t 4 )e 3 + t 3 s 1 -ts 2 -t , Q ϕ,3 = t 3 w 1 -tw 0 -2t 4 + 2 . P ϕ,4 = t 2 (s 2 1 -2s 1 s 3 -4s 2 e 2 4 + 8s 2 e 4 -4s 2 + s 2 3 + 8e 3 4 -16e 2 4 + 8e 4 ) + 4(t 4 + 1)(s 1 e 2 4 -s 1 e 4 -s 3 e 4 + s 3 ) , Q ϕ,4 = 4(t 4 + 1)σ 1 -4t 2 σ 2 + t 2 w 2 1 -4(t 4 + 1)w 1 + 8t 2 w 0 -32t 2 . Table 2 sums up the number of terms of the computable polynomials for comparison.

5.2 Index calculus on E(F q 5 ) IPSEC Oakley key determination 'Well Know Group' 3 curve An interesting target for the decomposition attack is the IPSEC Oakley key determina-tion 'Well Know Group' 3 curve [START_REF]The Oakley key determination protocol[END_REF] defined over the binary field F 2 155 = F (2 31 ) 5 . Since this is a degree 5 extension field, the decomposition-based index calculus uses a 6-th summation polynomial. The cardinality of the curve is 12 times a prime number; according to Prop.4, we can only consider the action of the 2torsion or the 3-torsion points. With the 2-torsion point and the morphism ϕ of Prop.8 for λ = 0, the reduced factor base has 536 864 344 elements, which as expected is very close to 2 31 /4. Using the corresponding 6-th symmetrized summation polynomial computed above, a test takes 10.28 sec (3.44 sec for the Gröbner basis computation for a well-chosen order and 6.84 sec for the change of order with FGLM [START_REF] Faugère | Efficient computation of zerodimensional Gröbner bases by change of ordering[END_REF]) using FGb [START_REF] Fgb | A Library for Computing Gröbner Bases[END_REF] on a Intel Core i7-4650U CPU at 1.70 GHz. Alternatively, the same computation with Magma V2.18-3 (on an AMD Opteron 6176 SE at 2.3 GHz) takes 995 sec for the Gröbner basis and about 6 hours for the order change1 .

To put this in perspective, we can compare to the only other existing method computing decompositions on this curve, namely the "n -1" approach of [START_REF] Joux | Elliptic curve discrete logarithm problem over small degree extension fields[END_REF]: the computation of only one relation was estimated in [START_REF] Granger | New timings for oracle-assisted SDHP on the IPSEC Oakley 'Well Known Group' 3 curve[END_REF] to take about 37 years on a single core, whereas with our results the expected time to get one relation is 2 4 × 5! × 10.28 sec ≈ 5.5 hr. Even if it is still too slow to seriously threaten the DLP on this IPSEC standard, these experiments show that other non-standard problems like the oracle-assisted static Diffie-Hellman problem [START_REF] Koblitz | Another look at non-standard discrete log and Diffie-Hellman problems[END_REF] are no longer secure on this curve.

Random curve in odd characteristic with full 2-torsion To test the speed-up provided by the presence of the full 2-torsion subgroup, we considered a random curve in Legendre form over the optimal extension field F (2 31 +413) 5 , with a near-prime cardinality and satisfying the condition of Prop.10. Using the 6-th symmetrized summation polynomial as computed above, a decomposition test takes only 6.66 sec (2.82 sec for the Gröbner basis and 3.84 sec for FGLM) using FGb on a 3.47 GHz Intel Xeon X5677 CPU, or about 5 hours (55 min for the GB and 4h25 for FGLM) using Magma. By comparison, in [START_REF] Faugère | Using symmetries in the index calculus for elliptic curves discrete logarithm[END_REF] only one 2-torsion was accounted for (in a twisted Edwards model) and the authors reported a timing of 2 732 sec for one decomposition test. Once again, this shows the total weakness of some non-standard problems on such curves.

Conclusion

The introduction of summation polynomials associated to any morphism ϕ from an elliptic E to P 1 opens new perspectives for the decomposition based index calculus. In particular, we have been able to use equivariant morphisms to take advantage of 2-torsion points in any characteristic. As demonstrated by our examples and timings, the speed-up over the classical approach is far from negligible and allows to seriously threaten more curves. The framework we have developed also applies to higher order torsion points, which will be more detailed in an extended version of this article.

  of the square root of b and λ ∈ K. (ii) If char(K) = 2 and j(E) = 0, then E admits an equation of the form y 2 + xy = x 3 + ax 2 + b with a unique non-trivial 2-torsion point T = (0, √ b). Then the morphisms ϕ such that ϕ(-P ) = ϕ(P ) and ϕ(P + T ) = ϕ(P ) + 1 are of the form b 1/4 x(P ) + b 1/4 + λ, where λ ∈ K.

5. 1

 1 Computation of summation polynomials Characteristic 2 Let E : y 2 + xy = x 3 + ax 2 + b be an elliptic curve defined over a characteristic 2 field and ϕ : P → γ x(P )+γ + λ where γ 4 = b, as in Prop.8.

  10 + e 14 1 s 6 γ 12 + e 16 1 γ 16 , which has 50 terms in F 2 (γ)[e 1 , s 2 , . . . , s 6

	Again, the next polynomials become too large to be reproduced in their entirety;
	for example, we obtain
	P ϕ,6 = s 8 5 + e 2 1 s 6 5 s 6 + s 6 5 s 6 + • • • + e 12 1 s 2 5 γ
	e 8 1 γ 8 + e 6 1 s 5 γ 5 + e 4 1 s 2 4 γ 4 + e 2 1 s 2 3 s 5 γ 3 + s 4 3 γ 4 + e 2 1 s 3 5 γ + s 2 2 s 2 5 γ 2 + s 4 5 + s 3 5 γ .

Table 1 .

 1 Comparison of the number of terms of symmetrized Semaev polynomials and summation polynomials using a 2-torsion point in characteristic 2 (λ = 0). The crosses correspond to computations that stopped unsuccessfully after several weeks.

		n	3 4 5	6	7	8
	Semaev nb of monomials 3 6 39 638 -	-
	polynomials	timings	0 s 0 s 26 s 725 s ×	×
	Pϕ,n	nb of monomials 2 3 9 50 2 247 470 369 timings 0 s 0 s 0 s 1 s 383 s 40.5 h

Table 2 .

 2 Comparison of the number of terms of symmetrized classical Semaev polynomials and summation polynomials in odd characteristic using either a single 2-torsion point or the 2-torsion

	n	3 4 5	6
	Semaev polynomial	5 36 940 -
	Pϕ,n(s1, . . . , sn-1, en) 5 13 182 4125
	Qϕ,n(σ1, . . . , σn-2, w0, w1) 3 6 32 396

The performance gap between Magma and FGb can be partially explained by the non-optimized arithmetic operations of Magma when the field size exceeds

bits. Experiments on smaller fields showed a significantly smaller gap.

This work has been partially supported by the LabExPERSYVAL-Lab(ANR-11-LABX-0025) and the HPAC grant of the French National Research Agency (HPAC ANR-11-BS02-013)

Proof. Let T 0 = (0, 0), T 1 = (1, 0) and T 2 = (λ, 0) be the non-trivial 2-torsion points of E. Then the abscissa of P + T i is equal to g i (x P ), where

To determine if these involutions can be conjugated to z → -z, z → 1 z and z → -1 z , we look at their fixed points. Let Fix i be the set of fixed points of g i for i = 0, 1, 2; then Fix i is non empty if and only ∆ i is a square. As {0; ∞} and {±1} are the set of fixed points of z → -z and z → 1 z respectively, we deduce easily that there must be at least two squares among {∆ 0 ; ∆ 1 ; ∆ 2 }. Reciprocally, if there are two squares among {∆ 0 ; ∆ 1 ; ∆ 2 }, then it is possible to find an homography h ∈ PGL 2 (K) sending the fixed points of the corresponding involutions to {0; ∞} and {±1}, and we can take ϕ(P ) = h(x(P )).

Remark 11

The condition that ∆ i is a square in K is equivalent to the existence of a 4-torsion point T i with a rational x-coordinate such that [START_REF] Diem | On the discrete logarithm problem in elliptic curves[END_REF]

a square so there are exactly one or three squares among {∆ 0 ; ∆ 1 ; ∆ 2 }, and heuristically the latter should occur for about one curve out of four. Similarly if p ≡ 3 [START_REF] Faugère | Using symmetries in the index calculus for elliptic curves discrete logarithm[END_REF] then there are exactly zero or two squares among the ∆ i , the latter occurring heuristically for 3/4 of the curves. Overall about half of the curves in twisted Legendre form will satisfy the hypotheses of the above proposition. For the remaining curves one has to work with degree 2 morphisms whose equivariance property has a less simple expression.

Proposition 12 Suppose that the hypotheses of Prop.10 are satisfied. Then the rational fraction

is invariant under the action of G 4 for n ≥ 3, i.e. for all g = (( ,

Proof. From Prop.7 the polynomial P ϕ,n is invariant under the action of G 2 (identified with the subgroup of G 4 whose elements are of the form ( , 0, σ)), and it is also obviously true for the denominator

. Since G 4 is generated by G 2 and u = (0, (1, 1, 0, . . . , 0), e) (where e ∈ S n is the neutral element), it is sufficient to check that

); in particular, there exists c ∈ K such that P = c • P ϕ,n and consequently

Now the same reasoning as in the proof of Prop.7 shows that c = 1.