Cécile Antoine Joux

Cécile Pierrot

Algorithmic aspects of elliptic bases in finite field discrete logarithm algorithms

Keywords: 2010 Mathematics Subject Classification. 11Y16, 12Y05, 11G20 Discrete logarithms, Finite fields, Elliptic bases

1. Introduction. The discrete logarithm problem (DLP) is a fundamental problem underlying the security of many cryptographic systems. Given G a finite cyclic group denoted multiplicatively and g a generator of the group, solving the discrete logarithm problem in G means being able, for any arbitrary element h ∈ G, to find an integer x such that: g x = h.

Our formulation differs in many details. As such, it might shed a different light on the topic and help the reader to study the theoretical breakthrough on provable algorithms. As of now, our proposal remains slightly inferior to the method in [START_REF] Joux | Improving the polynomial time precomputation of frobenius representation discrete logarithm algorithms -simplified setting for small characteristic finite fields[END_REF], the fastest currently known (heuristic) method to compute discrete logarithms in small characteristic. However, it gets very close, while leaving room for improvement in the analysis.

1.0.1. A tool from Pomerance. To turn an algorithm in the Frobenius representation family into a provable algorithm, it is not only necessary to prove that the finite field representation can be constructed, but it is also required to change the following steps: relation generation and linear algebra. Let h be a random element and g the generator. Essentially, one follows the approach of [START_REF] Pomerance | Fast, rigorous factorization and discrete logarithm algorithms[END_REF], which consists in decomposing plenty of elements of the form g a h b over the factor base, which is a small set of small elements. Linear algebra can then be used to combine plenty of equations which leads to a random identity of the form g A h B = 1. We can then deduce the discrete logarithm of h in base g.

Assuming that the field representation exists, this makes the computation of discrete logarithms provable. For Frobenius representation algorithms, assuming that the field representation is given and deducing a provable algorithm has been studied in [START_REF] Granger | On the discrete logarithm problem in finite fields of fixed characteristic[END_REF][START_REF] Kleinjung | A new perspective on the powers of two descent for discrete logarithms in finite fields[END_REF][START_REF] Göloglu | A simplified approach to rigorous degree 2 elimination in discrete logarithm algorithms[END_REF].

Unfortunately, the full computation has to be restarted from scratch for every discrete logarithm computation in the same field. The aim of this work is to propose a practical algorithm with a representation that can be proven. This algorithm includes an "individual logarithm step" at the end, allowing, for instance, to reuse part of the work done for another discrete logarithm that was previously computed. 1.0.2. Discrete logarithm algorithm with an elliptic representation. Let F p k be the target finite field in which we want to compute discrete logarithms. To simplify exposition, we assume p ≥ 5, since the equation of the curves needs to be chosen differently in characteristic 2 or 3. We summarize our construction as follows:

1. Representation. Create an elliptic curve E over F q (q being a power of p) such that: #(E /F q ) = µk, with µ a natural integer. If k is square, there necessarily exists a k-torsion point P 1 ∈ E . Otherwise, for every prime dividing k, let e be the largest power of dividing k. For each with e > 1, it might be necessary to change E to an isogeneous curve by applying a sequence of -isogenies in order to guarantee that a point of order e exists. These changes to E suffice to guarantee the existence of P 1 .

Finally, find a point F ∈ E such that:

π(F ) = F + P 1 ,
where π is the Frobenius action in the field F q . In particular, if we note F = (θ, τ ) then we can write F q k as F q [θ, τ ]. This almost gives the desired representation of the target field. Indeed, F q [θ] is either F q k or F q k/2 . In the sequel, we assume that F q [θ] = F q k , multiplying k by 2 if necessary.

Then, since F p k is a subfield of both F q k or F q 2k , we see that computing discrete logarithms in F q [θ] is sufficient to achieve the desired goal.

2. Commutative Diagram. We now define the full representation we want to use from a curve C in 3 dimensions obtained as the image of the following rational map:

Φ : E → F 3 q Q → (x Q-P1 , x Q , x Q+P1 )
At first, this might seem to be a strange model of an elliptic curve, with respect to Weierstrass equations, for instance. However, the intuition is that, with this model coming from Semaev polynomials, the image of F is a point with an advantageous property: taking the Frobenius of one of its coordinates leads to the following one. In other words, if Φ(F ) is seen as a point of C in the affine space F q [U, V, W ] then it lies on the intersection of the surfaces defined by the two equations U q = V and V q = W . This property is at the core of our method for creating relations, since it allows us to re-use the core standard technique from the Frobenius representation approach to discrete logarithms. Starting from A and B two polynomials in F q [U, V ], we construct two big polynomials:

A q B -AB q = α∈P1(Fq) (A -αB)
in one hand, and:

A(V, W )B(U, V ) -A(U, V )B(V, W )
in the other hand. Each polynomial can be considered as an element of the function field F q (C ). Writing the divisor associated to each side, we can write down an equality between the image of each divisor in F q k . For polynomial themselves, the image is simply obtained by evaluation at Φ(F ). The equality of the two sides comes from the Frobenius relations between the coordinates of Φ(F ). 3. Relation collection. We sieve on pairs of polynomials (A, B) such that A = g 1 + αg 3 and B = g 1 + βg 2 + γg 3 where α, β, γ ∈ F q and g 1 , g 2 and g 3 are given polynomials constructed by linear combination of the monomials U, V, U V and 1. Set the factor base F as all the divisors of E with height at most 3. On one side α∈P1(Fq) (A -αB) will always lead to divisors that can be written as sum of divisors of F, and on the other side A(V, W )B(U, V )-A(U, V )B(V, W ) have a low enough height so that the probability that the related divisor D splits in factor base elements is high enough to get as many relations we want. Since we only need three degrees of freedom from the four monomials U, V, U V and 1, we choose g 1 , g 2 and g 3 all going through a common point. This nicely reduces the degree of the divisors appearing in the decomposition of the terms A -αB. This is essential in making the probability of success during the relation collection phase good enough. [START_REF] Cohen | Handbook of Elliptic and Hyperelliptic Curve Cryptography[END_REF]. Linear algebra and individual logarithm.

Thanks to the action of Frobenius, we can reduce the size of the factor base by a factor k. In other words, this reduces the effective size of the factor base F to O(q 3 /k). As a consequence, the cost of the sparse linear algebra, with O(q) entries per equation, is of O(q 7 /k 2 ) arithmetic operations. Note that when k is chosen close to q, this matches the O(q 5 ) asymptotic complexity obtained for this step in [START_REF] Joux | Improving the polynomial time precomputation of frobenius representation discrete logarithm algorithms -simplified setting for small characteristic finite fields[END_REF]. 5. Descent Phase. Finally, we need a descent phase to conclude. We give the necessary tools to adapt existing methods in this context.

1.0.3. Outline. Section 2 gives algebraic preliminaries for this work. In this sequel, we focus on the algorithmic aspects and describe our practical elliptic Frobenius algorithm. Being aimed at practicality, this algorithm is heuristic. From a performance analysis point of view, our heuristic approach almost achieves the same efficiency as the best pre-existing practical algorithm for DLP in small characteristic finite fields. Almost, because there is a glitch in the analysis of the fast computation of the extended factor base. However, despite this glitch, we were able to implement and use the elliptic representation approach to compute logarithms of an extended factor base for the finite field F 3 1345 . We highlight the heuristics we use as far as we can, in order to clarify the difference with the provable algorithm of [START_REF] Kleinjung | Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic[END_REF] or [START_REF] Lido | A provably quasi-polynomial algorithm for the discrete logarithm problem in finite fields of small characteristic[END_REF].

In Section 3 we give our variation on the representation of the target finite field while Section 4 details how to get relations. Section 5 deals with factor base extension and with the individual logarithms phase. Finally Section 6 presents (part of) a practical discrete logarithm computation over F 3 1345 .

2.

A Refresher on the Function Field Sieve Machinery.

Notations. Let K = F q denote a finite field. Let C be a non-singular curve in the n-dimensional projective space P n (F q ) defined over K and π denote the Frobenius map on P n (F q ). The set of places of K(C ) is denoted by Σ K(C ) . The group of degree-0 divisors of C is written Div 0 (C ) and the Picard group (or divisor class group) of C is Pic 0 (C ). Everything that is needed in this article about classical objects such as algebraic function fields, divisors, the Picard group is given in Appendix A.

A tool from FFS. Many concepts used here originate from the Function Field Sieve (FFS) algorithm [START_REF] Adleman | Function field sieve method for discrete logarithms over finite fields[END_REF]. The aim of this first section is not to describe FFS itself, but to describes these concepts in a slightly more general form than the original description of Adleman and Huang article. The main tool we need from FFS consists in sending a degree-0 divisor into a finite field.

Let L = F q k be a finite extension of K. Let F be a point of C /L such that the coordinates of F generate L over K. Given an arbitrary element f ∈ K(C ) * which does not have F as a pole, we can evaluate f at F and obtain a value in L. As explained in [START_REF] Adleman | Function field sieve method for discrete logarithms over finite fields[END_REF], this process can be generalized from functions to a large subset of divisors of C . Clearly, since α f and f have the same divisor for any α ∈ K, we need to proceed with care.

First, we define a map Ψ from Princ(C ) to L/K * defined as follows:

Ψ : Princ(C ) → L/K * D → Ψ(D) = f (F ),
where f is an arbitrary function such that div(f ) = D. Since the result is only considered up to multiplication by an arbitrary constant in K * , it is independent of the particular choice of f . To generalize to more divisors, we now consider a degree-0 divisor D together with an integer h ∈ N * such that hD is principal and h is coprime to the order of L * /K * = (q k -1)/(q -1). For such a divisor, we extend the definition by letting:

Ψ(D) = Ψ(hD) 1/h .
In the terminology of [START_REF] Adleman | Function field sieve method for discrete logarithms over finite fields[END_REF], we evaluate at F the "surrogate" function that we have associated to D thanks to the multiplication by h. Note that replacing h by any other h satisfying the conditions does not change the value of Ψ(D). Furthermore, remark that if Ψ is defined on D and D , it is also defined on D+D and Ψ(D+D ) = Ψ(D) • Ψ(D ). Similarly, if Ψ(D) is defined and non-zero, then Ψ(-D) = 1/Ψ(D).

From a computational point of view, if D has a small support, then Ψ(D) can be efficiently computed by using Miller's algorithm to compute the evaluation at F of the function corresponding to hD. See Section 3.3 for more details.

In the Function Field Sieve, this tool is used as part of the commutative diagram that underlies the construction of multiplicative relations. However, it is not used directly in the algorithm, only in its correctness proof. Similar, in our elliptic representation algorithm, the map Ψ is not really necessary to perform computations. However, having it at our disposal gives a very useful tool for checking the correctness of relations, thus helping to remove undesirable implementation bugs.

3. Representation of the Target Finite Field. Let q and k respectively be a prime power and the extension degree of the field. Our aim is to compute discrete logarithms in it. Let's write p its characteristic. Since we want to define the extension as F q [x P ], with x P the abcissa of some point on an elliptic curve, while the construction naturally writes it as F q [x P , y P ], there is a small risk of producing a subextension (missing a last quadratic extension) when k is even. If this happens, it suffices to replace k by 2k during the initial choice of the elliptic basis. As a consequence, we can safely ignore this point in the sequel.

3.1.

Choosing the elliptic basis. The representation step of our algorithm starts by forming an elliptic curve over a small extension of F q with cardinality a multiple of k. The following result explicits bounds with respect to q and k for both the extension degree and the multiplying factor. Theorem 1. If q and k be a prime power and a positive integer, then there exist µ and ν two integers and an elliptic curve over F q µ with cardinality νk such that µ ≤ log(k 2 /4)/ log q + 1.

