Razvan Barbulescu

Pierrick Gaudry

Antoine Joux

Emmanuel Thomé

A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic

The difficulty of computing discrete logarithms in fields F q k depends on the relative sizes of k and q. Until recently all the cases had a sub-exponential complexity of type L(1/3), similar to the factorization problem. In 2013, Joux designed a new algorithm with a complexity of L(1/4 + ǫ) in small characteristic. In the same spirit, we propose in this article another heuristic algorithm that provides a quasi-polynomial complexity when q is of size at most comparable with k. By quasi-polynomial, we mean a runtime of n O(log n) where n is the bit-size of the input. For larger values of q that stay below the limit L q k (1/3), our algorithm loses its quasi-polynomial nature, but still surpasses the Function Field Sieve.

Introduction

The discrete logarithm problem (DLP) was first proposed as a hard problem in cryptography in the seminal article of Diffie and Hellman [START_REF] Diffie | New directions in cryptography[END_REF]. Since then, together with factorization, it has become one of the two major pillars of public key cryptography. As a consequence, the problem of computing discrete logarithms has attracted a lot of attention. From an exponential algorithm in 1976, the fastest DLP algorithms have been greatly improved during the past 35 years. A first major progress was the realization that the DLP in finite fields can be solved in subexponential time, i.e. L(1/2) where L N (α) = exp O((log N ) α (log log N ) 1-α ) . The next step further reduced this to a heuristic L(1/3) running time in the full range of finite fields, from fixed characteristic finite fields to prime fields [START_REF] Adleman | A subexponential algorithm for the discrete logarithm problem with applications to cryptography[END_REF][START_REF] Coppersmith | Fast evaluation of logarithms in fields of characteristic two[END_REF][START_REF] Gordon | Discrete logarithms in GF(p) using the number field sieve[END_REF][START_REF] Adleman | The function field sieve[END_REF][START_REF] Joux | The function field sieve in the medium prime case[END_REF][START_REF] Joux | The number field sieve in the medium prime case[END_REF].

Recently, practical and theoretical advances have been made [START_REF] Joux | Faster index calculus for the medium prime case. Application to 1175bit and 1425-bit finite fields[END_REF][START_REF] Göloglu | On the Function Field Sieve and the impact of higher splitting probabilities[END_REF][START_REF] Joux | A new index calculus algorithm with complexity L(1/4 + o(1)) in very small characteristic[END_REF] with an emphasis on small to medium characteristic finite fields and composite degree extensions. The most general and efficient algorithm [START_REF] Joux | A new index calculus algorithm with complexity L(1/4 + o(1)) in very small characteristic[END_REF] gives a complexity of L(1/4 + o(1)) when the characteristic is smaller than the square root of the extension degree. Among the ingredients of this approach, we find the use of a very particular representation of the finite field; the use of the so-called systematic equation 1 ; and the use of algebraic resolution of bilinear polynomial systems in the individual logarithm phase.

In this work, we present a new discrete logarithm algorithm, in the same vein as in [START_REF] Joux | A new index calculus algorithm with complexity L(1/4 + o(1)) in very small characteristic[END_REF] that uses an asymptotically more efficient descent approach. The main result gives a quasi-polynomial heuristic complexity for the DLP in finite fields of small characteristic. By quasi-polynomial, we mean a complexity of type n O(log n) where n is the bit-size of the cardinality of the finite field. Such a complexity is smaller than any L(ǫ) for ǫ > 0. It remains super-polynomial in the size of the input, but offers a major asymptotic improvement compared to L(1/4 + o(1)).

The key features of our algorithm are the following.

-We keep the field representation and the systematic equations of [START_REF] Joux | A new index calculus algorithm with complexity L(1/4 + o(1)) in very small characteristic[END_REF].

-The algorithmic building blocks are elementary. In particular, we avoid the use of Gröbner basis algorithms. -The complexity result relies on three key heuristics: the existence of a polynomial representation of the appropriate form; the fact that the smoothness probabilities of some non-uniformly distributed polynomials are similar to the probabilities for uniformly random polynomials of the same degree; and the linear independence of some finite field elements related to the action of PGL 2 (F q ).

The heuristics are very close to the ones used in [START_REF] Joux | A new index calculus algorithm with complexity L(1/4 + o(1)) in very small characteristic[END_REF]. In addition to the arguments in favor of these heuristics already given in [START_REF] Joux | A new index calculus algorithm with complexity L(1/4 + o(1)) in very small characteristic[END_REF], we performed some experiments to validate them on practical instances.

Although we insist on the case of finite fields of small characteristic, where quasi-polynomial complexity is obtained, our new algorithm improves the complexity of discrete logarithm computations in a much larger range of finite fields.

More precisely, in finite fields of the form F q k , where q grows as L q k (α), the complexity becomes L q k (α + o(1)). As a consequence, our algorithm is asymptotically faster than the Function Field Sieve algorithm in almost all the range previously covered by this algorithm. Whenever α < 1/3, our new algorithm offers the smallest complexity. For the limiting case L(1/3, c), the Function Field Sieve remains more efficient for small values of c, and the Number Field Sieve is better for large values of c (see [START_REF] Joux | The number field sieve in the medium prime case[END_REF]). This article is organized as follows. In Section 2, we state the main result, and discuss how it can be used to design a complete discrete logarithm algorithm. In Section 3, we analyze how this result can be interpreted for various types of finite fields, including the important case of fields of small characteristic. Section 4 is devoted to the description of our new algorithm. It relies on heuristics that are discussed in Section 5, from a theoretical and a practical point of view. Before getting to the conclusion, in Section 6, we propose a few variants of the algorithm.

1 While the terminology is similar, no parallel is to be made with the systematic equations as defined in early works related to the computation discrete logarithms in F2n , as [START_REF] Blake | Computing logarithms in finite fields of characteristic two[END_REF].

Main result

We start by describing the setting in which our algorithm applies. It is basically the same as in [START_REF] Joux | A new index calculus algorithm with complexity L(1/4 + o(1)) in very small characteristic[END_REF]: we need a large enough subfield, and we assume that a sparse representation can be found. This is formalized in the following definition.

Definition 1 A finite field K admits a sparse medium subfield representation if

it has a subfield of q 2 elements for a prime power q, i.e. K is isomorphic to F q 2k with k ≥ 1; -there exist two polynomials h 0 and h 1 over F q 2 of small degree, such that h 1 X q -h 0 has a degree k irreducible factor.

In what follows, we will assume that all the fields under consideration admit a sparse medium subfield representation. Furthermore, we assume that the degrees of the polynomials h 0 and h 1 are uniformly bounded by a constant δ. Later, we will provide heuristic arguments for the fact that any finite field of the form F q 2k with k ≤ q + 2 admits a sparse medium subfield representation with polynomials h 0 and h 1 of degree at most 2. But in fact, for our result to hold, allowing the degrees of h 0 and h 1 to be bounded by any constant δ independent of q and k or even allowing δ to grow slower than O(log q) would be sufficient.

In a field in sparse medium subfield representation, elements will always be represented as polynomials of degree less than k with coefficients in F q 2 . When we talk about the discrete logarithm of such an element, we implicitly assume that a basis for this discrete logarithm has been chosen, and that we work in a subgroup whose order has no small irreducible factor (we refer to the Pohlig-Hellman algorithm [START_REF] Pohlig | An improved algorithm for computing logarithms over GF (p) and its cryptographic signifiance[END_REF] to limit ourselves to this case).

Proposition 2 Let K = F q 2k be a finite field that admits a sparse medium subfield representation. Under the heuristics explained below, there exists an algorithm whose complexity is polynomial in q and k and which can be used for the following two tasks.

1. Given an element of K represented by a polynomial P ∈ F q 2 [X] with 2 ≤ deg P ≤ k -1, the algorithm returns an expression of log P (X) as a linear combination of at most O(kq 2 ) logarithms log P i (X) with deg P i ≤ ⌈ 1 2 deg P ⌉ and of log h 1 (X). 2. The algorithm returns the logarithm of h 1 (X) and the logarithms of all the elements of K of the form X + a, for a in

F q 2 .
Before the presentation of the algorithm, which is made in Section 4, we explain how to use it as a building block for a complete discrete logarithm algorithm.

Let P (X) be an element of K for which we want to compute the discrete logarithm. Here P is a polynomial of degree at most k -1 and with coefficients in F q 2 . We start by applying the algorithm of Proposition 2 to P . We obtain a relation of the form log P = e 0 log h 1 + e i log P i ,

where the sum has at most κq 2 k terms for a constant κ and the P i 's have degree at most ⌈ 1 2 deg P ⌉. Then, we apply recursively the algorithm to the P i 's, thus creating a descent procedure where at each step, a given element P is expressed as a product of elements, whose degree is at most half the degree of P (rounded up) and the arity of the descent tree is in O(q 2 k).

At the end of the process, the logarithm of P is expressed as a linear combination of the logarithms of h 1 and of the linear polynomials, for which the logarithms are computed with the algorithm in Proposition 2 in its second form.

We are left with the complexity analysis of the descent process. Each internal node of the descent tree corresponds to one application of the algorithm of Proposition 2, therefore each internal node has a cost which is bounded by a polynomial in q and k. The total cost of the descent is therefore bounded by the number of nodes in the descent tree times a polynomial in q and k. The depth of the descent tree is in O(log k). The number of nodes of the tree is then less than or equal to its arity raised to the power of its depth, which is (q 2 k) O(log k) . Since any polynomial in q and k is absorbed in the O() notation in the exponent, we obtain the following result.

Theorem 3 Let K = F q 2k be a finite field that admits a sparse medium subfield representation. Assuming the same heuristics as in Proposition 2, any discrete logarithm in K can be computed in a time bounded by max(q, k) O(log k) .

Consequences for various ranges of parameters

We now discuss the implications of Theorem 3 depending on the properties of the finite field F Q where we want to compute discrete logarithms in the first place. The complexities will be expressed in terms of log Q, which is the size of the input.

Three cases are considered. In the first one, the finite field admits a sparse medium subfield representation, where q and k are almost equal. This is the optimal case. Then we consider the case where the finite field has small (maybe constant) characteristic. And finally, we consider the case where the characteristic is getting larger so that the only available subfield is a bit too large for the algorithm to have an optimal complexity.

In the following, we always assume that for any field of the form F q 2k , we can find a sparse medium subfield representation.

3.1 Case where the field is F q 2k , with q ≈ k The finite fields F Q = F q 2k for which q and k are almost equal are tailored for our algorithm. In that case, the complexity of Theorem 3 becomes q O(log q) . Since Q ≈ q 2q , we have q = (log Q) O(1) . This gives an expression of the form 2 O((log log Q) 2 ) , which is sometimes called quasi-polynomial in complexity theory.

Corollary 4 For finite fields of cardinality Q = q 2k with q + O(1) ≥ k and q = (log Q) O (1) , there exists a heuristic algorithm for computing discrete logarithms in quasi-polynomial time

2 O((log log Q) 2 ) .
We mention a few cases which are almost directly covered by Corollary 4. First, we consider the case where Q = p n with p a prime bounded by (log Q) O (1) , and yet large enough so that n ≤ (p + δ). In this case F Q , or possibly F Q 2 if n is odd, can be represented in such a way that Corollary 4 applies.