Proof. Let p denote the characteristic of F q . We can perform following case by case analysis:

1. First, let us assume that k < 2 √ q. Thus there exist at least two multiples νk and (ν + 1)k of k in the Hasse interval q + 1 -2 √ q, q + 1 + 2 √ q . Furthermore, we may assume that νk < q + 1.

If p divides k then p cannot divide the trace t = q + 1 -νk. Let us recall now the following result:

Corollary 1 (of Waterhouse's theorem [24]). For each value of the characteristic p, for any extension degree n and for every integer t in ]-2 √ p n , 2 √ p n [ such that t ≡ 0 mod p, there exists an elliptic curve over F p n whose number of rational point is exactly p n + 1 -t. The reader can for example find a proof in [START_REF] Ughi | On the number of points of elliptic curves over a finite field and a problem of B. Segre[END_REF]. Note that we can run into some cases where the characteristic does divide the trace and yet such that there exists such a curve. Theorem 4 in [START_REF] Ughi | On the number of points of elliptic curves over a finite field and a problem of B. Segre[END_REF] gives the exhaustive list of these special cases. Back to our discussion of the case where p divides k, we see that, Waterhouse's theorem yields the existence of an elliptic curve over F q with cardinality νk.

If p does not divide k then two sub-cases occur. Either q + 1 -νk is not a multiple of p, and Waterhouse's theorem permits to conclude again that there exists an elliptic curve over F q with cardinality νk, or it is. In the second case, p divides q + 1 -νk and doesn't divide k, so p doesn't divide t = q + 1 -νk -k. From Waterhouse's theorem we obtain a curve over F q with cardinality (ν + 1)k.

Either way, when k < 2 √ q we always find a curve over the base field F q .

2. If k ≥ 2 √ q then there is no guarantee of the existence of two multiples of k in the Hasse interval. Thus, unless we are lucky, we need to increase the size of the finite field to get a larger interval. Let µ be the smaller integer such that k < 2 √ q µ . Applying the previous case on this extended field, we see that there always exists an elliptic curve over F q µ with cardinality νk such that νk < q µ + 1 + 2 √ q µ . To conclude, notice that the additional extension degree µ that we need is (at most) equal to the ceiling of log(k 2 /4)/ log q.

Once we have found E , it allows us to define the finite field F q µk , where µ is the extra extension degree needed to find E . To lighten notations, we assume without loss of generality that µ = 1. Indeed, it suffices to redefine a new value for q equal to the previous value q µ . Thanks to the upper bound on the extension degree, we see that it does not affect the quasi-polynomial time complexity of the algorithm.

We further assume that E contains a point P 1 in F q of order k. If necessary, apply low-degree isogenies to the initial curve E until a suitable one is obtained. Then construct a point F whose coordinates in the algebraic closure satisfy:

π(F ) = F + P 1 ,
where π is the q-th power Frobenius action. Write the coordinates of F as (θ, τ ). From [START_REF] Marc | Elliptic periods for finite fields[END_REF], we know that F q k = F q [θ, τ ]. Furthermore, from our assumption on k, we have

F q k = F q [θ].
Note that, when focusing on the practical variation of the algorithm, it is important to have k as large as possible compared to q. The above proof only guarantees that q = O(k 2 ), however, in the best cases we can have q = O(k).

3.2.

Representing the curve with a different model. We introduce here a model that represents elliptic curves in the three-dimensional affine space F q [U, V, W ].

To construct this new model, we start from a curve E together with a k-torsion point P 1 of E /F q . Let (x 1 , y 1 ) ∈ (F q ) 2 denote the coordinates of P 1 and (x , y ) the coordinates of

P = P 1 for ∈ [2, • • • , k -1].

3.2.1.

Adding some structure. The idea is to create a new model of E in which we artificially inject extra desirable properties. Namely, for any point Q ∈ E / Fq , we represent it by the triple of abcissae of the points Q -P 1 , Q and Q + P 1 , on the one hand and -Q, P 1 , Q -P 1 on the other hand. In this model, there is an easy way to add the π(F ) = F + P 1 constraint of the Couveignes and Lercier [START_REF] Marc | Elliptic periods for finite fields[END_REF] construction of elliptic bases. The Frobenius action on a special point called F to be defined later is shown on Figure 1.

Indeed, for point F we see that the triple of coordinates is (x π -1 (F ) , x F , x π(F ) ). Furthermore, for π(F ) the triple is (x F , x π(F ) , x π 2 (F ) ). As a consequence, the first two coordinates can be obtained by a simple shift. Furthermore, it is possible to recover the missing coordinate of π(F ) from the first two, in a way similar to Montgomery's ladder technique.

3.2.2.

Formal definition and equations of C . Now that we have captured our intuition, we give a formal definition of this new curve. We assume for simplicity that E is given by a reduced Weirstrass equation:

E : Y 2 = X 3 + a X + b,
but this can be generalized to include characteristic 2 and 3. With this notation, the third summation polynomial is given by:

S 3 (X 1 , X 2 , X 3 ) = 4σ 1 (σ 3 + b) -(σ 2 -a) 2 ,
where the σ i are the symmetric polynomials

σ 1 = X 1 + X 2 + X 3 , σ 2 = X 1 X 2 + X 1 X 3 + X 2 X 3 and σ 3 = X 1 X 2 X 3 .
By definition of the third Semaev polynomial, for any triple of points

Q 1 = (x Q1 , y Q1 ), Q 2 = (x Q2 , y Q2 ), Q 3 = (x Q3 , y Q3 ) ∈ E ( Fq ) \ {O}, we have: S 3 (x Q1 , x Q2 , x Q3 ) = 0 ⇔ ∃(e 1 , e 2 , e 3 ) ∈ {-1, 1} 3 , e 1 Q 1 + e 2 Q 2 + e 3 Q 3 = O.
We use this polynomial to describe the image C of the rational map:

Φ : E → F 3 q Q → (x Q-P1 , x Q , x Q+P1 )
For every point Q ∈ E / Fq , we use S 3 to rewrite the three simple identities (Q -P 1 )-Q+P 1 = O, Q-(Q+P 1 )+P 1 = O and (Q-P 1 )-(Q+P 1 )+P 2 = O. This shows that the point (x Q-P1 , x Q , x Q+P1 ) is a common root of the polynomials S 3 (U, V, x 1 ), S 3 (V, W, x 1 ), and S 3 (U, W, x 2 ). Let us first consider the variety given by these three equations. To determine its components, let us consider its intersection with the hyperplane U = W . This intersection is described by S 3 (U, V, x 1 ) = 0, U = W and S 3 (U, U, x 2 ) = 0. From Equation S 3 (U, W, x 2 ) that is a degree-4 polynomial in U , we know that U has finitely many values. Thus we want to remove the extraneous points lying in this hyperplane.

We look so at the components in the complement of this hyperplane and assume that U = W . In this case, since S 3 (U, V, x 1 ) -S 3 (V, W, x 1 ) is divisible by U -W we obtain a lower degree polynomial, namely:

S δ = S 3 (U, V, x 1 ) -S 3 (V, W, x 1 ) U -W .
The variety defined thanks to the three equations S 3 (U, V, x 1 ) = 0, S δ = 0 and S 3 (U, W, x 2 ) = 0 is now irreducible. We call it C and prove that it is a genus 1 curve isomorphic to E . To see that, let us give rational maps between E and C .

3.2.3. E and C are isomorphic. Let us consider the rational map:

Φ : E → C Q → (x Q-P1 , x Q , x Q+P1 )
Every point P in E is such that Φ(P ) ∈ C . Besides, the images of the three points O, P 1 and -P 1 are at infinity on C and that, by homogenization, we may check that there are exactly three points at infinity on C .

As usual, Φ induces a map Φ * from the function field F q (C ) to F q (E ) (expressed with the two variables X and Y ) using the following replacement:

Φ * : F q (C ) → F q (E ) U → Y +y1 X-x1 2 -X -x 1 , V → X, W → Y -y1 X-x1 2 -X -x 1 .
where y 1 is the ordinate of the point P 1 in E . Developing and using the curve equation, the images of U and W can be respectively simplified to:

U → x 1 X 2 + (a + x 1 2 ) X + a x 1 + 2 b + 2 y 1 Y (X -x 1 ) 2 , W → x 1 X 2 + (a + x 1 2 ) X + a x 1 + 2 b -2 y 1 Y (X -x 1 ) 2 .
In this form, it is clear that the map can be easily inverted when X = x 1 . Moreover, given a pair (U, V ) values we can compute the value of W and similarly, from (V, W ) we can compute U . When X = x 1 , we have two possibilities Φ(P 1 ) = (∞, x P1 , x P2 ) and Φ(-P 1 ) = (x P2 , x P1 , ∞). These are distinct (unless P 1 has order 2), which means that Φ is a bijection and thus an isomorphism.

E P 1 F F -P 1 F + P 1 π π θ τ Figure 1. Frobenius action on the point F ∈ E /F q k .

3.2.4.

Point in E with coordinates in the target finite field. Let F ∈ E be such that:

π(F ) = F + P 1 .
(1)

Lemma 1. If F ∈ E / Fq is such that π(F ) = F +P 1 then F ∈ E /F q k .
Furthermore, letting (θ, τ ) denote the coordinates of F , we have F q [θ, τ ] = F q k . In particular, there exist at least k rational points verifying the same property.

Proof.

Let us compute π k (F ) = π k-1 (F + P 1 ) = π k-1 (F ) + P 1 = • • • = F + kP 1 .
We know that P 1 has precisely order k hence π k (F ) = F . Besides, we note that any point π i (F )

for i = 1, • • • , k -1 satisfies Equation (1) too.
As already mentioned, having possibly doubled the value of k in construction, we may assume that F q [θ] = F q k . In our model of curve, the point F is determined by the fact that S 3 (θ, θ q , x 1 ) = 0. The abscissa θ of F can thus be determined as a root of this polynomial. Note that the choice of the ordinate τ gives an orientation on the direction of the Frobenius action. We choose the letter F to name this point as a mnemonic to remind that it represents our target Finite Field and that it has a special relationship with the Frobenius map.

F q [U, V ] × F q [U, V ] (A, B) F q [U, V, W ] A q B -A B q = α∈P1(Fq) (A -α B) F q [U, V, W ] A(V, W ) B(U, V ) -A(U, V ) B(V, W ) F q [U, V, W ] /I = F q [C ] F q [C ] = F q [U, V, W ] /I F q (E ) Princ(E ) ⊂ Div 0 (E ) F q (E )
Princ(E ) ⊂ Div 0 (E )

F q k /F * q ι ι Φ * Φ * div div Ψ Ψ
Factor base elements are there.

Commutative diagram.

From the above considerations, we derive the commutative diagram of Figure 2, which serves as the basis for our elliptic Frobenius representation algorithm. Note that the commutative diagram is above F q k /F * q . As a consequence, our algorithm doesn't compute the part of the discrete logarithm corresponding to F * q . However, this field is so small that this missing part can be easily obtained.

Remark 1. The diagram of Figure 2 could be simplified by removing references to the function field F q (E ) and computing divisors on C directly. However, when using standard computer algebra tools, it is much simpler to work on divisors with the Weirstrass equation of E .

3.3.1. Explicit maps to F q k based on Miller algorithm. The first two maps of the diagram are explicit and the two following ones are canonical injections. Φ * is given in Appendix and div is as defined in Section 2. As the composition if frequent we note Ξ = div • Φ * to lighten the ratings. In addition, we let Ψ denote a multiplicative group morphism that sends elements of Princ(E ) to F q k . Yet, only defining Ψ for principal divisors is not sufficient, since in the relation collection phase we need first to factor divisors in Princ(E ) into elementary divisors before descending them into the finite field. Keep in mind that elementary divisors have no reason to be principal.

For any divisor in Princ(E ) the first thing to do is to decompose it into elementary divisors in Div 0 . Then, we note that since we wish to construct a group morphism that sends elements of Div 0 to F q k /F * q , it suffices to describe this morphism for any of these elementary divisors. Let us consider:

D e = d i=1 π i (Q) -d(O),
where Q ∈ E /F q d is one of the conjugate points in the degree-d place. Fix a maximum degree D for the places we consider and let N D be the least common multiple of the cardinalities of E over each finite field

F q d with 1 ≤ d ≤ D.
From this, we see that N D D e is a principal divisor, thus there exists a function f De in the variables X and Y unique up to multiplication by a constant in F q such that div(f De ) = N D D e . We want to use the point F with coordinates in the target finite field to define it. Since θ and τ are respectively the abscissa and the ordinate of this point, it seems natural to send X to θ and Y to τ , or, in other words, to evaluate the function on the point F . However, since f De is only defined modulo a constant in F q , the result in the finite field would change depending on the choice of the function. To annihilate this constant, we have to divide the evaluation on F by the evaluation on O. Hence to have a well-defined application Ψ we set

Ψ(D e ) = (f De (F -O)) 1/N D .
However, evaluation at O isn't really necessary, since we are only interested in values in F q k /F * q . As done for bilinear pairings, this can be efficiently computed using Miller's algorithm [START_REF] Victor | The Weil pairing, and its efficient calculation[END_REF].

3.3.2.

Analysis of the invertibility of N D . In order to raise to the power 1/N D and get a uniquely defined value, we need to check that N D is invertible modulo the order of F * q k /F * q . This condition needs to be tested for all the orders of the curve E in the extension fields F q , F q 2 , • • • , F q D . We provide a replacement for Ψ in the case where N D cannot be inverted.

This analysis requires us to follow standard practice and first decompose our target group F * q k , in order to apply Pohlig-Hellman algorithm [START_REF] Pohlig | An improved algorithm for computing logarithms over GF(p) and its cryptographic significance (corresp.)[END_REF]. Thanks to [START_REF] Pohlig | An improved algorithm for computing logarithms over GF(p) and its cryptographic significance (corresp.)[END_REF] it suffices to compute discrete logarithms in all prime order subgroups of F * q k . An important technicality is that we would need to first factor q k -1. Unfortunately, this would dominate the cost of computation. However, to study the invertibility of N D , we do not need to factor q k -1, the existence of the factorization suffices.

Let γ be a prime factor dividing q k -1, it suffices to check that N D = 0 mod γ, for Ψ to be well-defined in subgroups of order a power of γ in F * q k . Since N D is defined as the least common multiple of the cardinalities of E over each of the finite fields F q d with 1 ≤ d ≤ D, where D ≤ k is the maximum degree of the places we want to consider, this gives us an extra condition on E . Namely, it should satisfy the following property:

• For any i = 1, • • • , D, |E /F q i | = 0 mod γ.
Let us study this condition. We denote by t the trace of E over F q and factor the characteristic polynomial of the Frobenius of E :

X 2 -tX + q = (X -r)(X -s) mod γ
with r and s in F γ 2 . We know that the number of points of E /F q i is equal to (1 -r i )(1 -s i ) mod γ. Thus, to ensure that the cardinalities of E over the field extensions F q i , with ι in [1, D], all differ from 0 modulo γ we just need to verify that both r i = 1 mod γ and s i = 1 mod γ. In order to do that, let us first study the order of the product rs = q mod γ.

By definition of γ, we have q k = 1 mod γ. Furthermore, the order of q is strictly smaller than k modulo γ if and only if γ already divides the order of the multiplicative group of a subfield of F q k . In that case, we compute this part of the logarithm by applying our method to the smallest such subfield.

We now assume that the order of q is precisely k mod γ. Thus, for any ι not a multiple of k, at most one of r i or s i can be equal to 1 mod γ. Exchanging r and s if necessary, we now study the case r i = 1 mod γ. In that case, we have s i = q i = 1 mod γ. This implies that E (F q i ) contains a γ-torsion point Q γ but not the full γ-torsion E [γ]. Thus, the Tate pairing provides a non-degenerate bilinear map to the γ roots of unity:

e i :< Q γ > × E (F q i )/γE (F q i ) → F * q / F * q (q k -1)/γ .
Fixing an arbitrary non-zero element from E (F q i )/γE (F q i ), we obtain a linear map Ψi from the subgroup generated by Q γ to the γ-th roots of unity.

Possibly after renormalization, Ψi gives a compatible replacement for Ψ that can be applied to the γ-torsion point. The renormalization consists in replacing Ψi by Ψi βi , where β i is the renormalization constant. As a consequence, it is mathematically possible to extend Ψ to all divisors. One computational caveat is that determining the value of β i can be expressed as a discrete logarihm problem in the group of order γ. It does not affect the efficiency of the overall algorithm but prevents independent check on relations containing divisors of degree ι not compatible with the definition of Ψ during the precomputation phase.

To see how β i can be determined, let us take a place p i of degree ι and compute Ψi (p i ). As usual this it the product of the value for all the conjugate points in p i . Then apply one step of the descent algorithm to relate p i to places of degrees = i which are all compatible with the computation of Ψ. Multiplying these contributions gives the renormalized value Ψi (p i ) βi . Thus, if we wish to do so, we can compute β i from the individual logarithms of these two values.

3.3.3.

Intuition about Ψ and commutativity of the diagram. This definition matches with the following intuitive one. To unsure the commutativity of the diagram we need to verify that Ψ(Ξ(ι(A q B -AB q ))) is equal in the finite field to the element

Ψ(Ξ(ι(A(V, W )B -AB(V, W )))).
Our intuition is that requiring in some sense:

U q = V and V q = W
would suffice to prove the commutativity. We point out that one point of the elliptic curve C , namely Φ(F ), precisely follows this restriction. Indeed, Φ(F ) has abscissa

x F -P1 = x π (k-1) (π(F -P1)) = x π (k-1) (F ) = π (k-1) (θ), ordinate x F = θ and applicate x F +P1 = x π(F ) = π(θ).
In a nutshell:

Φ(F ) = [θ q k-1 , θ, θ q ]
Thus, in the function field F q (C ), evaluation the functions at Φ(F ) gives the expected relationship to the Frobenius map. As a consequence, evaluation at F after transporting back to the function field of E using Φ * also gives the desired behavior.

To conclude about the commutativity of the diagram it suffices to note that we have the equalities in F * q :

Ψ • div • Φ * (U q ) = (θ q k-1 ) q = θ = Ψ • div • Φ * (V ) and Ψ • div • Φ * (V q ) = θ q = Ψ • div • Φ * (W ).
Hopefully, since Ψ • div • Φ * • ι is a morphism the equality in the finite field between images of A q B -AB q and A(V, W )B -AB(V, W ) holds too.

Extension of the diagram to bigger fields.

As with classical Frobenius representation algorithm, the commutative diagram can also be used when the coefficients of A and B are taken in another extension F q d . In that case, the commutative diagram ends in the compositum of F q d and F q k . The only difference is that the identity in the finite field is between the images of A q B -AB q and A π (V, W )B -AB π (V, W ), i.e. the coefficients of A and B need to be acted on by Frobenius.

4. Harvesting Relations. This section details the necessary tools to collect relations in our setting which is a mixture of the classical Function Field Sieve and of the Frobenius representation algorithms. As in the classical Function Field Sieve, our algorithm uses function fields instead of polynomials when writing down multiplicative relations. From Frobenius representation algorithms it inherits the use of a systematic form of relations.

4.1. The usual systematic product. We recall the systematic relation that we inherit from Frobenius representation algorithms:

A q B -A B q = α∈P1(Fq) (A -α B), (2)
where as in [START_REF] Joux | Improving the polynomial time precomputation of frobenius representation discrete logarithm algorithms -simplified setting for small characteristic finite fields[END_REF], when α is the point at infinity of P 1 (F q ), the term A -α B is used as a shorthand for B. For simplicity, we also use a bracket notation and define:

[A, B] = A(V, W ) B(U, V ) -A(U, V ) B(V, W ).
We underline that our bracket is F q -bilinear and antisymmetric, as in [START_REF] Joux | Improving the polynomial time precomputation of frobenius representation discrete logarithm algorithms -simplified setting for small characteristic finite fields[END_REF]. Yet, we warn the reader of the difference between the definition of our bracket and previous ones. Our bracket is equal to the entire fraction whereas the authors of [START_REF] Joux | Improving the polynomial time precomputation of frobenius representation discrete logarithm algorithms -simplified setting for small characteristic finite fields[END_REF] only consider the numerator of this rational fraction.

4.2.

Choice of A and B. In the commutative diagram of Figure 2 and in the above discussion, we indicate that relations are obtained from a choice of two bivariate polynomials A and B in U and V . However, we need to specify how these polynomials are chosen and which monomials they should contain. As a preliminary, let us notice that (A, B) and (αA, B) for α ∈ F q lead to the same relation. Indeed, (αA) q B -(αA) B q = α(A q B -A B q ) so the two divisors associated to the two corresponding functions are equals. Thus A and B are chosen as some kind of monic polynomials: the coefficient of the higher monomial (in the lexicographic order for instance) must be equal to 1. Then we note that monomials divisible by (U V ) 2 are not useful in A and B. Indeed, when going to F q [C ], reduction modulo S 3 (U, V, x 1 ) transforms these monomials into smaller monomials U 2 V, U V 2 , U 2 , U V, V 2 , U, V and 1. Moreover, it is natural to consider sets of monomials globally symmetric in U and V .

As a consequence for all those items, given a parameter t ≥ 1 we construct A and B as linear combinations of monomials from:

M t = U i , V i , U i V, U V i |i ∈ [0 • • • t] . Each M t contains 4t distinct monomials 1 . 4.3. Defining a naive factor base. Let D = Qi∈V e i Q i be a divisor of Div(V).
The degree of the zero of D (or height of D) is h(D) = ei>0 e i . Note that, for any prime or elementary divisor, the height is equal to the degree of the corresponding place. This notion of size is needed to define the factor base, which is as a subset of Div 0 (E ), as it is shown in Figure 2. We now explain how this subset is chosen. 4.3.1. Left side. Following the ideas of all Frobenius representation algorithms, we define the factor base such that the images of A -αB in this set are small. Doing this improve the relation collection phase compared to a classical sieving. Indeed, all elements in the left part of the diagram will belong to the factor base. The relation collection phase produces divisors of the form Ξ(i( (A -αB))), so, thanks to the fact that we consider morphisms, it yields a sum of divisors (Ξ(i(A -αB))). As explained, we require all the divisors noted by:

Ξ(i(A -αB))
to be in the factor base.

Let us find the maximal height they can reach. To do so we set A and B two linear combinations of monomials in M t and t an integer parameter to define later. All polynomials A -αB are so linear combinations of monomials in M t too. In other words, we are considering divisors of functions of F q (E ) of the form Φ * ( m∈Mt a m m) = m∈Mt a m Φ * (m) where a m are constants in the base field. We know that the height of the divisors we obtain in the left part of the diagram are dominated by the largest height achieve for any Ξ(m), with m ∈ M t .

Considering

h(Ξ(U t V t )) ≤ t h(Ξ(U )) + t h(Ξ(V ))
, we see that it suffices to determine both the height of the divisors associated to the images of U and V in the function field of E . The most significant monomials will be U t V and U V t .

Functions of C

Height of the associated divisors in

E 1 0 U, V, W 2 U V, V W, U W 4 U + V, V + W, U + W 4 U t V, U V t 2t + 2 U t V + U V t at most 2t + 2 U t V t+1 W, U V t+1 W t , U t V 2 W t , U V 2t W 4t + 4
Table 1. Some functions of F q [C ] and their height in E .

On the one hand we have

Ξ(V ) = div(X) = ([0, √ b, 1]) + ([0, - √ b, 1]) -2(O) where √
b is an element2 in Fq such that its square is equal to b. Hence:

h(Ξ(V )) = 2. (3)
On the other hand,

Ξ(U ) = div((Y + y 1 ) 2 -(X -x 1 ) 3 ) -div((X -x 1 ) 2 ). From div((Y +y 1 ) 2 -(X -x 1 ) 3 ) = 2(-P 1 )+(Q 1 )+(Q 2 )-4(O)
, where Q 1 and Q 2 are two conjugated points of a degree-2 place, and div((X -

x 1 ) 2 ) = 2(P 1 ) + 2(-P 1 ) -4(O), it comes Ξ(U ) = (Q 1 ) + (Q 2 ) -2(P 1 ). We obtain: h(Ξ(U )) = 2. (4)
Putting Equations ( 3) and ( 4) together with the upper bound, we conclude that the most significant monomials U t V and U V t have both height 2t+2. Yet Φ * (U t V ) and Φ * (U V t ) do not share the same denominator so to count their respective contribution in the height of divisors m∈Mt a m Φ * (m) we need to add the contribution of the residual denominator. Namely, since Φ * (U t ) brings the largest denominator, the height of the divisor of Φ * (U t V ) does not change, but for the one of Φ * (U V t ) we need to add the number of zeros corresponding to the denominator of Φ * (U t /U ). We note that there is 2(t -1) such points. To put it in a nutshell, the most significant monomial is U V t and all divisors on the left are sum of divisors with a height upper-bounded by 4t = (2t + 2) + 2(t -1).

To conclude, starting the relation collection phase with t = 1 it is natural to set the initial factor base as included in the set of divisors of Div 0 with height equal or lower than 4. We emphasize that in this case, all the divisors appearing in the left part belong to the factor base. Let us consider the polynomials of F q [U, V, W ] given on this side and write this time

M V W t = V i , W i , V i W, V W i |i ∈ [0 • • • t]
. Sorting the monomials in the lexicographic order, we recall that the leading coefficient for both A and B can be chosen equal to 1. Thus, keeping the leading monomial U t V apart and calling a m

Functions of C

Height of the associated divisors in E A(U, V ) -αB(U, V ) where α ∈ F q at most 4t

A(V, W )B(U, V ) -A(U, V )B(V, W ) at most 8t
Table 2. Functions appearing on both side of the diagram, and their corresponding heights in E . A and B are linear combinations of monomials from M t .

(resp. b m ) the coefficients in F q of A (resp. B) we obtain on the right side the polynomial:

[A, B] = A(V, W )B(U, V ) -A(U, V )B(V, W ) =   V t W + m∈M V W t \{V t W } a m m     U t V + m∈Mt\{U t V } b m m   -   U t V + m∈Mt\{U t V } a m m     V t W + m∈M V W t \{V t W } b m m  
Since the monomial U t V t+1 W vanishes it yields a linear combination of monomials where the three that dominate the height of the associated divisor are U V t+1 W t , U t V 2 W t and U V 2t W . Indeed, each variables U , V and W contributes the same way, thus, the most important monomials are those with the highest additive degree. We note then that we have h

(Ξ(U V t+1 W t )) = h(Ξ(U t V 2 W t )) = h(Ξ(U V 2t W )) = 4t + 4.
Yet, again, we need to carefully add the zeros raised by the residual denominator. The contribution of Φ * (U t V 2 W t ) is left unchanged but we must add the number of poles of Φ * (W t /W ) to the height of the divisor associated to Φ * (U V t+1 W t ) and the one corresponding to the denominator of Φ * ((U W ) t (U W ) -1 ) to the height of the divisor associated to Φ * (U V 2t W ). Since there are respectively 2(t -1) and 4(t -1) such points, we conclude that all the divisors appearing on the right side are twice as large as factor base elements since they have height equal or lower than 8t = 4t + 4 + 4(t -1). In particular, when t = 1, this gives divisors of height 8 at most.

4.3.3.

Complexity of the linear algebra with a naive factor base. A first and naive choice of factor base is made of all divisors of height ≤ 4.

However, this factor base is too large to be competitive when compared to the best Frobenius representation algorithms. To show this, let us briefly analyze the number of operations needed to perform linear algebra with this factor base. The number of divisors in this naive factor base is dominated by the number of degree 4 places on the curve E , corresponding to polynomials of degree 4 with coefficients in F q . So the order of the factor base's size is dominated by q 4 . Considering the Frobenius action of Section 4.4 that permits to divide the size of the factor base by k ≈ q, we obtain a factor base of size O(q 3 ). Since there are q terms in each linear equations, performing a sparse linear algebra step can be done in O((q 3 ) 2 q) = O(q 7 ) operations.

As a comparison, we see that the first phase of the algorithm in [START_REF] Joux | Improving the polynomial time precomputation of frobenius representation discrete logarithm algorithms -simplified setting for small characteristic finite fields[END_REF] only has a O(q 6 ) complexity. Thus, we need to improve our initial factor base. 4.4. Action of Frobenius and translation by P 1 . Let d be the largest possible height of an elementary divisor of the factor base. We would like to explicit how the action of Frobenius on elements of the finite field F q k is related to addition of -P 1 on the elliptic curve E . Considering the divisors:

D Q = d-1 i=0 (π i (Q)) -d(O)
related to the place given by any point Q ∈ E and:

D Q-P1 = d-1 i=0 (π i (Q -P 1 )) -d(O)
related to the translation of Q by -P 1 . We show that the two discrete logarithms satisfy a simple relation. More precisely, we have the following result: Lemma 2. Let Q ∈ E be a point with coordinates in F q d . We consider the divisors

D Q = d-1 i=0 (π i (Q)) -d(O) and D Q-P1 = d-1 i=0 (π i (Q -P 1 )) -d(O)
respectively related to the place given by the point Q in E and the one given by the translation of Q by -P 1 . Then:

Ψ(D Q-P1 ) = π(Ψ(D Q )) • Ψ((-P 1 ) -(O)) dN d .
where N d is divisible by all the cardinalities of E over each finite field F q i ⊂ F q d . Proof. Let us start from D Q the degree-d divisor. We recall that to have a principal divisor we need to consider N d D Q . Thanks to Miller algorithm we are able to recover a function f Q with coefficients in the base field F q such that N d D Q is the divisor of this function. By definition we obtain:

Ψ(D Q ) = f Q (F -O) 1/N d . To simplify the notation let us write α = f Q (O) 1/N d that is an element in F q .
Hence on the one hand we have:

π(Ψ(D Q )) = π(f Q (F ) 1/N d )/π(α) = f Q (π(F )) 1/N d • α -1 since α ∈ F q . ( 5
)
To link this expression to the divisor of π(Q), i.e. to the evaluation of f Q in the point π(F ) = F + P 1 we define the function g Q such that, for all S in E , g Q (S) = f Q (S + P 1 ). Let us write the divisor of this new function. Since a zero S (resp. a pole) of g Q is such that S + P 1 is a zero of f Q (resp. a pole), we obtain:

div(g Q ) = N d ( d-1 i=0 (π i (Q) -P 1 ) -d(-P 1 )) = N d ( d-1 i=0 (π i (Q -P 1 )) -d(-P 1 )) since P 1 is in E /F q = div(f Q-P1 ) + N d (d(O) -d(-P 1 )) = div(f Q-P1 ) -dN d ((-P 1 ) -(O))
Hence on the other hand we have: 1) and ( 5).

Ψ(D Q-P1 ) = Ψ(div(f Q-P1 )) = Ψ(div(g Q ) + dN d ((-P 1 ) -(O))) = Ψ(div(g Q )) • Ψ((-P 1 ) -(O)) dN d = g Q (F ) 1/N d α -1 • (α/g Q (O) 1/N d ) • Ψ((-P 1 ) -(O)) dN d = mod Fq g Q (F ) 1/N d α -1 • Ψ((-P 1 ) -(O)) dN d = mod Fq f Q (F + P 1 ) 1/N d α -1 • Ψ((-P 1 ) -(O)) dN d = mod Fq π(Ψ(D Q )) • Ψ((-P 1 ) -(O)) dN d from Equations (
We emphasize that the green term is a constant term. Thanks to this action, we are able to reduce the size of the factor base by a factor k throughout the computations. Indeed, if we know the discrete logarithm of Ψ(D Q ) then we learn for free the discrete logarithms of

Ψ(D Q-P1 ), Ψ(D Q-P2 ), • • • , Ψ(D Q-P k-1 ).
4.5. Getting a smaller factor base. To be able to reduce the size of the initial factor base, and thus to decrease the complexity of the linear algebra phase, we adapt the idea of systematic factors that was presented in [START_REF] Joux | Improving the polynomial time precomputation of frobenius representation discrete logarithm algorithms -simplified setting for small characteristic finite fields[END_REF] to the elliptic case. The idea was twofold: first extracting some systematic factors that appear in every equation, second, restrict the search to a sieving space that induce extra common factors. In this article, we choose to call these extra factors compelled factors to underline the difference with previous ones.

Left part of the diagram: making P 3 a compelled point. In our case, our aim is to consider a subgroup of the sieving space where A and B are polynomials such that the associated divisors always present a common (compelled) point. Here, choose to use the special point P 3 = 3 P 1 . As in [START_REF] Joux | Improving the polynomial time precomputation of frobenius representation discrete logarithm algorithms -simplified setting for small characteristic finite fields[END_REF] we select three generators g 1 , g 2 , g 3 in F q [U, V ] leading to divisors going through P 3 . We propose to sieve on pairs of polynomials (A, B) such that A = g 1 + αg 3 and B = g 1 + βg 2 + γg 3 where α, β, γ ∈ F q . Indeed, if A (resp. B) is a linear combination of those three generators and if P 3 is a zero of Φ * (i(g j )) for j = 1, 2 and 3 then it is also a zero of the image of A (resp. B) in E . As a consequence and for the same reason, P 3 is a zero of the image of A -αB too, where α belongs to the base field. Lemma 3. Let j be an integer in [0, k -1] and assume that P 0 is a shorthand for O. Then:

Ξ(U -x j ) = (P j+1 ) + (-P j-1 ) -2(P 1 ), Ξ(V -x j ) = (P j ) + (-P j ) -2(O),
and Ξ(W -x j ) = (P j-1 ) + (-P j+1 ) -2(-P 1 ).

Proof. Let j be an integer between 0 and k -1. We recall that x j denotes the abscissa of P j ∈ E and x 0 = 0. Then by definition:

Φ(P j ) = [x j-1 , x j , x j+1 ]
for all possible values of j. It means that, over the curve C , Φ(P j ) is a zero of U -x j-1 , V -x j and W -x j+1 . Going back to the curve E it yields that the point P j is a zero of Φ * (U -x j-1 ), Φ * (V -x j ) and Φ * (W -x j+1 ). Similarly, from:

Φ(-P j ) = [x j+1 , x j , x j-1 ]
we get that -P j is a zero of Φ * (U -x j+1 ), Φ * (V -x j ) and Φ * (W -x j-1 ). Besides, writing Φ * (U -x j ) as ((Y + y 1 )/(X -x 1 ))

2 -X -x 1 -x j we see that P 1 is a pole of Φ * (U -x j ) with multiplicity 2. Similarly -P 1 is a pole of W -x j with multiplicity 2. From Φ * (V -x j ) = X -x j we conclude that O is twice a pole too.

Hence as generators we select:

g 1 = U -x 2 , g 2 = V -x 3 , and g 3 = (U -x 2 )(V -x 3 ). ( 6
)
From Lemma 3 we have Ξ(g 1 )) = (P 3 ) + (-P 1 ) -2(P 1 ) and Ξ(g 2 )) = (P 3 ) + (-P 3 ) -2(O). Thus Ξ(g 3 )) = 2(P 3 ) + (-P 1 ) + (-P 3 ) -2(O) -2(P 1 ). Clearly the point P 3 is a positive point of each divisor.