Much the same can be said in the case where n is composite and factors nicely, so that F Q admits a large enough subfield F q with q = p m . This can be used to solve certain discrete logarithms in, say, F 2 n for adequately chosen n (much similar to records tackled by [START_REF] Joux | Discrete logarithm in GF(2 1778[END_REF][START_REF] Göloglu | Discrete logarithm in GF[END_REF][START_REF] Joux | Discrete logarithm in GF(2 4080[END_REF][START_REF] Göloglu | Discrete logarithm in GF(2 6120[END_REF][START_REF] Joux | Discrete logarithm in GF(2 6168[END_REF]).

Case where the characteristic is polynomial in the input size

Let now F Q be a finite field whose characteristic p is bounded by (log Q) O (1) , and let n = log Q/ log p, so that Q = p n . While we have seen that Corollary 4 can be used to treat some cases, its applicability might be hindered by the absence of an appropriately sized subfield: p might be as small as 2, and n might not factor adequately. In those cases, we use the same strategy as in [START_REF] Joux | A new index calculus algorithm with complexity L(1/4 + o(1)) in very small characteristic[END_REF] and embed the discrete logarithm problem in F Q into a discrete logarithm problem in a larger field.

Let k be n if n is odd and n/2 if n is even. Then, we set q = p ⌈log p k⌉ , and we work in the field F q 2k . By construction this field contains F Q (because p|q and n|2k) and it is in the range of applicability of Theorem 3. Therefore, one can solve a discrete logarithm problem in F Q in time max(q, k) O(log k) . Rewriting this complexity in terms of Q, we get log p (Q) O(log log Q) . And finally, we get a similar complexity result as in the previous case. Of course, since we had to embed in a larger field, the constant hidden in the O() is larger than for Corollary 4.

Corollary 5 For finite fields of cardinality Q and characteristic bounded by log(Q) O (1) , there exists a heuristic algorithm for computing discrete logarithms in quasi-polynomial time

2 O((log log Q) 2 ) .
We emphasize that the case F 2 n for a prime n corresponds to this case. A direct consequence of Corollary 5 is that discrete logarithms in F 2 n can be computed in quasi-polynomial time 2 O((log n) 2 ) .

Case where q

= L q 2k (α)
If the characteristic of the base field is not so small compared to the extension degree, the complexity of our algorithm does not keep its nice quasi-polynomial form. However, in almost the whole range of applicability of the Function Field Sieve algorithm, our algorithm is asymptotically better than FFS.

We consider here finite fields that can be put into the form F Q = F q 2k , where q grows not faster than an expression of the form L Q (α). In the following, we assume that there is equality, which is of course the worst case. The condition can then be rewritten as

log q = O((log Q) α (log log Q) 1-α ) and therefore k = log Q/ log q = O((log Q/ log log Q) 1-α ).
In particular we have k ≤ q + δ, so that Theorem 3 can be applied and gives a complexity of q O(log k) . This yields the following result.

Corollary 6 For finite fields of the form F Q = F q 2k where q is bounded by L Q (α), there exists a heuristic algorithm for computing discrete logarithms in subexponential time

L Q (α) O(log log Q) .
This complexity is smaller than L Q (α ′ ) for any α ′ > α. Hence, for any α < 1/3, our algorithm is faster than the best previously known algorithm, namely FFS and its variants.

Main algorithm: proof of Proposition 2

The algorithm is essentially the same for proving the two points of Proposition 2. The strategy is to find relations between the given polynomial P (X) and its translates by a constant in F q 2 . Let D be the degree of P (X), that we assume to be at least 1 and at most k -1.

The key to find relations is the systematic equation:

X q -X = a∈Fq (X -a). (1)
We like to view Equation (1) as involving the projective line P 1 (F q ). Let S = {(α, β)} be a set of representatives of the q + 1 points (α : β) ∈ P 1 (F q ), chosen adequately so that the following equality holds.

X q Y -XY q = (α,β)∈S (βX -αY ).
(

) 2
To make translates of P (X) appear, we consider the action of homographies.

Any matrix m = a b c d acts on P (X) with the following formula:

m • P = aP + b cP + d .
In the following, this action will become trivial if the matrix m has entries that are defined over F q . This is also the case if m is non-invertible. Finally, it is clear that multiplying all the entries of m by a non-zero constant does not change its action on P (X). Therefore the matrices of the homographies that we consider are going to be taken in the following set of cosets:

P q = PGL(F q 2 )/ PGL(F q ).
(Note that in general PGL 2 (F q ) is not a normal subgroup of PGL 2 (F q 2 ), so that P q is not a quotient group.)

To each element m = a b c d ∈ P q , we associate the equation (E m ) obtained by substituting aP + b and cP + d in place of X and Y in Equation ( 2).

(aP + b) q (cP + d) -(aP + b)(cP + d) q = (α,β)∈S β(aP + b) -α(cP + d) (E m ) = (α,β)∈S (-cα + aβ)P -(dα -bβ) = λ (α,β)∈S P -x(m -1 • (α : β)).
This sequence of formulae calls for a short comment because of an abuse of notation in the last expression. First, λ is the constant in F q 2 which makes the leading terms of the two sides match. Then, the term P -x(m -1 • (α : β)) denotes P -u when m -1 • (α : β) = (u : 1) (whence we have u = dα-bβ -cα+aβ ), or 1 if m -1 • (α : β) = ∞. The latter may occur since when a/c is in F q , the expression -cα + aβ vanishes for a point (α : β) ∈ P 1 (F q ) so that one of the factors of the product contains no term in P (X).

Hence the right-hand side of Equation (E m ) is, up to a multiplicative constant, a product of q+1 or q translates of the target P (X) by elements of F q 2 . The equation obtained is actually related to the set of points m -1 • P 1 (F q ) ⊂ P 1 (F q 2 ).

The polynomial on the left-hand side of (E m ) can be rewritten as a smaller degree equivalent. For this, we use the special form of the defining polynomial: in K we have X q ≡ h0(X) h1(X) . Let us denote by ã the element a q when a is any element of F q 2 . Furthermore, we write P (X) the polynomial P (X) with all its coefficients raised to the power q. The left-hand side of (E m ) is

(ã P (X q ) + b)(cP (X) + d) -(aP (X) + b)(c P (X q ) + d),
and using the defining equation for the field K, it is congruent to

L m := ã P h 0 (X) h 1 (X) + b (cP (X) + d) -(aP (X) + b) c P h 0 (X) h 1 (X) + d .
The denominator of L m is a power of h 1 and its numerator has degree at most (1 + δ)D where δ = max(deg h 0 , deg h 1 ). We say that m ∈ P q yields a relation if this numerator of L m is ⌈D/2⌉-smooth.

To any m ∈ P q , we associate a row vector v(m) of dimension q2 + 1 in the following way. Coordinates are indexed by µ ∈ P 1 (F q 2 ), and the value associated to µ ∈ F q 2 is 1 or 0 depending on whether P -x(µ) appears in the right-hand side of Equation (E m ). Note that exactly q + 1 coordinates are 1 for each m. Equivalently, we may write

v(m) µ∈P 1 (F q 2 ) = 1 if µ = m -1 • (α : β) with (α : β) ∈ P 1 (F q ), 0 otherwise. ( 3
)
We associate to the polynomial P a matrix H(P ) whose rows are the vectors v(m) for which m yields a relation, taking at most one matrix m in each coset of P q . The validity of Proposition 2 crucially relies on the following heuristic.

Heuristic 7 For any P (X), the set of rows v(m) for cosets m ∈ P q that yield a relation form a matrix which has full rank q 2 + 1.

As we will note in Section 5, the matrix H(P ) is heuristically expected to have Θ(q 3 ) rows, where the implicit constant depends on δ. This means that for our decomposition procedure to work, we rely on the fact that q is large enough (otherwise H(P ) may have less than q 2 + 1 rows, which precludes the possibility that it have rank q 2 + 1).

The first point of Proposition 2, where we descend a polynomial P (X) of degree D at least 2, follows by linear algebra on this matrix. Since we assume that the matrix has full rank, then the vector (. . . , 0, 1, 0, . . .) with 1 corresponding to P (X) can be written as a linear combination of the rows. When doing this linear combination on the equations (E m ) corresponding to P we write log P (X) as a linear combination of log P i where P i (x) are the elements occurring in the left-hand sides of the equations. Since there are O(q 2 ) columns, the elimination process involves at most O(q 2 ) rows, and since each row corresponds to an equation (E m ), it involves at most deg L m ≤ (1 + δ)D polynomials in the lefthand-side 2 . In total, the polynomial D is expressed by a linear combination of at most O(q 2 D) polynomials of degree less than ⌈D/2⌉. The logarithm of h 1 (X) is also involved, as a denominator of L m . We have not made precise the constant in F * q 2 which occurs to take care of the leading coefficients. Since discrete logarithms in F * q 2 can certainly be computed in polynomial time in q, this is not a problem.

Since the order of PGL 2 (F q i ) is q 3i -q i , the set of cosets P q has q 3 + q elements. For each m ∈ P q , testing whether (E m ) yields a relation amounts to some polynomial manipulations and a smoothness test. All of them can be done in polynomial time in q and the degree of P (X) which is bounded by k. Finally, the linear algebra step can be done in O(q 2ω ) using asymptotically fast matrix multiplication algorithms, or alternatively O(q 5 ) operations using sparse matrix techniques. Indeed, we have q + 1 non-zero entries per row and a size of q 2 + 1. Therefore, the overall cost is polynomial in q and k as claimed.

For the second part of Proposition 2 we replace P by X during the construction of the matrix. In that case, both sides of the equations (E m ) involve only linear polynomials. Hence we obtain a linear system whose unknowns are log(X + a) with a ∈ F q 2 . Since Heuristic 7 would give us only the full rank of the system corresponding to the right-hand sides of the equations (E m ), we have to rely on a specific heuristic for this step: Heuristic 8 The linear system constructed from all the equations (E m ) for P (X) = X has full rank.

Assuming that this heuristic holds, we can solve the linear system and obtain the discrete logarithms of the linear polynomials and of h 1 (X).

Supporting the heuristic argument in the proof

For Heuristic 7, we propose two approaches to support this heuristic. Both allow to gain some confidence in the validity of the heuristic, but of course none affect the heuristic nature of this statement.

For the first line of justification, we denote by H the matrix of all the #P q = q 3 + q vectors v(m) defined as in Equation (3). Associated to a polynomial P , Section 4 defines the matrix H(P ) formed of the rows v(m) such that the numerator of L m is smooth. We will give heuristics that H(P ) has Θ(q 3 ) rows and then prove that H has rank q 2 + 1, which of course does not prove that its submatrix H(P ) has full rank.

In order to estimate the number of rows of H(P ) we assume that the numerator of L m has the same probability to be ⌈ D 2 ⌉-smooth as a random polynomial of same degree. In this paragraph, we assume that the degrees of h 0 and h 1 are bounded by 2, merely to avoid awkward notations; the result holds for any constant bound δ. The degree of the numerator of L m is then bounded by 3D, so we have to estimate the probability that a polynomial in F q 2 [X] of degree 3D is ⌈ D 2 ⌉-smooth. For any prime power q and integers 1 ≤ m ≤ n, we denote by N q (m, n) the number of m-smooth monic polynomials of degree n. Using analytic methods, Panario et al. gave a precise estimate of this quantity (Theorem 1 of [START_REF] Panario | An analytic approach to smooth polynomials over finite fields[END_REF]):

N q (n, m) = q n ρ n m 1 + O log n m , (4)
where ρ is Dickman's function defined as the unique continuous function such that ρ(u) = 1 on [0, 1] and uρ ′ (u) = ρ(u -1) for u > 1. We stress that the constant κ hidden in the O() notation is independent of q. In our case, we are interested in the value of N q 2 (3D, ⌈ D 2 ⌉). Let us call D 0 the least integer such that 1 + κ log(3D)

⌈D/2⌉
is at least 1/2. For D > D 0 , we will use the formula (4); and for D ≤ D 0 , we will use the crude estimate N q (n, m) ≥ N q (n, 1) = q n /n!. Hence the smoothness probability of L m is at least min 1 2 ρ(6), 1/(3D 0 )! . More generally, if deg h 0 and deg h 1 are bounded by a constant δ then we have a smoothness probability of ρ(2δ + 2) times an absolute constant. Since we have q 3 + q candidates and a constant probability of success, H(P ) has Θ(q 3 ) rows. Now, unless some theoretical obstruction occurs, we expect a matrix over F ℓ to have full rank with probability at least 1-1 ℓ . The matrix H is however peculiar, and does enjoy regularity properties which are worth noticing. For instance, we have the following proposition.

Proposition 9 Let ℓ be a prime not dividing q 3 -q. Then the matrix H over F ℓ has full rank q 2 + 1.

Proof. We may obtain this result in two ways. First, H is the incidence matrix of a 3 -(q 2 + 1, q + 1, 1) combinatorial design called inversive plane (see e.g. [START_REF] Stinson | Combinatorial designs : constructions and analysis[END_REF]Theorem 9.27]). As such we obtain the identity

H T H = (q + 1)(J q 2 +1 -(1 -q)I q 2 +1 )
(see [21, Theorem 1.13 and Corollary 9.6]), where J n is the n × n matrix with all entries equal to one, and I n is the n × n identity matrix. This readily gives the result exactly as announced.

We also provide an elementary proof of the Proposition. We have a bijection between rows of H and the different possible image sets of the projective line P 1 (F q ) within P 1 (F q 2 ), under injections of the form (α : β) → m -1 • (α : β). All these q 3 + q image sets have size q + 1, and by symmetry all points of P 1 (F q 2 ) are reached equally often. Therefore, the sum of all rows of H is the vector whose coordinates are all equal to 1 1+q 2 (q 3 + q)(q + 1) = q 2 + q. Let us now consider the sum of the rows in H whose first coordinate is 1 (as we have just shown, we have q 2 + q such rows). Those correspond to image sets of P 1 (F q ) which contain one particular point, say (0 : 1). The value of the sum for any other coordinate indexed by e.g. Q ∈ P 1 (F q 2 ) is the number of image sets m -1 • P 1 (F q ) which contain both (0 : 1) and Q, which we prove is equal to q + 1 as follows. Without loss of generality, we may assume Q = ∞ = (1 : 0). We need to count the relevant homographies m -1 ∈ PGL 2 (F q 2 ), modulo PGL 2 (F q )-equivalence m ≡ hm. By PGL 2 (F q )-equivalence, we may without loss of generality assume that m -1 fixes (0 : 1) and (1 : 0). Letting m We may normalize to d = 1, and notice that multiplication of a by a scalar in F * q is absorbed in PGL 2 (F q )-equivalence. Therefore the number of suitable m is #F * q 2 /F * q = q + 1. These two facts show that the row span of H contains the vectors (q 2 + q, . . . , q 2 + q) and (q 2 + q, q + 1, . . . , q + 1). The vector (q 3 -q, 0, . . . , 0) is obtained as a linear combination of these two vectors, which suffices to prove that H has full rank, since the same reasoning holds for any coordinate.

⊓ ⊔ Proposition 9, while encouraging, is clearly not sufficient. We are, at the moment, unable to provide a proof of a more useful statement. On the experimental side, it is reasonably easy to sample arbitrary subsets of the rows of H and check for their rank. To this end, we propose the following experiment. We have considered small values of q in the range [16, . . . , 64], and made 50 random picks of subsets S i ⊂ P q , all of size exactly q 2 + 1. For each we considered the matrix of the corresponding linear system, which is made of selected rows of the matrix H, and computed its determinant δ i . For all values of q considered, we have observed the following facts.

-First, all square matrices considered had full rank over Z. Furthermore, their determinants had no common factor apart possibly from those appearing in the factorization of q 3 -q as predicted by Proposition 9. In fact, experimentally it seems that only the factors of q + 1 are causing problems. -We also explored the possibility that modulo some primes, the determinant could vanish with non-negligible probability. We thus computed the pairwise GCD of all 50 determinants computed, for each q. Again, the only prime factors appearing in the GCDs were either originating from the factorization of q 3 -q, or sporadically from the birthday paradox.

q #trials in gcd({δi}) in gcd(δi, δj ) 16 50 17 691 17 50 2, 3 431, 691 19 50 2, 5 none above q 2 23 50 2, 3 none above q 2 25 50 2, 13 none above q 2 27 50 2, 7 1327 29 50 2, 3, 5 none above q 2 31 50 2 1303, 3209 32 50 3, 11 none above q 2 q #trials in gcd({δi}) in gcd(δi, δj ) 37 50 2, 19 2879 41 50 2, 3, 7 none above q 2 43 50 2, 11 none above q 2 47 50 2, 3 none above q 2 49 50 2, 5 none above q 2 53 50 2, 3 none above q 2 59 50 2, 3, 5 none above q 2 61 50 2, 31 none above q 2 64 50 5, 13 none above q 2

Table1. Prime factors appearing in determinant of random square submatrices of H (for one given set of random trials)

These results are summarized in table 1, where the last column omits small prime factors below q 2 . Of course, we remark that considering square submatrices is a more demanding check than what Heuristic 7 suggests, since our algorithm only needs a slightly larger matrix of size Θ(q 3 ) × (q 2 + 1) to have full rank.

A second line of justification is more direct and natural, as it is possible to implement the algorithm outlined in Section 4, and verify that it does provide the desired result. A Magma implementation validates this claim, and has been used to implement descent steps for an example field of degree 53 over F 53 2 . An example step in this context is given for applying our algorithm to a polynomial of degree 10, attempting to reduce it to polynomials of degree 6 or less. Among the 148,930 elements of P q , it sufficed to consider only 71,944 matrices m, of which about 3.9% led to relations, for a minimum sufficient number of relations equal to q 2 + 1 = 2810 (as more than half of the elements of P q had not even been examined at this point, it is clear that getting more relations was easywe did not have to). As the defining polynomial for the finite field considered was constructed with δ = deg h 0,1 = 1, all left-hand sides involved had degree 20. The polynomials appearing in their factorizations had the following degrees (the number in brackets give the number of distinct polynomials found for each degree): 1(2098), 2(2652), 3(2552), 4(2463), 5(2546), 6(2683). Of course this tiny example size uses no optimization, and is only intended to check the validity of Proposition 2.

As for Heuristic 8, it is already present in [START_REF] Joux | A new index calculus algorithm with complexity L(1/4 + o(1)) in very small characteristic[END_REF] and [START_REF] Göloglu | On the Function Field Sieve and the impact of higher splitting probabilities[END_REF], so this is not a new heuristic. Just like for Heuristic 7, it is based on the fact that the probability that a left-hand side is 1-smooth and yields a relation is constant. Therefore, we have a system with Θ(q 3 ) relations between O(q 2 ) indeterminates, and it seems reasonable to expect that it has full rank. On the other hand, there is not as much algebraic structure in the linear system as in Heuristic 7, so that we see no way to support this heuristic apart from testing it on several inputs. This was already done (including for record computations) in [START_REF] Joux | A new index calculus algorithm with complexity L(1/4 + o(1)) in very small characteristic[END_REF] and [START_REF] Göloglu | On the Function Field Sieve and the impact of higher splitting probabilities[END_REF], so we do not elaborate on our own experiments that confirm again that Heuristic 8 seems to be valid except for tiny values of q.

An obstruction to the heuristics. As noted by Cheng, Wan and Zhuang [START_REF] Cheng | Traps to the BGJT-algorithm for discrete logarithms[END_REF], the irreducible factors of h 1 X q -h 0 other than the degree k factor that is used to define F q 2k are problematic. Let P be such a problematic polynomial. The fact that it divides the defining equation implies that it also divides the L m quantity that is involved when trying to build a relation that relates P to other polynomials. Therefore the first part of Proposition 2 can not hold for this P . Similarly, if P is linear, its presence will prevent the second part of Proposition 2 to hold since the logarithm of P can not be found with the technique of Section 4. We present here a technique to deal with the problematic polynomials. (The authors of [START_REF] Cheng | Traps to the BGJT-algorithm for discrete logarithms[END_REF] proposed another solution to keep the quasi-polynomial nature of algorithm.) Proposition 10 For each problematic polynomial P of degree D, we can find a linear relation between log P , log h 1 and O(D) logarithms of polynomials of degree at most (δ -1)D which are not problematic.

Proof. Let P be an irreducible factor of h 1 X q -h 0 of degree D. Let us consider P q ; by reducing modulo h 1 X q -h 0 and clearing denominators, there exists a polynomial A(X) such that

h D 1 P q = h D 1 P h 0 h 1 + (h 1 X q -h 0 )A(X). (5)
Since P divides two of the terms of this equality, it must also divide the third one, namely the polynomial R = h D 1 P (h 0 /h 1 ). Let v P ≥ 1 be the valuation of P in R. In the finite field F q 2k we obtain the following equalities between logarithms:

(q -v P ) log

P = -D log h 1 + i e i log Q i ,
where Q i are the irreducible factors of R other than P and e i their valuation in R. A polynomial Q i can not be problematic. Otherwise, it would divide the right-hand side of Equation ( 5), and therefore, also the left-hand side, which is impossible. Since v P ≤ deg R deg P ≤ δ < q, the quantity q -v P is invertible modulo ℓ (we assume, as usual that ℓ is larger than q) and we obtain a relation between log P , log h 1 and the logarithms of the non-problematic polynomials Q i . The degree of R/P vP is at most (δ -1)D, which gives the claimed bound on the degrees of the Q i .

⊓ ⊔

If δ ≤ 2, this proposition solves the issues raised by [START_REF] Cheng | Traps to the BGJT-algorithm for discrete logarithms[END_REF] about problematic polynomials. Indeed, for each problematic polynomial of degree D > 1, it will be possible to rewrite its logarithm in terms of logarithms of non-problematic polynomials of at most the same degree that can be descended in the usual way. Similarly, each problematic polynomial of degree 1 can have its logarithm rewritten in terms of the logarithms of other non-problematic linear polynomials. Adding these relations to the ones obtained in Section 4, we expect to have a full-rank linear system.

If δ > 2, we need to rely on the additional heuristic. Indeed, when descending the Q i that have a degree potentially larger than the degree of D, we could hit again the problematic polynomial we started with, and it could be that the coefficients in front of log P in the system vanishes. More generally, taking into account all the problematic polynomials, if when we apply Proposition 10 to them we get polynomials Q i of higher degrees, it could be that descending those we creates loops so that the logarithms of some of the problematic polynomials could not be computed. We expect this event to be very unlikely. Since in all our experiments it was always possible to obtain δ = 2, we did not investigate further.

Finding appropriate h 0 and h 1 . One key fact about the algorithm is the existence of two polynomials h 0 and h 1 in F q 2 [X] such that h 1 (X)X q -h 0 (X) has an irreducible factor of degree k. A partial solution is due to Joux [START_REF] Joux | A new index calculus algorithm with complexity L(1/4 + o(1)) in very small characteristic[END_REF] who showed how to construct such polynomials when k ∈ {q -1, q, q + 1}. No such deterministic construction is known in the general case, but experiments show that one can apparently choose h 0 and h 1 of degree at most 2. We performed an experiment for every odd prime power q in [3, . . . , 1000] and every k ≤ q and found that we could select a ∈ F q 2 such that X q + X 2 + a has an irreducible factor of degree k. Finally, note that the result is similar to a commonly made heuristic in discrete logarithm algorithms: for fixed f ∈ F q 2 [X, Y ] and random g ∈ F q 2 [X, Y ], the polynomial Res Y (f, g) behaves as a random polynomial of same degree with respect to the degrees of its irreducible factors.

Some directions of improvement

The algorithm can be modified in several ways. On the one hand one can obtain a better complexity if one proves a stronger result on the smoothness probability. On the other hand, without changing the complexity, one can obtain a version which should behave better in practice.

Complexity improvement

Heuristic 7 tells that a rectangular matrix with Θ(q) times more rows than columns has full rank. It seems reasonable to expect that only a constant times more rows than columns would be enough to get the full rank properties (as is suggested by the experiments proposed in Section 5). Then, it means that we expect to have a lot of choices to select the best relations, in the sense that their left-hand sides split into irreducible factors of degrees as small as possible.

On average, we expect to be able to try Θ(q) relations for each row of the matrix. So, assuming that the numerators of L m behave like random polynomials of similar degrees, we have to evaluate the expected smoothness that we can hope for after trying Θ(q) polynomials of degree (1 + δ)D over F q 2 . Set u = log q/ log log q, so that u u ≈ q. According to [START_REF] Panario | An analytic approach to smooth polynomials over finite fields[END_REF] it is then possible to replace ⌈D/2⌉ in Proposition 2 by the value O(D log log q/ log q).

Then, the discussion leading to Theorem 3 can be changed to take this faster descent into account. We keep the same estimate for the arity of each node in the tree, but the depth is now only in log k/ log log q. Since this depth ends up in the exponent, the resulting complexity in Theorem 3 is then max(q, k) O(log k/ log log q) .

Practical improvements

Because of the arity of the descent tree, the breadth eventually exceeds the number of polynomials below some degree bound. It makes no sense, therefore, to use the descent procedure beyond this point, as the recovery of discrete logarithms of all these polynomials is better achieved as a pre-computation. Note that this corresponds to the computations of the L(1/4 + ǫ) algorithm which starts by pre-computing the logarithms of polynomials up to degree 2. In our case, we could in principle go up to degree O(log q) without changing the complexity.

We propose another practical improvement in the case where we would like to spend more time descending a given polynomial P in order to improve the quality of the descent tree rooted at P . The set of polynomials appearing in the right-hand side of Equation (E m ) in Section 4 is {P -λ}, because in the factorization of X q -X, we substitute X with m • P for homographies m. In fact, we may apply m to (P : P 1 ) for any polynomial P 1 whose degree does not exceed that of P . In the right-hand sides, we will have only factors of form P -λP 1 for λ in F q 2 . On the left-hand sides, we have polynomials of the same degree as before, so that the smoothness probability is expected to be the same. Nevertheless, it is possible to test several P 1 polynomials, and to select the one that leads to the best tree.

This strategy can also be useful in the following context (which will not occur for large enough q): it can happen that for some triples (q, D, D ′ ) one has N q 2 (3D, D ′ )/q n ≈ 1/q. In this case we have no certainty that we can descend a degree-D polynomial to degree D ′ , but we can hope that at least one of the P 1 allows to descend.

Finally, if one decides to use several auxiliary P 1 polynomials to descend a polynomial P , it might be interesting to take a set of polynomials P 1 with an arithmetic structure, so that the smoothness tests on the left-hand sides can benefit from a sieving technique.

Conclusion

The algorithm presented in this article achieves a significant improvement of the asymptotic complexity of discrete logarithm in finite fields, in almost the whole range of parameters where the Function Field Sieve was presently the most competitive algorithm. Compared to existing approaches, and in particular to the line of recent works [START_REF] Joux | Faster index calculus for the medium prime case. Application to 1175bit and 1425-bit finite fields[END_REF][START_REF] Göloglu | On the Function Field Sieve and the impact of higher splitting probabilities[END_REF], the practical relevance of our algorithm is not clear, and will be explored by further work.

We note that the analysis of the algorithm presented here is heuristic, as discussed in Section 5. Some of the heuristics we stated, related to the properties of matrices H(P ) extracted from the matrix H, seem accessible to more solid justification. It seems plausible to have the validity of algorithm rely on the sole heuristic of the validity of the smoothness estimates.

The crossing point between the L(1/4) algorithm and our quasi-polynomial one is not determined yet. One of the key factors which hinders the practical efficiency of this algorithm is the O(q 2 D) arity of the descent tree, compared to the O(q) arity achieved by techniques based on Gröbner bases [START_REF] Joux | Faster index calculus for the medium prime case. Application to 1175bit and 1425-bit finite fields[END_REF] at the expense of a L(1/4 + ǫ) complexity. Adj et al. [START_REF] Adj | Weakness of F 3 6•509 for discrete logarithm cryptography[END_REF] proposed to mix the two algorithms and deduced that the new descent technique must be used for cryptographic sizes. Indeed, by estimating the time required to compute discrete logarithms in F 3 6•509 , they showed the weakness of some pairing-based cryptosystems.

  d) = (0 : 1) and (a : c) = (1 : 0), whence b = c = 0, and both a, d = 0.

This estimate of the number of irreducible factors is a pessimistic upper bound. In practice, one expects to have only O(log D) factors on average. Since the crude estimate does not change the overall complexity, we keep it that way to avoid adding another heuristic.

Acknowledgements

The authors would like to thank Daniel J. Bernstein for his comments on an earlier version of this work, and for pointing out to us the possible use of asymptotically fast linear algebra for solving the linear systems encountered.


Bernard Mouillac
email: bernard.mouillac@igf.cnrs.fr

Christiane Mendre

Pharmacological chaperones Vasopressin receptors and pharmacological chaperones: from functional rescue to promising therapeutic strategies

Keywords: antidiuretic hormone, V2 vasopressin receptor, congenital Nephrogenic Diabetes Insipidus, vaptans, biased agonists, therapeutic rescue AVP, arginine-vasopressin, AQP2, aquaporin-2, cNDI, congenital Nephrogenic Diabetes Insipidus, GPCR, G protein-coupled receptor, PC, pharmacological chaperones, V2R, vasopressin type 2 receptor

Conformational diseases result from protein misfolding and/or aggregation and constitute a major public health problem. Congenital Nephrogenic Diabetes Insipidus is a typical conformational disease. In most of the cases, it is associated to inactivating mutations of the renal arginine-vasopressin V2 receptor gene leading to misfolding and intracellular retention of the receptor, causing the inability of patients to concentrate their urine in response to the antidiuretic hormone. Cell-permeable pharmacological chaperones have been successfully challenged to restore plasma membrane localization of the receptor mutants and to rescue their function. Interestingly, different classes of specific ligands such as antagonists (vaptans), agonists as well as biased agonists of the V2 receptor have proven their usefulness as efficient pharmacochaperones. These compounds represent a potential therapeutic treatment of this Xlinked genetic pathology.

1. Introduction : the X-linked genetic disease cNDI 2. Antagonists to the rescue : known compounds with "novel" pharmacological chaperone activity 3. Agonists and biased agonists : better pharmacological chaperones than antagonists ? 4. Clinical trials 5. Conclusions and perspectives Conflict of interest References

Introduction: the X-linked genetic disease cNDI

Regulated water excretion by the kidney is crucial to preserve water homeostasis of our body. The adjustement of water renal reabsorption, to respond to increase in blood osmolality (hypernatremia) or decrease in blood volume (hypovolemia), mainly depends on the release of the antidiuretic hormone arginine-vasopressin (AVP) from the pituitary [START_REF] Treschan | The vasopressin system[END_REF][START_REF] Moeller | Nephrogenic diabetes insipidus : essential insights into the molecular background and potential therapies for treatment[END_REF][START_REF] Feinstein | Noncanonical control of vasopressin receptor type 2 signaling by retromer and arrestin[END_REF]. Binding of AVP to the vasopressin type 2 receptor (V2R), a Gs protein-coupled receptor (GPCR) localized at the basolateral membrane of the principal cells of the kidney collecting duct, results in an intracellular cAMP-dependent signaling cascade of events. Among them, phosphorylation of the water channel aquaporin-2 (AQP2) and its translocation from storage compartments to the apical surface of the cells are of primary importance. Water from prourine which enters the cells exits via aquaporin-3 and aquaporin-4 at the basolateral side, leading to water reabsorption and urine concentration. Upon restoration of water balance, the level of plasma AVP drops and AQP2 is internalized, leaving the apical membrane watertight again. Disorders that interfere with proper urine concentration can be life-threatening, especially in children. One such disease is the congenital form of Nephrogenic Diabetes Insipidus (cNDI) [START_REF] Morello | Nephrogenic diabetes insipidus[END_REF]. Indeed, cNDI is a rare inherited disease, characterized by insensivity of the kidney to AVP and absence of water reabsorption. It results in polyuria and compensatory polydipsia, and may lead to severe dehydration and electrolyte imbalance (hypernatremia) in the case of inadequate water supply. The X-linked form of cDNI is caused by mutations in the V2R gene [START_REF] Bichet | Nature and recurrence of AVPR2 mutations in X-linked nephrogenic diabetes insipidus[END_REF]. To date, over 200 different V2R mutations have been described. V2R mutations are divided into five different classes. Class II mutations (the most prevalent, more than 50%) are most frequently missense mutations (amino acid substitutions). These mutations result into misfolded, traffickingdeficient receptors that do not reach plasma membrane of the basolateral side of the principal cells of the kidney collecting duct. Indeed, most of the mutants are retained in the endoplamic reticulum (ER) and in the ER-Golgi intermediate compartment. Consequently, V2R mutants are unable to interact with circulating AVP [START_REF] Tsukagushi | Binding, intracellular transport and biosynthesis-defective mutants of vasopressin type 2 receptor in patients with X-linked nephrogenic diabetes insipidus[END_REF]. These V2R mutants, rather than resulting in nonfunctional proteins (mutants from classes III and IV) are intrinsically functional, as demonstrated by overexpression in heterologous cell expression systems [START_REF] Ala | Functional studies of twelve mutant V2 vasopressin receptors related to nephrogenic diabetes insipidus : molecular basis of a mild clinical phenotype[END_REF]. cNDI-untreated adult patients may have a daily output of 15-20 L of highly dilute urine. Newborn infants often suffer from hypernatremic dehydration with symptoms of irritability, poor feeding and weight gain. In addition, repeated periods of brain dehydration may result in permanent brain damage, mental retardation and seizures can occur. The main strategy for treating cNDI patients consists of a sufficient water supply to replace the urinary water loss, but this can seriously impact on the quality of life due to excessive drinking and urine voiding. Some diuretics, like hydrochlorothiazide, amiloride or the cyclooxygenase inhibitor indomethacin, have been proven effective to reduce urine output by up to 50% [START_REF] Bockenhauer | Urinary concentration : different ways to open and close the tap[END_REF]. However, diuretics may affect the sodium and potassium balance in patients and therefore these treatments require tight monitoring of serum electrolytes and osmolality. Although understanding of cNDI from molecular and cell biological point of view has largely increased since the cloning of the V2R gene in 1992 [START_REF] Birnbaumer | Molecular cloning of the receptor for human antidiuretic hormone[END_REF][START_REF] Lolait | Cloning and characterization of a vasopressin V2 receptor and possible link to nephrogenic diabetes insipidus[END_REF][START_REF] Rosenthal | Molecular identification of the gene responsible for congenital nephrogenic diabetes insipidus[END_REF], developing alternative strategies to manage water homeostasis and induce antidiuresis in cNDI patients is still obvious. The V2R is a "natural" target for establishing new forms of therapies, and rescue of its function is a very elegant and specific approach. Here starts the story of pharmacological chaperones (PC).

Antagonists to the rescue: known compounds with novel pharmacological chaperone activity

Chemical chaperones, like glycerol and DMSO, were shown for instance to correct mutants of the AQP2 water channel, as assessed by protein maturation, cellular targeting and water permeability [START_REF] Tamarappoo | Defective aquaporin-2 trafficking in nephrogenic diabetes insipidus and correction by chemical chaperones[END_REF]. Taking the concept of chemical chaperones further, artificial mutants of the multidrug resistance P-glycoprotein-1, a cell surface transporter which interacts with a panel of cytotoxic agents, were functionally rescued. Indeed, ER-retained mutants were targeted to the plasma membrane and their functional rescue was demonstrated using specific substrates or inhibitors like vinblastin, cyclosporin or verapamil [START_REF] Loo | Correction of defective protein kinesis of human P-glycoprotein mutants by substrates and modulars[END_REF]. These compounds were proposed to stabilize a specific native-like conformation of the transporter, allowing its release from the ER quality control cell system. The concept was applied to the mutants of V2R responsible for cNDI, based on the idea that pharmacological ligands act by binding to and stabilizing specific conformations of their receptors. Selective cell-permeant nonpeptidic V2R antagonists (which block the V2R in an inactive conformation) were assessed to check whether they could facilitate the folding of mutant receptors that are retained in ER and unable to interact with AVP [START_REF] Morello | Pharmacological chaperones rescue cell-surface expression and function of misfolded V2 vasopressin receptor mutants[END_REF]. The experiments were successful. Given that these antagonists are specific to the V2R and that they perform chaperone-like activity, Drs. Bichet and Bouvier termed these compounds pharmacological chaperones (PC) [START_REF] Morello | Pharmacological chaperones : a new twist on receptor folding[END_REF]. Other names like pharmacochaperones or pharmacoperones have then been proposed. The first antagonist (or inverse agonist) to be used was SR121463, a selective high-affinity V2R ligand [START_REF] Morello | Pharmacological chaperones rescue cell-surface expression and function of misfolded V2 vasopressin receptor mutants[END_REF]. An overnight treatment of the cells retaining different V2R mutants into an intracellular compartment converted precursor forms into fully glycosylated mature receptors that were targeted to the cell surface. Once correctly localized at the plasma membrane, these mutants were able to differentially bind AVP and produce a correlated cAMP intracellular signal. Interestingly, V2R membrane-impermeable peptidic antagonists were unable to mimic the SR121463 effect, indicating a PC intracellular effect. The PC-driven V2R mutant rescue was not limited to SR121463, because another nonpeptidic antagonist, VPA985, reproduced equivalent results. Since the publication of this outstanding study, SR121463 was used to rescue a larger panel of V2R mutants [START_REF] Tan | Appropriate polarization following pharmacological rescue of V2 vasopressin receptors encoded by X-linked nephrogenic diabetes insipidus alleles involves a conformation of the receptor that also attains mature glycosylation[END_REF][START_REF] Wüller | Pharmacochaperones post-translationally enhance cell surface expression by increasing conformational stability of wild-type and mutant vasopressin V2 receptors[END_REF][START_REF] Bockenhauer | Vasopressin type 2 receptor V88M mutation : molecular basis of partial and complete nephrogenic diabetes insipidus[END_REF][START_REF] Janovick | Therapeutic rescue of misfolded mutants : validation of primary high throughput screens for identification of pharmacoperone drugs[END_REF] and different other antagonists (or inverse agonists) were tested for their PC properties, such as the V1AR-selective SR49059 [START_REF] Wüller | Pharmacochaperones post-translationally enhance cell surface expression by increasing conformational stability of wild-type and mutant vasopressin V2 receptors[END_REF][START_REF] Bernier | Functional rescue of the constitutively internalized V2 vasopressin receptor mutant R137H by the pharmacological chaperone action of SR49059[END_REF], the mixed V1A/V2R YM087 [START_REF] Bernier | Pharmacologic chaperones as a potential treatment for X-linked nephrogenic diabetes insipidus[END_REF] and the V2R-selective OPC31260 and OPC41061 [START_REF] Robben | Functional rescue of vasopressin V2 receptor mutants in MDCK cells by pharmacochaperones : relevance to therapy of nephrogenic diabetes insipidus[END_REF]. A list of the different PC used to rescue cNDI V2R mutants is presented in Table 1, as well as the different receptor mutants for which the PC beneficial effect was proven. Very importantly, the PC effect was also reproducible in polarized renal cells where V2R mutants were appropriately targeted to the basolateral membrane, the natural localization of the wildtype V2R [START_REF] Robben | Rescue of vasopressin V2 receptor mutants by chemical chaperones : specificity and mechanism[END_REF]. In addition, because of their target specificity, the PC compounds are active at nanomolar concentrations on cultured cells [START_REF] Robben | Functional rescue of vasopressin V2 receptor mutants in MDCK cells by pharmacochaperones : relevance to therapy of nephrogenic diabetes insipidus[END_REF]. This is a tremendous advantage, compared to chemical chaperones which are active at micromolar concentrations or even more.

Interestingly, the concept of PC developed for V2R mutants responsible for cNDI was applied to other GPCR families [START_REF] Janovick | Rescue of hypogonadotropic hypogonadismcausing and manufactured GnRH receptor mutants by a specific protein-folding template : misrouted proteins as a novel disease etiology and therapeutic target[END_REF] but also to the V1A and V1B subtypes of the vasopressin receptor family, strenghtening the idea that PC action can be generalized to many intracellular-retained misfolded mutant receptors. Regarding vasopressin receptor family, SSR149415, which is a specific nonpeptidic antagonist for V1B was demonstrated to rescue plasma membrane localization and function of the V1B mutant 341FN(X) 2 LL(X) 3 L350 [START_REF] Auzan | Mechanisms of cell-surface rerouting of an endoplasmic reticulum-retained mutant of the vasopressin V1b/V3 receptor by a pharmacological chaperone[END_REF]. Then, the selective nonpeptidic antagonist SR49059 was shown to rescue the functional properties of surface-impaired D148A/N/E mutants of the V1A receptor subtype [START_REF] Hawtin | Pharmacological chaperone activity of SR49059 fo functionally recover misfolded mutations of the vasopressin V1a receptor[END_REF]. To date, no more study has been investigated using PC to rescue other artificial mutants of V1AR, V1BR or the vasopressin-related oxytocin receptor. Although very promising, using antagonists for rescuing function of the V2R and more generally GPCRs responsible for inherited conformational diseases is somehow paradoxical. First of all, because these antagonists specifically block (inhibit) their receptors, they can not directly stimulate receptor-associated signaling pathways. Regarding patients who suffer from cNDI, the therapeutic beneficial effect would be antidiuresis, through activation of a cAMPdependent signaling cascade and particularly membrane translocation of AQP2. Indeed, using the PC antagonist strategy, functional rescue of mutants of the V2R is a subtle balance between the ability of the ligand to target cell-surface expression of the mutants and its possibility to be displaced by AVP for receptor activation [START_REF] Mendre | Pharmacological chaperones : a potential therapeutic treatment for conformational diseases[END_REF]. In this regard, considering the antagonist affinity is an important feature for this challenge, and therefore low-affinity antagonists (those which are easily displaced by AVP) may possess a highest clinical value [START_REF] Los | Potential of nonpeptide (ant)agonists to rescue vasopressin V2 receptor mutants for the treatment of X-linked nephrogenic diabetes insipidus[END_REF]. However, the efficiency of such low-affinity antagonist ligands in rescuing receptor function is lower than that of high-affinity ligands (the higher the affinity, the better rescue will be obvious). Moreover, high concentrations of low-affinity antagonists to be administered for clinical efficiency might lead to unwanted side effects in patients (see below section 4). In addition, compound-intrinsic factors other than affinity may influence their capacity to confer functional rescue and their extent to be displaced by AVP, like their localization in the binding pocket of the V2R, their intrinsic activity or their lipophilic value.

it seems that concerning cNDI patients, the high-affinity OPC31260 (mozavaptan) and OPC41061 (tolvaptan) nonpeptidic antagonists would combine best clinical potential, in terms of cell surface rescue, low concentration to be used, and efficient displacement by AVP [START_REF] Robben | Functional rescue of vasopressin V2 receptor mutants in MDCK cells by pharmacochaperones : relevance to therapy of nephrogenic diabetes insipidus[END_REF][START_REF] Wesche | Congenital nephrogenic diabetes insipidus : the current state of affairs[END_REF].

Agonists and biased agonists : better pharmacological chaperones than antagonists ?

Other pharmacological approaches to treat cNDI patients may have a higher potential that the antagonist PC strategy. Indeed, agonists and biased agonists of the V2R may prove to be of higher clinical value. Theoretically, PC agonists possess advantages over antagonists since they are able to directly stimulate the V2R and induce receptor-associated signaling pathways. In this case, V2R-selective high-affinity ligands are likely to be the most appropriate to efficiently rescue plasma membrane targeting of the mutants and their direct activation. However, agonists also promote V2R internalization, and consequently a decrease in the cAMP signal, a phenomenon that could reduce the beneficial effects of these compounds. Two agonist-based PC alternative approaches have been described, and constitue very promising therapeutic strategies. Recent investigations by Robben et al. indicated that ER-retained but intrinsically functional V2R mutants can be activated intracellularly by different agonists [START_REF] Robben | Intracellular activation of vasopressin V2 receptor mutants in nephrogenic diabetes insipidus by nonpeptide agonists[END_REF]. The activation surprisingly leads to sufficient cAMP increase to induce AQP2 to be translocated to the apical membrane of renal polarized cells. The recently developed nonpeptidic agonist OPC51803 and two novel agonists VA999088 and VA999089 were used in this study to rescue function of a panel of different cNDI V2R mutants (see Table 1). In contrast to PC-assisted receptor folding and rescue, the localization and maturation of the cNDI mutants did not change upon ligand binding and receptor activation. Due to their structural features (small lipophilic molecule compounds which have the ability to penetrate cell membranes and reach the ER), it is surprising that these three ligands do not behave as PC and likely induce plasma membrane targeting of the different V2R mutants. Consequently, they cannot be classified as pharmacological chaperones but still constitute promising future therapeutic candidates for cNDI clinical studies [START_REF] Moeller | Nephrogenic diabetes insipidus : essential insights into the molecular background and potential therapies for treatment[END_REF]. Like for PC-based approaches, V2R rescue and intracellular receptor activation by OPC51803 and both VA compounds may only work for mutations that affect folding or proper intracellular transport, but neither for highly truncated receptors, nor those that lost their Gs-dependent coupled signaling pathways. These ligands may also be tested on a larger panel of cNDI mutants, in order to check their PC potential properties. The discovery of biased agonist PC of the V2R is a novel therapeutic opportunity for cNDI [START_REF] Jean-Alphonse | Biased agonist pharmacochaperones of the AVP V2 receptor may treat congenital nephrogenic diabetes insipidus[END_REF]. The V2R nonpeptidic agonists MCF14 (OPC23h), MCF18 (VNA932) and MCF57 possess only part of the AVP signaling properties. Indeed, these molecules are full agonists of the Gs-dependent cAMP signal (which is responsible for AQP2 translocation and water reabsorption) but do not induce receptor internalization and arrestin-related signaling pathways (antagonists for arrestin recruitment and associated events). On a therapeutic point of view, these particular properties may lead to additional beneficial effects for cNDI patients. The ligands MCF14, MCF18 and MCF57 are high-affinity agonists for V2R and are capable of inducing cNDI mutant receptor maturation, translocation to the plasma membrane and can directly initiate a cAMP response (they may act in synergy with circulating AVP in the case of in vivo clinical trials). Functional rescue was demonstrated for different mutants of the V2R (see Table 1). They constitute a novel class of PC. Indeed, the V2R biased agonist PC, able to generate a cAMP signal and acting as noninternalizing ligands, potentially providing a long-lasting cellular response during drug administration, may constitute ideal therapeutic compounds for treating cNDI.

Clinical trials

A small-scale short-term clinical trial has been set up using SR49059, a low-affinity antagonist for V2R (it is specific for the V1A receptor subtype) [START_REF] Bernier | Pharmacologic chaperones as a potential treatment for X-linked nephrogenic diabetes insipidus[END_REF]. Different patients with R137H, W164S and Δ62-64 mutations were treated with the nonpeptidic antagonist. Interestingly, SR49059 significantly decreased the 24-h urine volume and water intake, demonstrating a successful PC behavior in vivo. However, because of potential interference with the cytochrome P450 metabolic pathway (hepatic toxicity), the development of this molecule was discontinued during clinical phase II. To date, no other clinical trial has been developed for cNDI patients. Recently, the cell-permeable nonpeptidic antagonist OPC41061 (tolvaptan, Samsca) has been approved in USA and Europe for the treatment of hyponatremia in the syndrome of inappropriate antidiuretic hormone secretion and congestive heart failure. This ligand may be of high therapeutic value for novel clinical trials for treating cNDI in the future, provided that it can be displaced by AVP in vivo.

Conclusions and Perspectives

There have been many advances in the identification of PC compounds for potentially treating cNDI. In principle, V2R-specific PC have more desirable properties as V2R mutant therapeutics than current nonspecific treatments like thiazides with indomethacine. The use of biased agonist PC is of particular clinical interest. Because the rescuing properties of these ligands have been analyzed to only a few misfolded receptors, it would be important to investigate their PC properties on a larger panel of V2R mutants (most of the mutants from class II are potential candidates to be treated). Like in the case of cystic fibrosis, a combination of selective PC with proteostasis regulators may constitute an ideal drug therapy [START_REF] Hanrahan | Novel pharmacological strategies to treat cystic fibrosis[END_REF]. Indeed, since most of the V2R mutants are ER-retained, rejected by the ER quality control system, and consequently targeted to the ubiquitin-proteasome degradation pathway, proteostasis regulators which modify the cellular pathways responsible for protein quality control and trafficking may improve/complement the activity of PC. The X-linked genetic disease cNDI provides an excellent example of how the study of a rare pathology can provide new insights into the knowledge and treatment of conformational diseases.

Table 1 .

 1 Overview of pharmacochaperones with potential for treatment of cNDI and of V2R mutants that are rescued. In this study, SR121463 was used at 1 µM, a high concentration enabling plasma membrane rescue, but rendering very difficult displacement of this PC with AVP.

	Compound	Intrinsic activity	Specificity	Plasma membrane	Functional rescue	Reference
				rescue
	SR121463	Inverse agonist	V2R	L59P, ∆62-64, L83Q,	all	[14]
	(satavaptan,			Y128S, S167L, A294P,
	Aquilda ® )			P322H, R337X
				∆V278, L292P, R337X	L292P, R337X	[16]
				S167T, V206D	both	[23]
				L44P, ∆62-64, R113W,	none*	[22]
				I130F, S167T, G201D,
				T204N, V206D
				∆62-64, S167T, C319Y,	not tested	[17]
				P322S, W323H
				L44P, L59P, Y128S,	L44P, A294P,	[31]
				A294P, R337X	R337X
				V88M	no affinity for AVP	[18]
				L83Q	L83Q	[19]
	VPA985	Inverse agonist	V2R	L59P, ∆62-64, L83Q,	all	[14]
	(lixivaptan)			Y128S, S167L, A294P,
				P322H, R337X
	SR49059	Antagonist	V1AR	R137H	R137H	[20]
	(relcovaptan)
				C319Y	C319Y	[17]

Conflict of interest

The authors declare that there are no conflicts of interest.


Emmanuel Jeanvoine

Luc Sarzyniec

Lucas Nussbaum

Kadeploy3: Efficient and Scalable Operating System Provisioning for Clusters

 or xCAT [8] is a common approach. In that case the administrator must keep updated only one node (sometimes called golden node), that will be replicated to other nodes. This article presents Kadeploy3, a tool designed to perform operating system provisioning using disk imaging and cloning. Thanks to its efficiency, scalability, and reliability, it is particularly suited for large scale clusters.

A Reliable Deployment Process with Kadeploy3

Kadeploy3 belongs to the family of the disk imaging and cloning tools. It takes as input an archive containing the operating system to deploy, called an environment, and copies it on the target nodes. As a consequence, Kadeploy3 does not install an operating system following a classical installation procedure and the user has to provide an archive of the environment (as a tarball, for Linux environments).

Kadeploy3 does not directly take control of the nodes since it would require some specific and uncommon hardware support. Instead, it uses common network boot capabilities based on the PXE protocol [START_REF]Preboot Execution Environment (PXE) Specification[END_REF] and it manages the associated PXE profiles.

Using such a mechanism, combined to the capability to dynamically update the PXE profiles of the nodes and with the capability to reboot the nodes in a reliable way thanks to out-of-band control interfaces (Baseboard Management Controller, Remote Supervisor Adapter) or the power distribution unit's capabilities, it is possible to take the control of the nodes and to specify what they are booting.

As shown in figure 1, a typical deployment with Kadeploy3 is composed of three major steps, called macro steps.

1. Minimal environment setup: the nodes reboot into a trusted minimal environment that contains all the tools required for the deployment (partitioning tools, archive management, ...) and the required partitioning is performed. 2. Environment installation: the environment is broadcast to all nodes and extracted on the disks. Some post-installations operations can also be performed. 3. Reboot on the deployed environment.

Macrostep 2

Env. intallation

Macrostep 3

Final reboot

Fig. 1. Kadeploy deployment process, composed of three macro-steps Each macro step can be executed via several different mechanisms to optimize the deployment process depending upon required parameters and the specific infrastructure. For instance, the Reboot on the deployed environment step can perform a traditional reboot or it might instead rely on a call to kexec(8) for a shorter reboot.

Reconfiguring a set of nodes involves several low-level operations that can lead to failures for various reasons, e.g., temporary loss of network connectivity, reboot taking longer than planned, etc. Kadeploy3 reliability is achieved thanks to two ways. First the deployment process has a powerful error management and second, critical reboot operations required for the node control are based on reboot commands escalation in order to be able to take control of the nodes in any situation.

Reliability of the Deployment

Kadeploy3 is designed to detect failures as quickly as possible and improve deployment reliability by providing a macro step replay mechanism on the nodes of interest. To illustrate that, let's consider the last deployment macro step that aims at rebooting on the deployed environment. Kadeploy3 implements, among others, the following strategies:

1. directly load the kernel inside the deployed environment thanks to kexec; 2. perform a hard reboot using an out-of-band management hardware without checking the state of node.

Thus it is possible to describe strategies such as: try to launch the first strategy; then if some nodes fail, try to launch the second strategy several time if required. Since all the steps involved in the deployment process rely on system calls (hard disk operations, network communications, specific hardware management), a special attention has been paid to the error handling. Thus, Kadeploy3 collects the result of every operation (exit status, stdout, stderr), even when it is performed on remote nodes. As a consequence, some steps can be replayed on nodes where a problem occurs.. Furthermore, some operations are likely to last too long (e.g., network boot, file-system creation, etc). Kadeploy3 also provides administrators with the capability to define specific timeouts for some operations in order to adapt the deployment process to the infrastructure. That allows to identify some problems quickly and to replay some operations on the related nodes.

Reliability of Reboot Operations

Since reboot operations are essential to control the cluster nodes, and ultimately the entire deployment process itself, they must behave correctly and reliably. Several methods can be used to reboot a nodes, for instance:

1. direct execution of the /sbin/reboot command; 2. use the capability of out-of-band management hardware with protocols such as IPMI. Various kinds of reboot can be executed: reset, power cycle, etc; 3. use the power management capability of the power distribution unit (PDU).

Performing a /sbin/reboot is the best solution with regards to speed and cleanliness. But it may not be an option if the target node is unreachable via inband methods such as SSH (e.g., the node is already down, the OS has crashed, an unfriendly operating system is installed, etc). In this scenario, we would use IPMI-like features if available. Also, it might be better for speed to perform a reset rather than a power cycle since it bypasses the power on self test, but sometimes this is not sufficient. Finally, if onboard management hardware is unreachable, we may be required to use the capabilities of a remotely manageable PDU.

Kadeploy3 provides administrators with a way to specify several levels of commands in order to perform escalation if required. This allows them to perform highly reliable deployments if the clusters have the appropriate hardware. Unfortunately, depending on the methods chosen, reboot escalation comes at a cost and a balance must be struck between desired reliability and the time to deployment.

Scalability

In addition to have a reliable node control mechanism, deploying large scale clusters in a reasonable time require to be able to execute efficiently several commands and to send large files on a large number of nodes.

Parallel commands

The deployment workflow contains several operations that reduce to executing a command on a large set of nodes.

Thanks to SSH, one can execute commands remotely and retrieve their outputs. Launching SSH commands on a large number of nodes in sequence does not scale at all. Furthermore, launching all commands simultaneously can impose an extreme load on the server and can saturate all of its file descriptors.

Several tools have been built to overcome these limitations. For instance, Pdsh [START_REF]Parallel Distributed Shell[END_REF] and ClusterShell [2] are designed to execute SSH commands on many nodes in parallel. Both tools use windowed execution to limit the number of concurrent SSH commands and both also allow retrieval of command outputs on each node.

We choose to leverage TakTuk [START_REF] Claudel | TakTuk, adaptive deployment of remote executions[END_REF] as our mechanism for parallel command execution and reporting. TakTuk is based upon a model of hierarchical connection. This allows it to distribute the execution load on all the nodes in a tree and to perform commands with low latency. Using such a hierarchical mechanism would normally require the tool to be installed on all nodes. Fortunately, TakTuk includes a convenient auto-propagation feature that assures the tool's existence on all necessary nodes. The tool also uses an adaptive work-stealing algorithm to improve performance, even on heterogeneous infrastructures.

File broadcast

The broadcast of the system image to all nodes is a critical part of the deployment. In cluster environments where the most important network for applications is using Infiniband or Myrinet, the Ethernet network is often composed of a hierarchy of switches (e.g., one switch per rack) that is hard to leverage for a high-performance broadcast. File distribution to a large number of nodes via any sequential push or pull method is not scalable. Kadeploy3 provides system administrators with three scalable file distribution approaches during the Environment installation macro step to minimize deployment time.

With tree-based broadcast, a file is sent from the server to a subset of nodes, which in turn send the file to other subsets until all the nodes have received. The size of the subsets, called tree arity, can be specified in the configuration. A large arity can reduce the latency to reach all nodes but transfer times might increase because global bandwidth is equal to the bandwidth of a network link divided by the tree arity. The opposite effect occurs when the arity is small. In general, this broadcast method does not maximize bandwidth and should be used primarily for the distribution of small files. This method is also inefficient when used in hierarchical networks. We implement tree-based broadcast using TakTuk.

Chain-based broadcast facilitates the transfer of files with high bandwidth. A classical chain-based broadcast suffers from the establishment time of the chain in large scale clusters. Indeed, since each node must connect to the next node in the chain (usually via SSH), a sequential initialization would drastically increase the entire broadcast period. Thus we perform the initialization of the chain with a tree-based parallel command. This kind of broadcast is near-optimal in a hierarchical network if the chain is well ordered since, as shown in Figure 2, all the full-duplex network links can be saturated in both directions, and images server Fig. 2. Topology-aware chained broadcast. Data is pipelined between all nodes. When correctly ordered, this ensures that inter-switches links are only used once in both directions.

the performance bottleneck becomes the backplane bandwidth of the network switches. For this method, we implement chain initialization using TakTuk and perform transfers using other custom mechanisms.

BitTorrent-based broadcast is able to send files at large scale without making any assumptions about the quality of the network. Furthermore, BitTorrent is able to efficiently handle churn, an important property in large scale systems like petascale and future exascale clusters. Currently, our experiments show that there are two scenarios in which the performance of this broadcast method is inferior to the other methods. The first pathological case is one in which we are broadcasting on a small-scale cluster with a high-speed network, and the second is one in which we are broadcasting small files. In both cases, BitTorrent exhibits high latency and the overhead of the protocol dominates the time to broadcast. The large number of established connections between nodes induced by the protocol can lead to bottlenecks depending on the network topology.

In a default configuration, Kadeploy3 uses tree-based broadcast for the files used in the deployment process (e.g., disk partition map) and chain-based method for the environment broadcast which is usually a large file. However, this behavior can be modified in the configuration.

Other advanced features

In addition to being reliable and scalable, Kadeploy has many useful features.

Multi-cluster support

Kadeploy3 can be configured to manage several clusters at the same time, through a hierarchical set of YAML configuration files. In a Grid-like environment, it is also possible to initiate and control deployments on several Kadeploy servers from a unique Kadeploy client.

Hardware and software compatibility

Kadeploy3 does not generally rely on vendor-specific mechanisms. Vendor-specific remote control systems used to trigger nodes reboots can be easily used, even if they do not support the IPMI protocol.

Environments can be stored either as tarballs (for Linux environments) or as raw partitions, which enables the deployment of Windows or BSD-based systems.

Rights management and environments library

Kadeploy3 can be used to provide users with a Cloud-like experience with baremetal system reservation. It can integrate with a cluster batch scheduler used to manage reservations, to delegate system deployment rights to specific users for the duration of a job. Kadeploy3 can also manage a set of environments and their visibility (public, private) in order to provide default environments, on which users can base their work to create and register custom environments.

Statistics collection

It is often hard to identify defunct nodes in a cluster, especially when failures are transient. Kadeploy3 integrates a statistics collection mechanism that enables the detection of nodes that often fail during the deployment process.

Performance Evaluation

Grid'5000 experimental testbed

Kadeploy3 has been used intensively on the Grid'5000 testbed (http://www. grid5000.fr) since the end of 2009 (and previous versions of Kadeploy were used since 2004). In that time, approximately 620 different users have performed 117,000 deployments. On average each deployment has involved 10.3 nodes. The largest deployment involved 496 nodes. To our knowledge, the deployed operating systems are mostly based on Linux (all flavors) with a sprinkling of FreeBSD. Although the Grid'5000 use case does not exercise all the goals targeted by Kadeploy3 (e.g., scalability), it shows the tool's adequacy with regard to most characteristics, such as reliability.

Curie Petascale Supercomputer

We had the opportunity to evaluate Kadeploy3 on the Curie [START_REF]The Curie supercomputer[END_REF] supercomputer owned by GENCI (http://www.genci.fr/) and operated by CEA (http:// www.cea.fr). 2088 nodes were available to perform the test and the goal was to deploy the production environment. After a single administrative cycle, 2015 nodes where successfully deployed. This prove the efficiency and the reliability of Kadeploy3 in a large scale production infrastructure.

Virtual testbed

Validating scalability on large physical infrastructures can become complex (we only had access several hours to the Curie supercomputer since it is used for production purpose) because it requires privileged rights on many components (e.g., access to management cards, modification of PXE profiles, etc). Thus we chose to build our own large-scale virtual testbed on Grid'5000, leveraging important features such as link-layer isolation, and Kadeploy3 of course.

We performed an experiment where we used 635 physical nodes of the Grid'5000 testbed. Depending on the nodes capabilities, we launched a variable number of KVM virtual machines. In total, 3,999 virtual machines were launched and participated in a single virtual network (despite the physical nodes where located on four different geographical sites). Then we installed all the required servers: DHCP, TFTP, MySQL, HTTP server, Kadeploy3. Once the testbed was launched, we were able to perform deployments within a single cluster of 3,999 nodes. During the largest run, a 430 MB environment was installed on 3,838 virtual machines in less than an hour. 161 virtual nodes were lost due to network or KVM issues. A significant amount of time was also wasted because of the high latency between distant geographical sites (10-20 ms), which affected some infrastructure services like DHCP and the PXE protocol.

Wrapping-up

We think that Kadeploy3 can help system administrators of large scale clusters to save a precious time by reducing the OS provisioning time. The best way to be convinced is to have a try. Kadeploy3 is free software (CeCill 2 license) written in Ruby and available from http://kadeploy3.gforge.inria.fr/. Source code can be downloaded as well as Debian and RPM packages. Kadeploy3 is configured thanks to few YAML files and to help administrators, a complete guide describes the entire installation and configuration steps.