Thus, if we start to sieve with a parameter t equal to 1, we obtain divisors on the left part of the diagram that have a height lower or equal to 4. Since P 3 is a positive point for all these divisors, we are left with divisors that have a height lower or equal to 3. We conclude with the definition of the reduced factor base:

F = {d ∈ Div(E ) | d is elementary and h(d) ≤ 3} .
Remark 2. The factor base is the same on both sides of the diagram.

As previously, we can upper bound the cardinality of the factor base by the number of divisors with height lower than 3, so the number of monic degree-3 polynomials in F q , which is q 3 . Thanks to the Frobenius action, the base is reduces by a factor of k, and the reduced factor base has size O(q 3 /k). At the end, assuming that we get enough equations (we discuss this issue in Section 4.6), linear algebra recovers the discrete logarithms of the initial factor base elements in O((q 3 /k) 2 q) = O(q 7 /k 2 ) operations. When k is close to q, this matches the result of [START_REF] Joux | Improving the polynomial time precomputation of frobenius representation discrete logarithm algorithms -simplified setting for small characteristic finite fields[END_REF]. Remark 3. Note that by contrast with polynomials, ideals of degree 4t are determined from 4t monomials, instead of 4t + 1. This is unfortunate because it forces us to increase the degrees to get enough degrees of freedom when generating relations. However, this drawback is counter-balanced by the reduction of the factor base size obtained by using the action of Frobenius.

4.6. How to get enough relations with the reduced factor base. Thank to P 3 which is a compelled point we know that, on the left part of the diagram, we directly have divisors that split into factor base elements only. Now the questions are whereas we manage to easily obtain small height divisors on the right part or not, and how many relation we expect to write. We recall that, to be able to perform linear algebra, we need as many relations as unknowns.

We have around q 3 /3 unknowns and we sieve on q 3 pairs of polynomials (A, B) consisting in linear combinations of g 1 , g 2 and g 3 as given in [START_REF] Göloglu | A simplified approach to rigorous degree 2 elimination in discrete logarithm algorithms[END_REF]. It means that we need a probability higher than 1/3 to get a relation. Since a degree-d divisor is clearly linked with an irreducible polynomial of the same degree as seen in Section 2, this probability is assumed to be the same that a random polynomial of degree d to factor into terms of degree at most 3.

For degree d = 8, the probability is easy to compute. A polynomial fail to factor into terms of degree at most 3 when one factor as degree 4 or more. Since there can only be a single factor when the degree is 5, 6, 7 or 8 and at most two of degree 4. Thus, for large fields, the probability of success approaches 1 -(1/8 + 1/7 + 1/6 + 1/5 + 3/16 + 1/32) ≈ 0.147. Unfortunately, this is much smaller than 1/3.

Right part of the diagram: the two compelled points P 2 and P 3 . Thus we need to look at the right part of the diagram more carefully. Going back to the analysis made in Section 4.3, Right part we see that choosing A and B as monic (in some sense) does not reduce the height of the associated divisor. Hence, for (A, B) a pair of linear combinations of g 1 , g 2 and g 3 as in [START_REF] Göloglu | A simplified approach to rigorous degree 2 elimination in discrete logarithm algorithms[END_REF], the divisor:

Ξ([A, B])
has still a height of 8. Because P 3 is a zero of Φ * (A(U, V )) and Φ * (B(U, V )), we note that P 3 is a zero of Φ * ([A, B]) too. Yet it is not enough and we need to extract another compelled positive point of the associated divisor to the image of A(V, W ) (resp. B(V, W )) over E . We start by underlining that g 1 , g 2 and g 3 respectively becomes V -x 2 , W -x 3 and (V -x 2 )(W -x 3 ), when sending V to W and U to V . Thus according to Lemma 3, the point P 2 = 2 P 2 is a zero of all the generators, and so a zero of [A, B] as P 3 . We conclude that we are left with a divisor of height at most 6. The probability that it splits into a sum a divisors with height at most 3 is so roughly equals to:

1 -(1/6 + 1/5 + 1/4) ≈ 0.383 > 1/3, as q grows. As a consequence, we heuristically expect to get a linear system with enough equations to get the discrete logarithms of all elements of F in O(q 5 ) operations.

Heuristic. The heuristic in this linear algebra step and in all the following ones comes from the fact that we have no argument to prove we really get enough equations. We can count them and expect that when their number slightly exceeds the number of unknows, we are able to find a solution. Yet, nothing provably indicates whether the kernel of our matrix of relations has dimension 1 or not.

5.

Extended Factor Base and Individual Discrete Logarithm. We only sketch here the last two main steps of our practical algorithm, the computation of an Extended Factor Base and the Individual Discrete Logarithm step. Indeed, they are an adaptation of the techniques that already exist for Frobenius representation algorithms to our setting.

5.1.

From divisors of height 3 to divisors of height 4. As done in Frobenius representation algorithms, we extend the initial factor base and now include all elementary divisors up to height 4. Thanks to the Frobenius action, there are approximately q 4 /4k ≈ q 3 /4 unknowns. The naive approach we showed earlier gives the desired logarithms at a cost of O(q 7 ) arithmetic operations (or O(q 9 /k 2 ) when k is away from q). Practical speed up with regrouping. To speed up the computation of height 4 divisors, it is possible to decompose the height 4 factor base into small groups, in a way similar to [START_REF] Joux | Improving the polynomial time precomputation of frobenius representation discrete logarithm algorithms -simplified setting for small characteristic finite fields[END_REF], in order to perform several linear algebra steps on these small groups, instead of a single big linear algebra step. In Appendix B, we give details on how to produce relation in these groups. One technicality is the interaction of the groupings with the reduction of the factor base size given the action of Frobenius.

Once the height 4 divisors are obtained, it is a simple matter to continue extending the factor base to height 5 divisors. For that final step, no additional linear algebra is needed. It suffices to keep relations where a single height 5 divisors appears, the rest being of lower degree. See Appendix B for a detailed explanation. However, for the height 4 extension, the expected number of produced relations seems to be slightly too low asymptotically to guarantee its success. Nevertheless, we tested the method on a practical example to check its viability. Namely, for the target finite field F 3 1345 , we were able to compute logarithms for an extended factor base comprising divisors of height up to 5. This was done by choosing a curve of (prime) cardinality 269 over F 243 . Studying the exact behavior of the height 4 extension to understand this gap is thus a matter of further research.

Computing Individual Discrete Logarithms.

To solve the discrete logarithm problem in our target finite field, we need not only to know the logarithms of extended factor base elements but to be able to compute the discrete logarithm of any arbitrary element. This is the aim of this section. Various descent phases were previously proposed by various authors, the idea is to show how to adapt to our context. In practice, one can use the bilinear descent, the classical descent and the zig-zag descent or a mix of them. Indeed the quasi-polynomial descent of [START_REF] Barbulescu | A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic[END_REF] is unlikely to be practical for currently accessible computations.

For the classical descent which simply consist in writing the target finite field element whose discrete logarithm is wanted as a product or quotient of relatively low-degree polynomials in θ, no adaptation is needed. We only need to check that any polynomial in f (θ) can be injected in the commutative diagram. This is simply done by written the divisor of f (V ) since Ψ(V ) = θ. When f is irreducible, the corresponding divisor is either the sum of two elementary divisors of height deg(f ) or a single elementary divisor of height 2 deg(f ).

We illustrate the adaptation with the bilinear and zigzag descents: 5.2.1. Bilinear descent for our setting. The bilinear descent step is easy to adapt from [START_REF] Joux | Improving the polynomial time precomputation of frobenius representation discrete logarithm algorithms -simplified setting for small characteristic finite fields[END_REF]. Remark that we usually need to unbalance the degrees of freedom in A and B, thus choosing different sets of generating polynomials. Instead of constructing the polynomials just from 1, U , V and U V we built them from higher degree polynomials in M ta and M t b respectively. We assume that t a ≥ t b . Let us first analyze the case where we use all these monomials, remembering that there are 4t a and 4t b of them. As usual, we force A and B to be monic and remove the head monomial of B from A. All of the other coefficients are replaced by a corresponding formal unknown. Thus, the polynomial A contains 4t a -2 unknowns. If t a = t b , B contains 4t b -1 monomials. If t a = t b , we can remove an extra unknown from B. Furthermore, we know that the height of factors of the form A -αB is upper bounded by 4t a . We also know from Table 4.3.3 that the height of the bracket is at most 8t a .

If we want to adjust the values modulo 4 of the number of degrees of freedom, it is necessary to use compelled points. More precisely, we can force A and B to go through one, two or three compelled points. This reduces the degrees of freedom by the same amount on both sides. It also reduces height on the left by the same value and heights on the right by its double.

As in Frobenius representation algorithms, the coefficients of each monomials in [A, B] are bilinear (or linear or constant) in the A and B unknowns. To force an elementary divisor of degree d to appear in [A, B], it suffices to require that the bracket vanishes when evaluated at each of the d conjugate points corresponding to the associated prime divisor. This yields a bilinear system of d equations in the A and B unknowns. This equation can be solved using Grobner basis techniques exactly as in the case of Frobenius representation.

The only extra (and minor) restriction here is the relation between the number of A variables and B variables modulo 4.

5.3.

Zig-zag descent. The zig-zag descent seems to be the best option to achieve provable quasi-polynomial complexity. In particular, it is used both in [START_REF] Kleinjung | Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic[END_REF] and [START_REF] Lido | Discrete logarithm over finite fields of small characteristic[END_REF]. As a consequence, we also show how to adapt it to our setting. As it is more lenghty to describe than the bilinear descent, we assign a separate section to it. F q 2 t [X] z i , where z i are degree-2 polynomials

F q 2 t-1 [X] z i
, where z i are degree-4 polynomials . . .

F q 4 [X] z i , where z i are degree-2 t-1 polynomials F q 2 [X] z • z *
, where z and z * are degree-2 t polynomials F q [X] z a degree-2 t+1 polynomial Figure 3. Tower of extensions over the base field F q in the classical zig-zag descent.

Short recap on the zig-zag descent. First the main idea is to adapt the zig-zag descent presented in [START_REF] Granger | On the powers of 2[END_REF] to our setting. Let us give an insight of this descent in the classical settings. We call z our target, which is an irreducible polynomial in F q [X] of degree3 2d = 2 t+1 . One crucial point of this method is that for any relation in F q 2 [X] implying degree-d polynomials, one can find a relation in the subfield F q [X] at the price of having polynomials of degree twice as large. Thus, in order to make z appear in a polynomial relation of F q [X], we write it as a product of two degree-d conjugated polynomials z and z * over the extended field F q 2 [X] and we try to get one relation (in the extended field) involving one of this degreed polynomials. Multiplying by the same conjugated relation we would obtain a relation (in the subfield) where z appears.

Recursively manipulating this trick on a tower of extensions as presented in Figure 3, we write in fact z as a product of conjugated degree-2 polynomials over F q 2 t [X]. Indeed, this descent method rests upon the existence of an extended field in which any degree-2 polynomials evaluated in θ can be written as product of linear evaluations in θ. Thus at the end, we get a relation of the form z(θ) = i L i (θ) where L i are linear polynomials.

Elliptic zig-zag descent. To adapt the previous descent to our settings, a idealized method would be to exhibit a sufficiently large extension of the curve C in which any height-2 divisor can be written not as a degree-2 place but as a sum of points on this exact extension (and not the larger following one). This precisely would have translated the requirement that all degree-2 polynomials split in linear polynomials when the extension degree of the field is sufficiently large. Unfortunately, to the best of our knowledge, this ideal adaptation isn't possible.

On the technical side, we see that the method is much easier to describe when computing logarithm in F q k for an odd extension degree k. Indeed, in that case, the compositum of F q k and any extension F q 2 i is simply F q k2 i . Making this assumption is very convenient to describe the adaptation to the elliptic representation. We deal now with to the elliptic representation setting, with the additional restriction that the extension degree k is odd. Figure 4 illustrates our general technique.

5.3.1.

Points and divisors over extensions. As mentioned in Section 3, the commutative diagram in Figure 2 can be used not only over F q but also over extensions. We now give more details for F q d , assuming that d and k are coprime.

This we now use polynomials A and B with coefficients in the larger field F q d . Everything remains almost identical, except the definition and properties of the bracket. With a larger field, we use:

[A, B] * = A π (V, W ) B(U, V ) -A(U, V ) B π (V, W ),
where A π denotes the polynomial derived from A by raising each coefficient of A to the power q (while keeping the same monomials). This new bracket [•, •] * is F q -bilinear (but not F q d -bilinear).

5.3.2.

Bootstrapping the descent. Let z ∈ F q k be our target arbitrary element for which we want to find a discrete logarithm. Thanks to the diagram of Figure 2, we know that there exists a polynomial Pol in F q [U, V ] such that:

z = Ψ(Ξ(Pol(U, V ))).
In fact, there are many such polynomials. We choose such that 2 > k and search a representation by a polynomial Pol in F q [U, V ] such that:

1. z = Ψ(Ξ(Pol(U, V ))). 2. h(Ξ(Pol(U, V ))) = 2 . 3. Ξ(Pol(U, V )) exactly corresponds to a place of degree 2 .
Let us call p z such a place in Σ Fq(C ) . We could lift it to Σ F q 2 (C ) so that it corresponds to 2 points. However, for the rest of the method, it suffices to decompose it into degree-8 places. Theses places appear in Σ F q 2 -3 (C ) .

C /F q 2 t-3 (p 8 ) i , where p 8 are degree-8 places C /F q 2 t-4 (p 16 ) i , where p 16 are degree-16 places . . . C /F q 2 p 2 t-1 + p2 t-1 , where p 2 t-1 and p2 t-1 are conjugated degree-2 [A,B] * , there is a way to express the logarithm of the divisor corresponding to a degree-8 place as a sum of logarithms of divisors of degree at most 4. Once this is done, we can pair conjugates divisors and go one step down in the tower of quadratic extension. This at most doubles the height of divisors. Iterating the process, we now encounter places of degree 6 and 8 whose divisors need to be expressed as combination of divisors of degree at most 4. Finally, at the bottom of the tower, everything can be expressed using divisors of height at most 4, this in turn permit to compute the logarithm of z.

Keeping this strategy in mind we now describe the transformation of logarithm of divisors into sums of divisors of lower height. More precisely, we first transform degree 8 places as sums using divisors of height at most 6. Places of degree 6 can be expressed using divisors of height up to 5. Finally place of degree 5 are transformed using divisors of height up to 4.

The exact degrees appearing in the descent strategy depend on the relative position in the tower of extension. Except at the lower levels, it is possible to descent directly from degree 8 to degree 5 and from degree 6 to degree 4. Except at the lower levels, it even possible to descend from degree 4 to degree 3.

Thus, from a practical point of view,there are two essentially equivalent options for the descent. Either one starts from a degree-8 place and encounters descent steps from 8 to 5 then 4 and descent steps from 6 to 4, except in the lower levels where longer chains from 8 to 6 then 5 and finally 4 appear. Or one starts from a degree 4 place and encounters descent steps from 6 to 4 then 3 and steps from 4 to 3. At the lower levels, this approach gets stuck.

In our presentation, we choose the approach that starts from a degree-8 place. Note than in the context of provable algorithms, using degree 8 possibly leads to a more difficult proof. 5.3.4. Degree-5 places. We start with degree 5 places since it is slightly simpler and illustrates the general idea. We let d be the power of 2 corresponding to our current position in the tower of extensions.

Again, we create somehow relations from:

α∈P1(Fq) (A -α B) = [A, B] * ,
where (A, B) is a pair of polynomials with coefficients in F q d . For degree 5, the polynomials are built from monomials in M 1 , i.e. from 1, U , V and U V . To check whether there are enough degrees of freedom to force a place too appear, we need to consider how many (non equivalent) pairs of candidates relations we can try. Since we use the new bracket instead of [•, •], the counting changes slightly. Before considering the property of the bracket, there is a total of 8 coefficients in F q d , four in each of A and B. Remark that, for any Λ ∈ F q d , we have [ΛA, ΛB] * = Λ q+1 [A, B] * . Simultaneously, the left side corresponding to (ΛA, ΛB) is Λ q+1 α∈P1(Fq) (A-αB). Since Λ q+1 appears on both sides, we see that (A, B) and (ΛA, ΛB) generate the same equation. Thus, we can set the leading coefficient of A to 1. This removes one of the coefficients.

In addition, because of the F q -linearity of the bracket, for any λ ∈ F q , we have This decreases the numbers of degrees of freedom to 7 -3/d > 5, when d > 1. Thus, we have enough degrees of freedom available. In the case d = 1, we are in the base field where the logarithms of the degree-5 places have already been precomputed as part of the extended factor base.

Let p 5 be a place of degree 5 in Σ F q d (C ) . Using a variation on bilinear descent and solving a bilinear system of equations in 6 unknowns over the extension field F q d , we can obtained a relation involving p 5 . Since the number of variables is a small constant, this is a very efficient computation.

The relation can be written in the form:

D∈Div | h(d)≤4 D = (p 5 ) + D 3
where D 3 is a divisor of height 3. This shows that we can descend any divisors of height 5 as a sum of divisors of height at most 4. Note that D 3 and the divisors on the left may not be elementary, however, in that case they decompose into elementary divisors of lower degrees.

Note that we do not prove here that such a decomposition always exists. Instead out counting of the degrees of freedom gives heuristic support to this fact. It might be possible to adapt the proofs of [START_REF] Lido | Discrete logarithm over finite fields of small characteristic[END_REF] or [START_REF] Kleinjung | Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic[END_REF] to our specific setting. 5.3.5. Degree-6 places. For degree 6, there are two options depending of the extension degree d.

When d ≥ 4, we can again build relations using only the monomials 1, U , V and U V . In this case, it gives 7 -3/d > 6 degrees of freedom. Thus, we can directly descend to a sum of divisors of height at most 4.

For the remaining cases, d = 2 or d = 1, we need to use monomials from M 2 to provide more degrees of freedom. However, if we use them all, the height of the left-hand factor become 8 and the height of the bracket is 16. To control this explosion, it suffices to fix three (essentially arbitrary) compelled points and keep a basis of all functions going through these 3 points. This basis contains 5 polynomials, say g 1 , . . . , g 5 . Forming A and B as linear combinations of the g i s induces a systematic factor of total height 3 in every term A -αB (corresponding to the compelled points). Furthermore, this systematic factor also appears in the decomposition of the bracket together with an extra systematic factor also of height 3. This extra factor corresponds to the compelled points translated by -P 1 . Thanks to the systematic factors, the height of the left becomes 5 while the height of the right becomes 10. There is a total of 10 coefficients in A and B, which corresponds to 9 -3/d ≥ 6 degrees of freedom when removing identical relations as in the previous case. More precisely, we can fix the coefficient of g 1 in A to 1, one component of the coefficient of g 1 in B to 0, and one component of g 2 to 1 in B and 0 in A. Solving a bilinear system, we can find coefficients that lead to an equation:

D∈Div | h(d)≤5 D = (p 6 ) + D 4
where D 4 is a divisor of height 4. This expresses the logarithm p 6 as a sum of logarithms of divisors of height at most 5.

5.3.6. Degree-8 places. For degree 8 places, we proceed as in the second method for degree 6. We use monomials from M 2 . With three compelled points as in degree 6, we have 9 -3/d degree of freedom. This is more than 8 as soon as d ≥ 4. In this case, we can write the logarithm p 8 as a sum of logarithms of divisors of height at most 5.

When d is 1 or 2, we use only two compelled points. We thus have a basis of 6 polynomials and 9 -3/d ≥ 8 degrees of freedom. The height after removing the systematic factors become 6 for the left factors and 12 for the bracket. Thus, in the lower levels of the tower of extension, we can write the logarithm p 8 as a sum of logarithms of divisors of height at most 6. 5.3.7. Practical (un)efficiency of the approach. In the Frobenius representation zigzag, every step down the tower was based on the creation of one relation. As a consequence, at every level, the total number of elements under consideration was multiplied by O(q). By contrast, here, we need two levels of relations for each of the middle levels of the tower. As a consequence, the total number at each level is multiplied by O(q 2 ), which makes this approach much less appealing in practice.

6. Practical discrete experiment over F 3 1345 . To study the practicality of the elliptic representation in discrete logarithm computations, we have performed an experiment using q = 3 5 = 243. We did run our experiment on a server. The most time consuming steps where implemented in pure C, with calls to the magma software [START_REF] Bosma | The Magma algebra system. I. The user language[END_REF] for verification purposes and complex Gröbner basis computations.

We define

F 243 as F 3 [a]
where a is a root of the irreducible polynomial x 5 -x + 1. To define the full extension, we use the elliptic curve E with equation:

y 2 = x 3 + a x 2 + x + a 35 .
This curve has k = 269 points over F 243 , thus allowing us to define the extension

F 243 269 = F 3 1345 = F 243 [v].
Note that this k is a prime close to the top of the Hasse interval for a field with 3 5 elements. We also choose the point P 1 = (1, a 195 ) to describe the action of Frobenius.

The trivariate description, i.e. the curve C obtained from the Semaev polynomial is then defined by the three equations:

U V +a 3 U W +a 9 U +V W +V +a 9 W +a 193 =0 U W 2 +a 13 U W +a 26 U +a 239 V W 2 +a 239 V W +a 239 V +a 6 W 2 +a 59 W +a 134 =0 V 2 W 2 +V 2 W +V 2 +V W 2 +a 190 V W +a 38 V +W 2 +a 38 W +a 110 =0
Adding the two extra Frobenius relations V = U q and W = V q we can use a Gröbner basis algorithm to find the minimal polynomial F v of our finite field generator v.

For simplicity, we use the image of the point P 1 by the pairing to the field as a basis of the discrete logarithms in the subgroup of large order:

3 1345 -1 648196409762 .
Of course, 648196409762 = 2 × 11 2 × 10223 × 262007 is small enough so that logarithms modulo this number can be computed by generic algorithms.

6.1. First set of discrete logarithms. In an initial step, we constructed equations from a pair of polynomials (A, B) of the form:

A(U,V )=(U -U (P1))(V -V (P1))+C A (U -U (P1),B(U,V )=(V -V (P1))+D B (U -U (P1),
where C A and D B take all possible values in F 243 . Because of the compelled point P 1 , every polynomial of the form A -αB factors into places of degree at most 3.

Going through all the possible pairs took 90s on a single core of our server and created 22 575 equations in 17 887 variables corresponding to the places of degree 2 and 3. This system of equations was then solved using Wiedeman algorithm, the standard four phases respectively took:

• First matrix multiplication sequence. 286 minutes on four cores,

• Fast Berlekamp-Massey. 14 minutes on a single core,

• Second matrix multiplication sequence. 146 minutes on four cores,

• Final sum and verification. 3 minutes on a single core. The resulting 17 887 logarithms were tested by using magma to transfer places to the finite field through pairings and verifying the exponentiation. 6.2. Discrete logarithms of degree-4 places. For places of degree 4, we used the grouping technique described in Appendix B and worked with 244 groups. For a typical group4 , the cost of computations of the corresponding logarithms are distributed as follow:

• Generating equations. Under a minute on a single core, about 13 500 unknowns per group. • First matrix multiplication sequence. 8 minutes on four cores, • Fast Berlekamp-Massey. 10 minutes on a single core, • Second matrix multiplication sequence. 5 minutes on four cores, • Final sum and verification. Under a second. In total, 3 253 919 logarithms were computed for degree 4 places. 6.3. Discrete logarithms of some degree-5 places. For place of degree 5, a fraction of the logarithms can be obtained by descending to degree 4. Unfortunately, this is not enough to get all of them. To be able to go the descent phase, we divided the places of degree 5 into 242 × 244 groups of approximately equal size. Each full set of 244 groups in turn permits a "descent" from degree 5 to degree 5 (inside the specific set of group) for a fraction of places. In total, 20 full sets of 244 groups were enough to enable the descent phase. The timings for each set of groups were as follow:

• Generating equations. About 750 minutes for most sets (less for the first three because of the cost of descent for later sets). • Linear algebra. About 4 minutes on four cores, for a single group. I.e.

roughly 1000 minutes for a set. • Final verification. About 15 000 minutes to recompute all equations, check all logarithms and perform eventual corrections. The corrections are necessary when the initial (truncated) systems of equations do not have full rank. In that case, a small number of logarithms are possibly wrong and corrected in this step. In total, 1 753 982 logarithms were computed for the first set of degree 5 places. Then, 754 224 for the second set and 323 074 for the third. Finally, the remaining 17 sets of roughly equal size (because of the choice to only use the first three for degree-5 to degree-5 descent here) containing altogether 2 319 092 logarithms. 6.4. Descent. To illustrate the descent, we start from a challenge generated from the expansion of the real constant Π. The exact formula is given in a magma verification script available on request, or given in Appendix C. Let us denote this challenge value by Z.

In a first step, we consider many elements of the form Z i,j = Z • (u + 1) i • (u + a) j . Since the logarithms of v + 1 and v + a are known, finding the logarithm of one of those is equivalent to finding the logarithm of Z. We consider many such elements to have a better chance to find a smooth expression of one of them.

For each such element, we view it as a polynomial in v and using a continued fraction algorithm to find an expression of Z i,j as a quotient of two half-degree polynomials in v. We kept the Z i,j with the lowest possible degree obtained after factoring the numerator and denominator. More precisely, we do not consider the degree of the factorization into polynomials but into places of the curve C .

We considered 240 values of j and 30 000 values of i for each j. We run 48 instances in parallel on our server for a wall-clock time of 4200 minutes and a CPU-time of approximately 140 days.

The best Z i,j contained places up to degree 36, it is given in the magma verification script.

By using the bilinear descent, we were able to compute the logarithms of places up to degree 18. As an illustration, we give in the magma file the logarithm of a degree 18 polynomial in v, which was computated as the sum of logarithms of two places of degree 18. Each of those two computations took about 4 days, using a single core 5 . We also computed the logarithms of lower degree places.

However, our decomposition still contains three polynomials of respective degree 25, 34 and 36 (each corresponding to two places of the same degree) for which we could not compute the logarithms. The reason for this aborted computation is that the Gröbner basis descent did not terminate for theses cases. We considered using the alternative approaches but did not find an option that would allow us to finish the computation without requiring excessive development and/or running times.

Appendix A. Notations and reminders about algebraic function fields and divisors. Let K = F q denote a finite field. Let C be a non-singular curve in the n-dimensional projective space P n (F q ) defined over K and π denote the Frobenius map on P n (F q ). We let K(C ) denote the function field of C over K. More details can be found in [START_REF] Cohen | Handbook of Elliptic and Hyperelliptic Curve Cryptography[END_REF][START_REF] Stichtenoth | Algebraic Function Fields and Codes[END_REF] if needed. A discrete valuation on K(C ) is a map V from K(C ) to Z such that for all x, y ∈ K(C ) we have:

1. V(xy) = V(x) V(y); 2. V(x + y) ≥ min(V(x), V(y)); 3. V(x + y) = min(V(x), V(y)) when V(x) = V(y). We define an equivalence relation between valuations by saying that two valuations V and V are equivalent whenever there exists a non zero rational constant α such that for all x ∈ K(C ), we have V (x) = α V(x). We recall that a place of K(C ) is an equivalence class of discrete valuations of K(C ) which are trivial on K. The set of places of K(C ) is denoted by Σ K(C ) . In every place p, there exists a unique valuation whose value group is Z, it is called the normalized valuation of p and denoted V p .

We recall that, for a non-singular curve C , there is a one-to-one correspondance between places of K(C ) and Galois orbit of points on C . The degree of a place p is the number of points in the corresponding orbit, we denote it by Deg(p).

The divisor group Div(C ) of C (over K) is defined as the free abelian group over Σ K(C ) . An element D of Div(C ) is expressed as:

D = p∈Σ K(C ) n p (p),
where each n p ∈ Z and n p = 0 for all but finitely many places p. Since each place corresponds to a Galois orbit of points, a divisor D can also be given in the alternative form: D = P ∈C /Fq n P (P ),

where each n P ∈ Z, n P = 0 for all but finitely many points and n P = n Q if P and Q belong to the same Galois orbit of points. A divisor D is said to be prime when D = (p) for a place p ∈ Σ K(C ) . The degree of a divisor D is defined as:

Deg(D) = p∈Σ K(C ) n p Deg(p) = P ∈C /Fq n P .
In this paper, a degree-0 divisor that is the difference between a prime divisor and the right number of times the point at infinity O is defined as an elementary divisor.

In particular, any elementary divisor associated to a point Q ∈ C /F q d is a divisor of the form:

d-1 i=0 π i (Q) -d(O).
A divisor D is called effective when n p ≥ 0 for all p. Any divisor D can be uniquely written as a difference of two effective divisors in the form D = D 0 -D ∞ , where:

D 0 = p ∈ Σ K(C ) n p ≥ 0 n p (p) and D ∞ = p ∈ Σ K(C ) n p < 0 -n p (p).
equations, we again use linear algebra to compute the logarithms of the elements of G.

Note that the probability to find a good relation is 3/4 when q grows. We thus expect 3q 2 /4 equations in q 2 /4.

Note that the pairs (A, B) that fail to give an equation are nonetheless useful! Indeed, a pair (A, B) of sieving polynomials fails if [A, B] leads to a divisor with height precisely 4. It means that after obtain the logarithm of elements of G we can derive the logarithm of these extra divisors for free. B.1. Construction of groups with one compelled point. Following the idea of the special group G, we would like to construct small other groups of divisors that have two properties. First, for each group, we need to be able to create relations involving only heigh-4 divisors from this group on the left, possibly with divisors of lower height. Second, we need to control the splitting probability of the bracket on the right of the equation. We proceed using compelled points.

How to choose our generators g 1 , g 2 and g 3 in this case ? We recall that the naive height-4 sieving is based on the monomials 1, U, V, U V . Since there is no reason to favor nor U neither V , we propose to preserve symmetry between the two variables, writing:

g 1 = U V + k 1 U g 2 = U V + k 2 V g 3 = 1.
where k 1 and k 2 are in the base field F q . Defining again groups:

G k1,k2 = {Ξ(g 1 + αg 2 + βg 3 ) | α, β ∈ F q }
with q 2 divisors each, we sieve on pairs of polynomials (A, B) such that A = g 1 +αg 2 and B = g 1 + βg 3 where α, β ∈ F q . On the left side all divisors have height lower than 4 and belong to G k1,k2 . On the right side, we are left with a bracket [A, B] leading to a height lower than 8. To decrease this height we consider the brackets:

[g 1 , g 2 ] = k 1 [U, U V ] + k 2 [U V , V ] + k 1 k 2 [U, V ] [g 1 , g 3 ] = V W + k 1 V -U V + k 1 U [g 2 , g 3 ] = V W + k 2 W -U V + k 2 V
Note that [A, B] is a linear combination of these brackets and that the last two ones are associated to divisors of height lower than 4. Thus, removing a point in div

(Φ * ([g 1 , g 2 ])) will suffice. Let us look at k 1 [U, U V ] + k 2 [U V , V ] + k 1 k 2 [U, V ] in details. Calling c f the coefficient in F q of the leading monomial 6 of [g 1 , g 2 ]
for the denominator of any fraction f , we see that we can force k

1 c [U,U V ] + k 2 c [U V ,V ] + k 1 k 2 c [U,V ] = 0 in F q . We underline that for any fixed constant k 1 = -c [U V ,V ] c -1 [U,V ]
there exists a unique k 2 such that the previous equality is verified. It means that we create q -1 such groups. Besides, this annihilates the leading monomial so decreases the weighted degree of [g 1 , g 2 ] and leads to remove a point in the associated divisor of [A, B]. Hence, we are left with a residual height of 7. We want the corresponding divisor to be written as a sum of divisors of height 3 at most. The heuristic probability to get a good relation is so equal to:

1 -(1/7 + 1/6 + 1/5 + 1/4) ≈ 0.2405 as q tends to infinity. 6 Considering the weighted degree in X and Y of each monomial. This is slightly too low for the purpose. As a consequence, we need either to improve the group construction or to make good use of the equations with a single height-4 divisor in the bracket. Nevertheless, since 0.24 is close to 1/4, it is conceivable that we can find enough relations in practice. We decided to test it and we computed all the discrete logarithms up to height-5 for the target finite field F 3 1345 = F 243 269 with this method.

Remark 4. It is useful to know that:

[U, U V ] = U V (V -W ) [U V , V ] = V W (V -W ) [U, V ] = V 2 -U W B.2.
Interaction with the action of Frobenius. Looking at our groupings, we see that we have built a total of q different ones (including the special group G.

Since each grouping contains about q 2 /4, the computations (if successful) gives us about q 3 /4 logarithms of height 4. This is much less than the total expected number which is close to q 4 /4. However, the action of the Frobenius potentially multiply these logarithms by a factor of k. For practical, we heuristically assume that this is the case. The fact that we were able to compute the logarithms of all height-4 divisors for F 3 1345 supports this assumption.

B.3. Going to height 5. We continue the extension to height 5 in similar fashion. Since, this requires more degree of freedom, we no longer need to use compelled points. Instead, we sieve on more general polynomials of the forms

A = U V + a U U + a 1 and B = U V + b V V + b 1 .
On the left-hand side, all factors of the form A -αB have height 4. Thus they decompose in divisors of height at most 4 and their logarithms can be directly obtained. On the right-hand side, the bracket has height at most 8. We expect that it contains an elementary divisor of height 5 with probability close to 1/5. As a consequence, we obtain about q 4 /5 divisors of height 5 without performing any linear algebra. Again, thanks to the action of Frobenius, we expect to recover an overwhelming fraction of divisors of height 5. This turn out to work for our example F 3 1345 . Appendix C. Verification of discrete logarithms for the target field F 3 1345 . Here is a Magma code that constructs the target finite field of our example thanks to an elliptic curve and gives some discrete logarithms. E-mail address: antoine.joux@m4x.org E-mail address: cecile.pierrot@inria.fr

Figure 2 .

 2 Figure 2. Commutative diagram of our algorithm.

4. 3 . 2 .

 32 Right side. On the right part of the diagram, divisors are given through the extra variable W . We can compute the corresponding height exactly as for U . Again it gives: h(Ξ(W )) = 2.

Figure 4 .

 4 Figure 4. Tower of elliptic curves extensions in the elliptic zigzag descent. The path in green represents how we decompose p z in smaller degree places over higher extensions during the algorithm.

  [A, B -λA] * = [A, B] * . Thus we can fix one component of the leading coefficient of B to 0. Then, using [A, λB] * = λ [A, B] * we can fix one component of another coefficient of B to 1. Finally, thanks to the relation [A -λB, B] * = [A, B] * , we can set the corresponding component in A to 0.

1 g f 3

 3 p o l <x>:=Poly nomia lRin g (GF( 3 ) ) ; 2 g f e x t <a>:=ext<GF( 3 ) | x^5-x+1>; 3 g f 2 p o l <x2>:=Pol ynom ialRi ng ( g f e x t ) ( ( q^k ) -1) d i v c o f ; 14

  I d e a l C := R a d i c a l D e c o m p o s i t i o n ( I d e a l ( [ f 1 , f 2 , f 3 ] ) ) [ 1 ] ; 37 38 // Add F r o b e n i u s c o n s t r a i n t t o g e t f i e l d d e f i n i t i o n ( i n V b e c a u s e o f t h e c h o s e n o r d e r i n g o f t h e p o l y n o m i a l r i n g ) 39 F i e l d D e f := G r o e b n e r B a s i s ( B a s i s ( I d e a l C ) c a t [ V-U^q ,W -V^q ] ) [ 3 ] ; 40 B i g F i e l d <v>:=ext<g f e x t | U n i v a r i a t e P o l y n o m i a l ( F i e l d D e f ) >; 41 Eext := BaseChange (E , B i g F i e l d ) ; 42 b o o l ,Q:= I s P o i n t ( Eext , v ) * D i v i s o r ( curPdoub )-D i v i s o r ( 2 * curPdoub )-D i v i s o r ( ZeroPt ) ; 74 b o o l , f n := I s P r i n c i p a l (tmpD) a n i t y c h e c k : F r o b e n i u s c o r r e c t n e s s a f t e r mapping t o B i g F i e l d 86 L0:= MyTatePairing ( P0 , k , c o f ) ; 87 L t e s t := MyTatePairing ( 1 4 * P0 , k , c o f ) ; 88 a s s e r t L t e s t eq L0^(&+[q^i : i i n [ 0 . . 1 3 ] ] ) ; 89 90 91 // C h a l l e n g e Log from Pi 92 93 R:= R e a l F i e l d ( 2 0 0 0 ) ; 94 p i v a l := Pi (R) ; 95 96 Z:=&+[( F l o o r ( p i v a l * 3^( v a l +1) ) mod 3 ) * v ^( v a l d i v 5 ) * a ^( v a l mod 5 :=(Z * ( v+1) ^9586 * ( v+a ) ^134) ; 99 100 tmp1 : = ( 1 ) * v^134+(-1+a ^3) * v^133+(a-a ^4) * v^132+(-1-a+a^2+a ^4) * v^131+( a ^3-a ^4) * v^130+(-a-a^3-a ^4) * v^129+( a+a^2+a^3-a ^4) * v^128+(a-a^3+a ^4) * v^127+(-1+a ^2) * v^126+(-1-a^2+a ^3) * v^125+(1-a^2-a^3-a ^4) * v^124+(-a -a^3-a ^4) * v^123+(-a+a^2+a^3-a ^4) * v^122+(-a-a^2+a ^3) * v^121+(a-a^2+a ^3-a ^4) * v^120+(-1+a-a^2-a ^4) * v^119+( a^2+a^3+a ^4) * v^118+(-a-a^2-a ^4) * v^117+(-1-a^2-a^3-a ^4) * v^116+(-a^2+a ^3) * v^115+(a-a^2+a^3-a ^4) * v^114+(1+a-a^2+a ^3) * v^113+(-1-a+a ^3) * v^112+(1+a+a^2+a^3+a ^4) * v ^111+(a-a ^3) * v^110+(-1-a^2-a^3+a ^4) * v^109+( a^2-a^3+a ^4) * v^108+(1-a -a^2+a ^3) * v^107+(1-a+a^2+a ^3) * v^106+( a^2-a ^3) * v^105+(-1+a^2+a^3-a ^4) * v^104+(-a-a ^4) * v^103+(1+a+a^3-a ^4) * v^102+(-1+a-a^2+a^3+a ^4) * v ^101+( a+a^3+a ^4) * v^100+(-1+a+a^2-a^3+a ^4) * v^99+(1-a+a^2-a ^3) * v ^98+(1+a^3-a ^4) * v^97+(-1+a+a ^4) * v^96+(-1-a-a^2-a ^3) * v^95+(-1+a-a ^2+a^3+a ^4) * v^94+(a^2+a ^4) * v^93+(-1+a-a^2-a^3+a ^4) * v^92+(-a-a^2-a ^3-a ^4) * v^91+(-a+a^2-a^3+a ^4) * v^90+(a ^3) * v^89+(-1-a ^2) * v^88+(a-a ^2+a^3+a ^4) * v^87+(-1-a+a ^2) * v^86+(1+a^2+a^3-a ^4) * v^85+(1+a+a^2+a ^3-a ^4) * v^84+(a-a^2+a ^4) * v^83+(-1-a ^4) * v^82+(a ^3) * v^81+(-1-a-a ^3) * v^80+(-1+a+a^2-a ^4) * v^79+(a ^4) * v^78+(1-a+a^2+a^3-a ^4) * v^77+(1+a+a ^2+a^3-a ^4) * v^76+(-1-a+a^2-a^3-a ^4) * v^75+(-1+a^3+a ^4) * v^74+(1-a^2-a^3+a ^4) * v^73+(1+a-a^3+a ^4) * v^72+(a-a ^3) * v^71+(1+a^3+a ^4) * v^70+(a-a^2+a^3-a ^4) * v^69+(-1+a-a^2-a ^4) * v^68+(1+a-a ^4) * v^67+(-a^2+a ^4) * v ^66+(1+a+a^2-a^3+a ^4) * v^65+(a-a^2+a ^4) * v^64+(-1-a+a^2+a^3-a ^4) * v ^63+(-1+a^2+a ^4) * v^62+(1-a+a^3-a ^4) * v^61+(-1+a+a^2-a^3+a ^4) * v ^60+(1-a+a^3-a ^4) * v^59+(-1+a-a^2-a^3+a ^4) * v^58+(-1-a+a^3+a ^4) * v ^57+(-a^2-a ^4) * v^56+(a^2-a ^4) * v ^55+(1) * v^54+(-1+a^2-a^3+a ^4) * v ^53+(a+a^2-a^3-a ^4) * v^52+(a+a^2-a^3-a ^4) * v^51+(a^3-a ^4) * v^50+(1-a ^4) * v^49+(1-a-a^2+a ^3) * v^48+(1+a+a ^3) * v^47+(-1+a^2-a^3+a ^4) * v ^46+(1-a^2+a ^3) * v^45+(1-a+a^2+a^3+a ^4) * v^44+(a-a ^2) * v^43+(1+a^2+a ^3) * v^42+(-1+a-a^2+a ^4) * v^41+(1+a^2-a^3+a ^4) * v^40+(-1+a^2+a ^3) * v ^39+(1-a-a^2+a^3+a ^4) * v^38+(-1+a^2-a ^3) * v^37+(-a-a^3-a ^4) * v^36+(a^2+a^4) * v^35+(a^3-a ^4) * v^34+(1+a+a^3-a ^4) * v^33+(-a ^2) * v^32+(1-a+a ^2+a^3+a ^4) * v^31+(1+a-a^3-a ^4) * v^30+(-1-a-a ^3) * v^29+(1-a^2-a^3-a ^4) * v^28+(-1+a ^3) * v^27+(-1+a^2-a ^3) * v^26+(1-a+a^2-a^3-a ^4) * v ^25+(-1-a-a ^2) * v^24+(-1+a-a^3+a ^4) * v^23+(1+a^2-a ^3) * v^22+(-1+a-a ^2-a^3+a ^4) * v^21+(-1+a-a ^3) * v^20+(-a-a ^3) * v^19+(1+a^3+a ^4)* v ^18+(1+a-a^2+a ^4) * v^17+(a-a^2-a ^3) * v ^16+(1) * v^15+(-a^2+a ^3) * v ^14+(1+a-a ^3) * v^13+(1-a+a^2+a ^4) * v^12+(-1-a ^3) * v^11+(-1-a-a^2+a^3a ^4) * v^10+(-a ^4) * v^9+(1+a ) * v^8+(-1+a ^2) * v^7+(-1+a+a^2+a^3+a ^4) * v ^6+(1-a-a^2-a ^3) * v^5+(a-a^3-a ^4) * v^4+(-a+a^2+a^3-a ^4) * v^3+(1-a^2-a ^3) * v^2+(-1+a+a^2-a^3-a ^4) * v+(-1) e r t ( v+a ) ^( k * c o f ) eq L0^l o g v p l u s a ; 133 134 // T e s t i n g a d e g r e e 18 l o g example ( f i f t h p o l y n o m i a l i n t h e f a c t o r i s a t i o n o f tmp1pol ) 135 img := E v a l u a t e ( F a c t o r i z a t i o n ( tmp1pol ) [ 5 ] [ 1 ] , v ) e r i f y c o r r e c t n e s s o f t h e l o g 148 a s s e r t img^c o f eq L0^t e s t l o g ;

Not 4(t + 1) since each of 1, U , V and U V are included twice.

Be careful, here we assume that the characteristic differs from 2. If not, we just consider the corresponding degree-2 place.

Indeed, one can use Wan's theorem[START_REF] Wan | Generators and irreducible polynomials over finite fields[END_REF] Theo 5.1] to ensure that any field element is equivalent to an irreducible polynomial of degree a power of 2 only slightly larger than the extension degree k.

There are a couple of groups with slightly different performances but this does not affect the overall performance.

Since magma was not installed on our main server, the computation of Gröbner basis were delegated to a smaller server. However, during that time the main server was simply waiting for the result.

This work has been supported in part by the European Union as H2020 Programme under grant agreement number ERC-669891.

The degree map from Div(C ) to Z is a group morphism. Its kernel is denoted Div 0 (C ) and called the group of degree-0 divisors of C , it is a subgroup of Div(C ).

We define the map div that sends an element f ∈ K(C ) * to a divisor in the following way:

A divisor associated to a function in the above way is called a principal divisor. The image of div, i.e. the set of all principal divisors, is denoted Princ(C ). All principal divisors have degree 0 and Princ(C ) is a subgroup of Div 0 (C ). Every principal divisor can also be written as a difference of effective divisors as:

The places (or points) that occur in div(f ) 0 or div(f ) ∞ are respectively called the zeroes or poles of f . Note that for two functions f and g of K(C ) * , we have div(f ) = div(g) if and only if there exists an element α ∈ K * such that g = α f . Since Princ(C ) is a subgroup of Div 0 (C ), we can form the quotient group, which is called the Picard group (or divisor class group) of C and denoted Pic 0 (C ). Two divisors have the same representative in the Picard group if and only if their difference is principal.

Appendix B. Relations for factor base extension. Let us describe our decomposition in groups to extend the factor base to all elementary divisors of height equal or lower than 4. The idea is to write a partition of q groups with q 2 elements in each and to be able to decrease the height of the divisor associated to the bracket on the right again. To illustrate the process, we define a first group with the monomials:

Defining then G as all the linear combinations of these three monomials with coefficients in F q permits to set our first (special) group as:

All the divisors in the special group have height lower than 4. We now sieve on pairs of polynomials (A, B) such that A = g 1 + αg 2 and B = g 1 + βg 3 where α, β ∈ F q . On the left side it is clear that all polynomials raised in the product belong to G. So all the divisors in the corresponding sum on the left side have height lower than 4 (see Table 4.3.1) and belong to G. On the right side, we are left with a bracket [A, B] leading to a height lower than 8. Again, the probability that it splits into divisors with a height lower than 3 is too low. Yet, computing the brackets: