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

Pierrick Gaudry
email: pierrick.gaudry@loria.fr

Louise Huot
email: louise.huot@lip6.fr

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

Sub-Cubic Change of Ordering for Gröbner Basis. A Probabilistic Approach

Keywords: I.1.2 [Computing Methodologies]: Symbolic and Algebraic Manipulation; F.2.2 [Theory of Computation]: Analysis of Algorithms and Problem Complexity ALGORITHMS, EXPERIMENTATION, THEORY Polynomial systems, Gröbner basis, change of ordering

HAL is

INTRODUCTION

In all this paper, we consider the fundamental problem of Polynomial System Solving (PoSSo for short). More precisely, we focus on the complexity of computing a LEX Gröbner basis of a zerodimensional ideal. In the sequel, we denote by D the finite number of the corresponding solutions counted with multiplicities in an algebraic closure of the coefficient field.

For the particular case of approximating or computing a rational parametrization of all the solutions of a polynomial system with coefficients in a field of characteristic zero there exist algorithms with sub-cubic complexity in D. Indeed, if the number of real roots is logarithmic in D then the cost is O(12 n D 2 ) for the approximation, see [START_REF] Mourrain | Asymptotic acceleration of solving multivariate polynomial systems of equations[END_REF], and if the multiplicative structure of the quotient ring is known the cost is O n2 n D 5 2 for the rational parametrization, see [START_REF] Bostan | Fast algorithms for zero-dimensional polynomial systems using duality[END_REF]. However, to the best of our knowledge, there is no better bound than O(nD 3 ) for the complexity of computing a LEX Gröbner basis.

This complexity bound for solving the PoSSo problem is obtained by using the usual algorithm to compute a LEX Gröbner basis. This algorithm consists in two steps. First by computing a degree reverse lexicographical (DRL for short) Gröbner basis by using for instance the F5 algorithm [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases without reduction to zero (F5)[END_REF] whose complexity is bounded by O (ne ωn d ωn ) arithmetic operations [START_REF] Bardet | Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems[END_REF] where d is the maximal degree of the input equations and ω is the exponent in the complexity of multiplying two dense matrices (2 ≤ ω<2.3727 from [START_REF] Williams | Multiplying matrices faster than Coppersmith-Winograd[END_REF]). Then, the LEX Gröbner basis is computed using a change of ordering algorithm [START_REF] Faugère | Efficient computation of zero-dimensional Gröbner bases by change of ordering[END_REF][START_REF] Faugère | Fast algorithm for change of ordering of zero-dimensional Gröbner bases with sparse multiplication matrices[END_REF][START_REF] Faugère | Sparse FGLM algorithms[END_REF] e.g. the FGLM algorithm whose complexity is bounded by O nD 3 arithmetic operations which is in turn bounded by O nd 3n according to the Bézout bound. When d ≥ 44 (see Figure 1) the complexity of the PoSSo problem is then bounded by O nd 3n arithmetic operations.

In this paper, we propose a new probabilistic algorithm for solving the PoSSo problem. The change of ordering step (Fast FGLM on Figure 1) has a complexity in O (D ω ) bounded by O (d ωn ) where the notation O means that we omit the logarithmic factors in D or polynomial factors in n. As a consequence, the complexity of our algorithm (Fast PoSSo on Figure 1) and thus of the PoSSo problem is bounded by O (e ωn d ωn ) the complexity bound of the F5 algorithm. A deterministic version of this complexity result can be found in the extended version of this work [START_REF] Faugère | Polynomial systems solving by fast linear algebra[END_REF] but the range of applicability of the probabilistic version is wider. In order to obtain such a complexity for solving the PoSSo problem, we first propose in Section 3 a dense and fast version of the change of ordering for Shape Position ideals described in [START_REF] Faugère | Fast algorithm for change of ordering of zero-dimensional Gröbner bases with sparse multiplication matrices[END_REF][START_REF] Faugère | Sparse FGLM algorithms[END_REF]. In order to obtain a sub-cubic variant of this algorithm, we focus on its dominant part, the computation of the Krylov iterates associated to a square matrix of size D × D. We propose to use the algorithm of Keller-Gehrig [START_REF] Keller-Gehrig | Fast algorithms for the characteristic polynomial[END_REF] for computing these iterates in O (D ω ) which provides us the expected complexity.

Let I⊂K[x1,...,xn] be the ideal of which we look for the solutions. The input of this change of ordering algorithm is the DRL Gröbner basis of I and the matrix representation, denoted Tn, of the multiplication by xn in the quotient ring K[x1,...,xn]/I. From [START_REF] Faugère | Efficient computation of zero-dimensional Gröbner bases by change of ordering[END_REF], computing Tn can be done in O nD 3 arithmetic operations in K. We thus need a way to reduce the cost, to at most sub-cubic, of the computation of Tn. Using the study of the shape of DRL Gröbner bases by Moreno-Socías [START_REF] Moreno-Socías | Degrevlex Gröbner bases of generic complete intersections[END_REF] we actually show in Section 4 that, in the generic case, no arithmetic operation is required to build the matrix Tn (Theorem 8). Note that this was already heuristically known in [START_REF] Faugère | Sparse FGLM algorithms[END_REF]. Hence, we remove the heuristic nature of this result.

Moreover, for non-generic polynomial systems, using results of Galligo [START_REF] Galligo | A Propos du Théorème de Préparation de Weierstrass[END_REF], Bayer and Stillman [START_REF] Bayer | A theorem on refining division orders by the reverse lexicographic order[END_REF] and Pardue [START_REF] Pardue | Nonstandard Borel-Fixed Ideals[END_REF] about Generic initial ideals we prove (Corollary 14) that a generic linear change of variables bring us back to this case. As a consequence we obtain our main result about change of ordering. THEOREM 1. Let I be a generic ideal of K[x1,...,xn] of dimension zero. If I is in Shape Position then given its DRL Gröbner basis its LEX Gröbner basis can be computed in O (D ω ) arithmetic operations in K. In the case where I is non-generic and radical we obtain the same complexity up to a change of variables chosen in a non-empty Zariski open subset of GL (K,n).

The radical assumption in the non-generic case is required to ensure that after a generic linear change of variables the ideal is in Shape Position (using the Shape Lemma [START_REF] Gianni | Algebraic solution of systems of polynomial equations using Gröbner bases[END_REF][START_REF] Lakshman | On the complexity of computing a Gröbner basis for the radical of a zero dimensional ideal[END_REF]). However, even if the ideal is not radical our algorithm (and complexity result) is still correct if the ideal is in Shape Position after a generic linear change of variables. The characterization of such zero-dimensional ideals has been done in [START_REF] Becker | The shape of the shape lemma[END_REF].

Finally, by using this result in Section 5 we present our new algorithm for polynomial systems solving using Gröbner basis, its complexity and its probability of success. Moreover, as presented in the end of this section although our result seems theoretical we obtain significant improvements in practice.

Related work. Since we focus on Shape Position (possibly up to a linear change of variables) ideals the output of our algorithm for solving the PoSSo problem i.e. as a representation of the solutions, is similar (up to a normalization) to a rational univariate representation (RUR for short) introduced by Rouillier [START_REF] Rouillier | Solving zero-dimensional systems through the rational univariate representation[END_REF]. Given the multiplicative structure of the quotient ring, the complexity of the algorithm in [START_REF] Rouillier | Solving zero-dimensional systems through the rational univariate representation[END_REF]i si nO(nD 5 ) arithmetic operations in K which is decreased to O(n2 n D 5 2 ) in [START_REF] Bostan | Fast algorithms for zero-dimensional polynomial systems using duality[END_REF]. The main difference between [START_REF] Bostan | Fast algorithms for zero-dimensional polynomial systems using duality[END_REF][START_REF] Rouillier | Solving zero-dimensional systems through the rational univariate representation[END_REF] and our work is that the multiplicative structure of the quotient ring is not assumed to be known. In [START_REF] Faugère | Fast algorithm for change of ordering of zero-dimensional Gröbner bases with sparse multiplication matrices[END_REF][START_REF] Faugère | Sparse FGLM algorithms[END_REF], for generic ideals it is heuristically stated that a sufficient part of this multiplicative structure can be known without arithmetic operation. In this work, we prove this heuristic and extend its scope of applicability.

Contrary to the RUR where one looks for a separating variable, to compute the matrix representation of the multiplication by xn in the quotient ring we do not need that xn separates the variety. Hence, in some cases where the RUR is not applicable (i.e. after a generic linear change of coordinates the smallest variable is not separating) it is possible to compute with no arithmetic operations the corresponding multiplication matrix. Thus, we can compute its minimal polynomial and obtain the univariate polynomial of the lexicographical Gröbner basis. Note that if the RUR is not applicable then the ideal is not in Shape Position and our complete strategy for solving the PoSSo problem cannot be applied. However, the univariate polynomial that we have computed gives a significant information on the solutions which can be sufficient for instance in the case of finite fields.

NOTATIONS

From now on, K denotes a field and I⊂K[x1,...,xn] denotes an ideal in with a finite number D of solutions counted with mul-

tiplicities in K. A monomial of K[x1,...,xn] is denoted x α = x α 1 1 •••x αn n
with α =( α1,...,αn) ∈ N n . The quotient ring K[x1,...,xn]/I is denoted RI. The set of invertible matrices of size n × n with coefficients in K is denoted GL (K,n) and g •I with g ∈ GL (K,n) denotes the ideal {f (g • x) | f ∈I}where x is the vector (x1,...,xn).

Once a monomial ordering > on K[x1,...,xn] is fixed we define

• LT> (f ), the leading term of f w.r.t. >;

• in> (I)={LT> (f ) | f ∈I}, the initial ideal of I w.r.t.

>;

•G >, the reduced Gröbner basis of I w.r.t. >;

• E> (I)={LT> (f ) | f ∈G>}, the stair of I w.r.t. > i.e. a minimal set of generators of in> (I).

The quotient ring RI is a K-vector space of dimension D. Its canonical basis w.r.t. the ordering > is given by

B> (I)={x α | x α / ∈ in> (I)} = {ǫD > ••• >ǫ1 =1} .
The normal form map gives a representative of any polynomial f in RI w.r.t. this basis; we denote by NF> (f ) this unique polynomial of the form D i=1 ciǫi where ci ∈ K such that f -NF> (f ) ∈I. The normal form map thus provides a representation of RI as a D-dimensional K-vector space. The matrix representation of the multiplication by xi in RI seen as the vector space with the basis B> (I) is called the multiplication matrix by xi and is denoted Ti. The columns of this matrix thus consist of the coefficients of NF> (xiǫj) for j =1,...,D.

FAST CHANGE OF ORDERING FOR SHAPE POSITION IDEALS

In [START_REF] Faugère | Fast algorithm for change of ordering of zero-dimensional Gröbner bases with sparse multiplication matrices[END_REF], Faugère & Mou propose a probabilistic algorithm which given the reduced Gröbner basis w.r.t. a monomial ordering >1 of an ideal I⊂K[x1,...,xn] computes the LEX Gröbner basis -if it is in Shape Position -ofI. The idea is to take advantage of the shape of the LEX Gröbner basis (assumed to be known) to design a very efficient change of ordering algorithm.

Throughout this section, the multiplication matrix Tn is assumed to be known and I is assumed to be in Shape Position. That is to say the LEX Gröbner basis of I has the following shape: Computing hn. The polynomial hn is then given by the minimal polynomial of the multiplication matrix Tn. In order to reduce its computation to the solving of a linear Hankel system one can use the first part of the Wiedemann probabilistic algorithm [START_REF] Wiedemann | Solving sparse linear equations over finite fields[END_REF]. More precisely, first one computes the linearly recurrent sequence S =[ ( r,T j n 1) | j =0 ,...,2D -1] where r is a random column vector of K D , 1 =( 1 , 0,...,0) t is the vector representing the monomial 1 in RI and (•, •) denotes the scalar product. Then, by using the Berlekamp-Massey algorithm [START_REF] Massey | Shift-register synthesis and bch decoding[END_REF] one computes the minimal polynomial μ of S.

G> lex = {x1 -h1(xn),...,
has NF> 1 xi -D-1 k=0 c i,k x k n =0
. By translating this equation as a linear combination in RI seen as a K-vector space, then by multiplying the resulting equation by T j n for j =0,...,D-1 and taking the scalar product with r we deduce that 0= r,T j n (Ti1) -

D-1 k=0 c i,k r,T k+j n 1 . (3a)
For each polynomial hi for i =1 ,...,n -1 the equation (3a) allows to construct a linear Hankel system defined by the linearly recurrent sequence S of which c i,k for k =0,...,D-1 are the solutions. From [START_REF] Jonckheere | A simple Hankel interpretation of the Berlekamp-Massey algorithm[END_REF], this linear Hankel system is non-singular since the rank of the Hankel matrix is given by the degree of the minimal polynomial of S which is exactly D in our case. Note that one can assume w.l.o.g. that xi ∈ B> 1 (I). Hence, the vectors w i = Ti1 are known without arithmetic operations. For more details see [START_REF] Faugère | Fast algorithm for change of ordering of zero-dimensional Gröbner bases with sparse multiplication matrices[END_REF]. In [START_REF] Faugère | Sparse FGLM algorithms[END_REF] the authors propose a deterministic version of their algorithm for Shape Position ideal. Note that their algorithm computes the LEX Gröbner basis of the radical of the ideal I given in input if it is in Shape Position.

THEOREM 2( F AUGÈRE &MOU [START_REF] Faugère | Fast algorithm for change of ordering of zero-dimensional Gröbner bases with sparse multiplication matrices[END_REF][START_REF] Faugère | Sparse FGLM algorithms[END_REF]). Let I be an ideal of K[x1,...,xn]. Let r be a random column vector of K D and let T be the transpose of the multiplication matrix Tn w.r.t. a monomial ordering >.I f I is in Shape Position then given the reduced Gröbner basis of I w.r.t. > and the vectors T j r for j = 0,...,2D -1, there exists a probabilistic algorithm which computes the LEX Gröbner basis of I in O nD log 2 D log log D arithmetic operations in K.

If the radical of I is in Shape Position then given the reduced Gröbner basis of I w.r.t. > and the vectors T j n 1,T j n w1,..., T j n wn-1 for j =0,...,2D -1, there exists a deterministic algorithm which computes the LEX Gröbner basis of the radical of I in O nD 2 log D log log D (by omitting logarithmic factors in q if K = Fq) arithmetic operations in K.

One issue remains to get a change of ordering algorithm with sub-cubic complexity in D given the matrix T n. Indeed, in [START_REF] Faugère | Fast algorithm for change of ordering of zero-dimensional Gröbner bases with sparse multiplication matrices[END_REF] the authors assume the matrix Tn sparse and compute iteratively the vectors T j r or T j n 1,T j n w1,...,T j n wn-1 for j =0,...,2D -1. However, when Tn is dense this yields a complexity in O D 3 arithmetic operations in K. In order to overcome this issue we use an algorithm of Keller-Gehrig [START_REF] Keller-Gehrig | Fast algorithms for the characteristic polynomial[END_REF] which computes these matrixvector products by multiplying O (log D) matrices. More precisely, first one computes T 2 ,T 4 ,...,T 2 ⌈log 2 D⌉ using binary exponentiation with ⌈log 2 D⌉ matrix products; then the vectors T j r for j =0 ,...,2D -1 are computed by induction in ⌈log 2 D⌉ steps:

T 2 (T r | r)= T 3 r | T 2 r T 4 T 3 r | T 2 r | T r | r = T 7 r | T 6 r | T 5 r | T 4 r T 8 T 7 r | T 6 r | ••• |r = T 15 r | T 14 r | ••• |T 8 r . . . (3b) until the product T 2 ⌈log 2 D⌉ T 2 ⌈log 2 D⌉ -1 r |•••
I)i nO D log D D ω-1 + n log D log log D (resp. O nD 2 log D D ω-2 +loglogD by omitting logarith- mic factors in q if K = Fq) arithmetic operations in K.
In the next section we investigate the computation of the matrix Tn.

COMPUTING TN

In this section we fix the first monomial ordering to the DRL ordering > drl . To compute the multiplication matrix Tn we need to compute the normal forms w.r.t. the DRL ordering of all the monomials ǫixn for i =1,...,D with ǫi ∈ B> drl (I). From [START_REF] Faugère | Efficient computation of zero-dimensional Gröbner bases by change of ordering[END_REF] the monomials ǫixn can be of three types. PROPOSITION 4 (FGLM [START_REF] Faugère | Efficient computation of zero-dimensional Gröbner bases by change of ordering[END_REF]). Let F = {xjǫi | 1 ≤ i ≤ D and 1 ≤ j ≤ n}\B> (I) be the border. Let t = ǫixj with i ∈{ 1,...,D} and j ∈{ 1,...,n}. One has the following three cases I. either t ∈ B> (I) and NF> (t)=t;

II. or t ∈ E> (I) i.e. t =L T > (g) for some g ∈G > hence, NF> (t)=t -g; III. or t = x k t ′ with t ′ ∈ F . Hence, denoting NF> (t ′ )= s l=1 α l ǫ l with t ′ >ǫ s, we have NF> (t)= NF> (x k NF> (t ′ )) = s l=1 α l NF> (ǫ l x k ).
In this section, thanks to the study of the stairs of generic ideals by Moreno-Socías [START_REF] Moreno-Socías | Degrevlex Gröbner bases of generic complete intersections[END_REF], we first show that for generic ideals and DRL ordering, all monomials of the form ǫixn are either in B> drl (I) or in E> drl (I). Hence, the multiplication matrix Tn can be computed very efficiently. Then, we show that, up to a generic linear change of variables, this result can be extended to any ideal.

In the sequel, the arithmetic operations will be the addition or the multiplication of two operands in K that are different from ±1 and 0. In particular we do not consider the change of sign as an arithmetic operation.

Generic case

DEFINITION 5. A generic sequence of polynomials F is a sequence of polynomials whose coefficients are indeterminates i.e. F =(f1,...,fs) with fi = α ci,αx α is in K[x1,...,xn] where K = k({ci,α}) and k is a field. A generic ideal is an ideal generated by a generic sequence of polynomials.

In [START_REF] Moreno-Socías | Degrevlex Gröbner bases of generic complete intersections[END_REF] it is shown that the intersection of the section of RI by

x d 1 i 1 ,...,x d n-2
i n-2 has steps of depth two and height one for any d1,...,dn-2 ≥ 0 and i1,...,in-2 ≤ n -1 all pairwise distinct. We illustrate this result on Figure 2 where for fixed value of d1,...,di-1,di+1,...,dn-1 we represent the corresponding monomials of E> drl (I) ∪ B> drl (I). The xn-axis (resp. xi-axis) corresponds to the degree in xn (resp. xi) of these monomials.

d i-1 i-1 ,x d i i+1 ,...,x d n-2
n-1 with I a generic ideal.

The shape of the stair in Figure 2 is formally stated in the following theorem.

THEOREM 6( M ORENO-SOCÍAS [START_REF] Moreno-Socías | Degrevlex Gröbner bases of generic complete intersections[END_REF]). Let I be a generic ideal of K[x1,...,xn] generated by (f1,...,fn). Let M be the set of monomials of K[x1,...,xn-1] and Bi = {m ∈M|mx We deduce of the previous theorem that generic ideals satisfy the following property. PROPOSITION 7. Let I be a generic ideal. Let t be a monomial in E> drl (I) i.e. a leading term of a polynomial in the DRL Gröbner basis of I.I fxn divides t then for all k ∈{1,...,n-1},

i n ∈ B> drl (I)}. Let δ = n i=1 (deg(fi) -1), δ * = n-1 i=1 (deg(fi) - 1) and σ =min δ * , ⌊ δ 2 ⌋ . Let μ = δ -2σ, then a. B0 = ••• = Bμ (
x k t xn ∈ in> drl (I).
PROOF. This result is deduced from the shape of the stairs of I. Let t = x α 1 1 •••x αn n be a leading term of a polynomial in G> drl divisible by xn i.e. αn > 0 and m

= x α 1 1 •••x α n-1
n-1 . We use the same notations as in Theorem 6.

From Theorem 6 item (d), since t ∈ E> drl (I) and αn > 0 we have αn >μand αn ≡ δ mod 2. Then, from Theorem 6 item (c), deg(m) is the maximal degree reached by the monomials in Bα n-1 . Thus x k m/ ∈ Bα n-1 for all k ∈{ 1,...,n -1}. As a consequence, for all k ∈{ 1,...,n -1} we have x k t xn ∈ in> drl (I).

A consequence of this result is that all the monomials of the form ǫixn where ǫi ∈ B> drl (I) are either of type (I) or of type (II)of Proposition 4. Hence, their normal form can be read on G> drl with no arithmetic operations and the multiplication matrix Tn can be computed very efficiently. This is summarized in the following result. THEOREM 8. Given G> drl the DRL Gröbner basis of a generic ideal I of dimension zero, the multiplication matrix Tn can be read from G> drl with no arithmetic operation.

PROOF. Suppose that there exists i ∈{1,...,D} such that t = xnǫi is of type (III). Hence, t = m LT> drl (g) for some g ∈G> drl and deg(m

) > 1 with xn ∤ m (otherwise ǫi / ∈ B). Then, there exists k ∈{1,...,n-1} such that x k | m. By consequence, from Proposition 7,wehaveǫi = m x k • x k LT> drl (g) xn
∈ in> drl (I) which yields a contradiction. Thus, all monomials t = xnǫi are either in B or in E> drl (I) and their normal forms are known and given either by t (if t ∈ B) or by changing the sign of some polynomial g ∈G > drl and removing its leading term. Note that by using a linked list representation (for instance), removing the leading term of a polynomial does not require arithmetic operation.

From Theorem 8 and Proposition 3, we obtain the following result. COROLLARY 9. Let I be a generic ideal in Shape Position. From the DRL Gröbner basis of I, its LEX Gröbner basis can be computed in O(log D(D ω + nD log D log log D)) arithmetic operations with a probabilistic algorithm.

However, polynomial systems coming from applications are usually not generic. Nevertheless, this difficulty can be bypassed by applying a linear change of variables. By studying the structure of the Generic initial ideal (see Remark 10)o fI -that is to say, the initial ideal of g •I for a generic choice of g in GL (K,n)we will show that results of Proposition 7 and Theorem 8 can be generalized to non generic ideals, up to a generic linear change of variables. Indeed, in [START_REF] Galligo | A Propos du Théorème de Préparation de Weierstrass[END_REF] Galligo shows that for the characteristic zero fields, the Generic initial ideal of any homogeneous ideal satisfies a more general property than Proposition 7. Later, Pardue [START_REF] Pardue | Nonstandard Borel-Fixed Ideals[END_REF] extends this result to the fields of positive characteristic. REMARK 10. Note that Generic initial ideal are not defined as an initial ideal whose coefficients are indeterminates. Its definition is given in Definition 11. To avoid ambiguity, in the sequel we always use the notation Gin (I) for Generic initial ideal as defined in Definition 11.

Non-generic case

DEFINITION 11. Let K be an infinite field and I be an homogeneous ideal of K[x1,...,xn]. There exists a non-empty Zariski open set U ⊂ GL (K,n) and a monomial ideal J such that in> drl (g •I)=J for all g ∈ U . The Generic initial ideal of I is denoted Gin (I) and is defined by J .

The proof of the existence of Gin (I) can be found in [7, p.351-358]. The next result, is a direct consequence of [START_REF] Bayer | A theorem on refining division orders by the reverse lexicographic order[END_REF][START_REF] Galligo | A Propos du Théorème de Préparation de Weierstrass[END_REF][START_REF] Pardue | Nonstandard Borel-Fixed Ideals[END_REF] and summarized in [7, p.351-358]. This result allows to extend, up to a linear change of variables, Proposition 7 to non-generic ideals. THEOREM 12. Let K be an infinite field of characteristic p ≥ 0. Let I be an homogeneous ideal of K[x1,...,xn] and J = Gin (I). For the DRL ordering, for all generators m of J ,i fx t i divides m and x t+1 i does not divide m then for all j<i , the monomial

x j x i m is in J if t ≡ 0m o d p.
Polynomial systems coming from applications are usually not homogeneous and Theorem 12 does not apply directly. Let f = d i=0 fi be an affine polynomial of degree d of K[x1,...,xn] where fi is an homogeneous polynomial of degree i. The homogeneous component of highest degree of f , denoted f h , is the homogeneous polynomial f d . Let I be an affine ideal i.e. generated by a sequence of affine polynomials. In the next proposition we highlight an homogeneous ideal having the same initial ideal than I. This allows to extend the result of Theorem 12 to affine ideals. PROPOSITION 13. Let I = f1,...,fs be an affine ideal. If (f h 1 ,...,f h s ) is a regular sequence of polynomials, then there exists a non-empty Zariski open subset Ua ⊂ GL (K,n) such that for all g ∈ Ua, E> drl (g •I)=E> drl Gin I h . PROOF. Let f be a polynomial. We denote by f a the polynomial f -f h . Let t ∈ in> drl (I), there exists f ∈Isuch that LT> drl (f )=t. Since, f ∈Iand (f h 1 ,...,f h s ) is assumed to be a regular sequence then there exist h1,...,hs ∈ K[x1,...,xn] s.t. f = s i=1 hifi = s i=1 hif h i + s i=1 hif a i with deg(hifi) ≤ deg(f ) for all i ∈{1,...,s} and there exists j ∈{1,...,s} such that deg(hjfj)=d e g ( f ). By consequence, 0 = s i=1 hif h i ∈ I h where I h is the ideal generated by {f h 1 ,...,f h s } and LT> drl (f )=L T> drl s i=1 hif h i . Thus, in> drl (I) is included in in> drl I h . It is straightforward that in> drl I h ⊂ in> drl (I) hence in> drl I h =in> drl (I).

For all g ∈ GL (K,n), since g is invertible the sequence (g • f1,...,g• fs) is also regular. Indeed, if there exists i ∈{1,...,s} such that g • fi is a divisor of zero in the quotient ring K[x1,...,xn]/ g • f1,...,g• fi-1 then fi is a divisor of zero in K[x1,...,xn]/ f1,...,fi-1 . Hence,

in> drl (g •I)=in> drl (g •I) h .
Moreover, g is a linear change of variables thus it preserves the degree. Hence, for all f ∈I,wehave(g • f ) h = g • f h . Finally, let Ua be the non-empty Zariski open subset of GL (K,n) such that for all g ∈ Ua, we have the equality in> drl g •I h = Gin I h . Thus, for all g ∈ Ua,wehavein> drl (g

•I)=in> drl (g •I) h = in> drl g •I h = Gin I h .
Hence, from the previous proposition, for a random linear change of variables g ∈ GL (K,n) we have in> drl (g •I)=Gin I h . Thus from Theorem 12, for all generators m of the monomial ideal in> drl (g •I) (i.e. m is a leading term of a polynomial in the DRL Gröbner basis of g •I)ifx t n divides m and x t+1 n does not divide m then for all j<nwe have

x j xn m ∈ in> drl (g •I) if t ≡ 0m o d p.
Therefore, in the same way as for generic ideals, the multiplication matrix Tn of g •Ican be read from its DRL Gröbner basis.

Moreover, the Shape Lemma [START_REF] Gianni | Algebraic solution of systems of polynomial equations using Gröbner bases[END_REF][START_REF] Lakshman | On the complexity of computing a Gröbner basis for the radical of a zero dimensional ideal[END_REF] states that radical ideals have, up to a generic linear change of variables, a LEX Gröbner basis in Shape Position. Hence, one can compute very efficiently the multiplication matrix Tn and then use the algorithm presented in Section 3 to compute the LEX Gröbner basis of g •I. This is summarized in the following corollary. Following this result, we propose another algorithm for polynomial systems solving.

FAST ALGORITHM FOR SOLVING THE POSSO PROBLEM

Let S⊂K[x1,...,xn] be a polynomial system generating a radical ideal denoted I. For any g ∈ GL (K,n), from the solutions of g •I one can easily recover the solutions of I. Let U be the nonempty Zariski open subset of GL (K,n) such that for all g ∈ U , in> drl (g •I)=Gin I h .I fg is chosen in U then the multiplication matrix Tn can be computed very efficiently. Indeed, from Section 4 all the monomials of the form ǫixn for i =1 ,...,D are in B> drl (g •I) or in E> drl (g •I) and their normal form are easily known. Moreover, from the Shape Lemma [START_REF] Gianni | Algebraic solution of systems of polynomial equations using Gröbner bases[END_REF][START_REF] Lakshman | On the complexity of computing a Gröbner basis for the radical of a zero dimensional ideal[END_REF], there exists U ′ a non-empty Zariski open subset of GL (K,n) such that for all g ∈ U ′ the ideal g •I admits a LEX Gröbner basis in Shape Position.I fg is also chosen in U ′ then we can use the algorithm presented in Section 3 to compute the LEX Gröbner basis of g •I. Hence, we propose in Algorithm 1 a Las Vegas algorithm to solve the PoSSo problem. This is a randomized algorithm whose output (which can be fail) is always correct. The end of this section is devoted to evaluate its complexity and its probability of success i.e. when the algorithm does not return fail. REMARK 15. Let S = {f1,...,fn} be a polynomial system of K[x1,...,xn]. Note that Algorithm 1 can be used if (f h 1 ,...,f h n ) is a regular sequence or not. However, if it is not regular then the complexity and the probability of failure are not well understood. Input : A polynomial system S⊂K[x1,...,xn] generating a radical ideal. Output: g in GL (K,n) and the LEX Gröbner basis of g •S or fail. 1 Choose any g in GL (K,n); 2 Compute G> drl the DRL Gröbner basis of g •S; 3i fTn can be read from G> drl then 4

Extract Tn from G> drl ; 5i f G> drl is in Shape Position then 6

From Tn and G> drl compute G> lex using the deterministic algorithm of Proposition 3; 7 return g and G> lex ;

8 return fail;

depend on the probability of failure of Wiedemann algorithm. Nevertheless, in practice when K is sufficiently large we can use the probabilistic version of the change of ordering for Shape Position ideals.

Algorithm 1 succeeds if the three following conditions are satisfied

1. g ∈ GL (K,n) is chosen in a non-empty Zariski open set U ′ such that for all g ∈ U ′ , g •I has a LEX Gröbner basis in Shape Position; 2. g ∈ GL (K,n) is chosen in a non-empty Zariski open set U such that for all g ∈ U , in> drl (g •I)=Gin I h ; 3. p =0or p>0 and for all m ∈ E> drl (g •I), deg xn (m) ≡ 0m o d p.
The existence of the non-empty Zariski open subset U ′ is proven in [START_REF] Gianni | Algebraic solution of systems of polynomial equations using Gröbner bases[END_REF][START_REF] Lakshman | On the complexity of computing a Gröbner basis for the radical of a zero dimensional ideal[END_REF]. Conditions (1) and ( 2) are satisfied if g ∈ U ∩ U ′ . Since, U and U ′ are open and dense, U ∩ U ′ is also a non-empty Zariski open set.

Probability of success of Algorithm 1

Usually the coefficient field of the polynomials is the field of rational numbers or a finite field. Assume that K = Fq or K = Q and we randomly choose in a finite subset of Q of size q. The Schwartz-Zippel lemma [START_REF] Schwartz | Fast probabilistic algorithms for verification of polynomial identities[END_REF][START_REF] Zippel | Probabilistic algorithms for sparse polynomials[END_REF] allows to bound the probability that the conditions (1) and ( 2) are not satisfied by d q where d is the degree of the polynomial defining U ∩ U ′ . Thus, in order to bound this failure probability we need to estimate the degree of the polynomials defining U and U ′ .

Construction of U ′ . Let I = f1,...,fn be a radical ideal of K[x1,...,xn]. Since I is radical, all its solutions are distinct. Therefore, let ai =( ai,1,...,ai,n) ∈ K n be an element of the algebraic set of solutions of I (recall that the cardinality of this set is D). Let g be a given matrix in GL (K,n). We denote by vi =( vi,1,...,vi,n) the point obtained after transformation of ai by g, i.e vi = g•a t i . To ensure that g•I admits a LEX Gröbner basis in Shape Position, g should be such that vi,n = vj,n for all couples of integers (i, j) verifying 1 ≤ j<i≤ D. Hence, let g =( gi,j) be a (n × n) matrix of unknowns, the polynomial P U ′ defining the non-empty Zariski open subset U ′ is then given as the determinant of the Vandermonde matrix associated to vi,n for i =1 ,...,D where vi =(vi,1,...,vi,n)=g • a t i . Therefore, we know exactly the degree of P U ′ which is D(D-1)

2

.

Construction of U . The non-empty Zariski open subset U is constructed (see [7, p.351-358]) as the intersection of non-empty Zariski open subsets U1,...,U δ of GL (K,n) where δ is the maximum degree of the generators of Gin I h . Let d be a fixed degree. Let K[x1,...,xn] d = R d be the set of homogeneous polynomials of degree d of K[x1,...,xn]. Let {f1,...,ft d } be a vector basis of I h d = I h ∩ R d . Let g =( gi,j) be a (n × n) matrix of unknowns and let M be a matrix representation of the map

I h d → g •I h d defined as follow: m1 ••• mN ••• g • f1 M =(Mi,j)= . . . . . . . . . . . . ••• g • ft d
where Mi,j is the coefficient of mj in g • fi and {m1,...

,
I h )= δ d=0 dim K (R d /I h d ). Thus, δ d=0 dim K (I h d )= δ d=0 dim K (R d )-D = n+δ n -D. By consequence, deg(PU ) ≤ δ n+δ n -D .
For ideals generated by f1,...,fn s.t. (f h 1 ,...,f h n ) is a regular sequence, according to the Macaulay bound, δ can be bounded by n i=1 (deg(fi) -1) + 1. Note that the Macaulay bound gives also a bound on deg xn (m) for all m ∈ E> drl (g •I). To conclude, the probability that conditions (1) and ( 2) are satisfied is greater than

1 - 1 q D(D -1) 2 +(∆-n +1) ∆+1 n -D ,
where ∆= n i=1 deg(fi) and if p =0or p> n i=1 (deg(fi) -1) + 1 then condition (3) is satisfied.

Complexity of Algorithm 1

The matrix Tn can be read from G> drl (test in Line 3 of Algorithm 1) if all the monomials of the form ǫixn are either in B> drl ( G> drl ) or in E> drl ( G> drl ).L e t Fn = {ǫixn | i = 1,...,D}, the test in Line 3 is equivalent to test if Fn ⊂ B> drl ( G> drl ) ∪ E> drl ( G> drl ). Since Fn contains exactly D monomials and B> drl ( G> drl )∪E> drl ( G> drl ) contains at most (n+1)D monomials; testing if Fn is included in B> drl ( G> drl )∪ E> drl ( G> drl ) can be done in at most O(nD 2 ) elementary operations which can be decreased to O(D) elementary operations if we use a hash table. Hence, the cost of the test in Line 4 of Algorithm 1 is negligible in comparison to the complexity of the algorithm in Proposition 3. Hence, the complexity of Algorithm 1 is given by the complexity of F5 algorithm to compute the DRL Gröbner basis of g •Iand Proposition 3. From [START_REF] Lazard | Gröbner bases, gaussian elimination and resolution of systems of algebraic equations[END_REF], the complexities of computing the DRL Gröbner basis of g •I or I are the same. Since it is straightforward to see that the number of solutions of these two ideals are also the same we obtain the main result of this paper about the complexity of the PoSSo problem. As previously mentioned, according to the Bézout bound the number of solutions D is bounded by the product of the degrees of the input equations. Since this bound is generically reached we get the following corollary. COROLLARY 19. Let K be a field of characteristic zero or a finite field Fq of sufficiently large characteristic. Let S = {f1,..., fn}⊂K[x1,...,xn] be a generic polynomial system generating a radical ideal. If the degree of each polynomial in S is equal to a parameter d then there exists a Las Vegas algorithm which solves the PoSSo problem in O(e ωn D ω ) arithmetic operations in K.

Benchmarks

In this section we discuss the impact of Algorithm 1 on the practical resolution of the PoSSo problem. Note that algorithms of Proposition 3 to compute the LEX Gröbner basis given the multiplication matrix Tn is of theoretical interest. Indeed, although in theory ω is bounded by 2.3727 in practice in our knowledge the best implementation of the matrix product uses Strassen algorithm [START_REF] Strassen | Gaussian elimination is not optimal[END_REF]. For instance this algorithm is implanted in MAGMA [START_REF] Bosma | The Magma algebra system. I. The user language[END_REF] or in LINBOX [START_REF] Dumas | LinBox: A generic library for exact linear algebra[END_REF]. Thus, in practice ω =log 2 (7) ∼ 2.8073.

As a consequence, in practice the sparse version of Faugère and Mou [START_REF] Faugère | Fast algorithm for change of ordering of zero-dimensional Gröbner bases with sparse multiplication matrices[END_REF][START_REF] Faugère | Sparse FGLM algorithms[END_REF] is much more efficient than the fast version using dense matrix multiplication. Hence, in the following experiments we use the sparse version of change of ordering. In Table 1,w e give the time to compute the LEX Gröbner basis using the usual algorithm (F5 followed by a change of odering algorithm) and Algorithm 1. This time is divided into three steps, the first is the time to compute the DRL Gröbner basis using F5 algorithm, the second is the time to compute the multiplication matrix Tn and the last part is the time to compute the LEX Gröbner basis given Tn using the algorithm in [START_REF] Faugère | Fast algorithm for change of ordering of zero-dimensional Gröbner bases with sparse multiplication matrices[END_REF]. Since, this algorithm takes advantage of the sparsity of the matrix Tn we also give its density. We also give the number of normal forms to compute (i.e. the number of terms of the form ǫixn that are not in B> drl (I) or in E> drl (I) (resp. in B> drl (g •I) or in E> drl (g •I)).

The experiments are performed on various polynomial systems such as random systems (n dense polynomials of degree d with random coefficients), systems coming from economical problems [START_REF] Morgan | Solving Polynominal Systems Using Continuation for Engineering and Scientific Problems[END_REF] named "Eco" and systems coming from the resolution of the elliptic curve discrete logarithm problem on Edwards curves [START_REF] Faugère | Using symmetries in the index calculus for elliptic curves discrete logarithm[END_REF] named "Edwards (weights)" or on the "Well Know Group" 3 of the IPSEC Oakley key determination [START_REF] Faugère | Symmetrized summation polynomials: Using small order torsion points to speed up elliptic curve index calculus[END_REF][START_REF] Orman | The oakley key determination protocol[END_REF] named "Oakley".

We also present experiments on a "pathological" case for our algorithm in the sense that the system in input is already a DRL Gröbner basis. Thus, while the usual algorithm does not have to compute the DRL Gröbner basis, our algorithm needs to compute the DRL Gröbner basis of g •I. The system in input is of the form S = {f1,...,fn}⊂F65521[x1,...,xn] with LT> drl (fi)=x 2 i . Hence, the monomials in the basis B> drl (I) are all the monomials of degree at most one in each variable. The degree of the ideal D is then 2 n . The monomials ǫixn that are not in B> drl (I) or in E> drl ( S ) are of the form x 2 n m where m is a monomial in x1,...,xn-1 of total degree greater than zero and linear in each variable. By consequence, using the usual algorithm we have to compute 2 n-1 -1 normal forms to compute only Tn. In the whole of Table 1, we omit the coefficient field when it is F65521. REMARK 20. In practice, before applying a linear change of variables we check if the system is in the generic case (corresponding to the column labelled "Generic case" in Table 1). We apply a change of variables only if it is required to compute very efficiently the matrix Tn and to obtain a Shape Position ideal. In this generic case, our algorithm is as efficient as the usual algorithm but provide a better complexity bound. It is the case for instance when solving the elliptic curve discrete logarithm problem as in [START_REF] Faugère | Using symmetries in the index calculus for elliptic curves discrete logarithm[END_REF].

One can note in Table 1 that in the usual algorithm, when the system is not in the "generic case", the bottleneck of the resolution of the PoSSo problem is the change of ordering due to the construction of the multiplication matrix Tn. Since our algorithm allows to compute very efficiently the matrix Tn (for instance for the pathological example with n =1 1 , less than one second in comparison to 7 520 seconds for the usual algorithm), the most time consuming step becomes the computation of the DRL Gröbner basis.

Moreover, still when the system is not in the "generic case" the total running time of our algorithm is far less than that of the usual algorithm. For instance, for the system "Edwards" with n =5the PoSSo problem can now be solved in less than six hours whereas we could not solve this instance of the PoSSo problem using the usual algorithm. REMARK 21. In Table 1, for the "Oakley" example we do not give the time for the change of ordering using the usual algorithm because it is not implemented in FGb for K = F 2 31 . However, this example shows that our method still works in characteristic two. Indeed, with the usual algorithm we need to compute 480 normal forms to compute Tn while with our algorithm the number of normal forms is decreased to 0.

We do not have explanations for all the benefits in practice of our method. Especially why the computation of the LEX Gröbner basis is speeded up for the "Eco" examples while the density of the matrix is increased. This is probably due to a particular structure. In general our method seems more efficient in practice. Actually, for the moment we do not find any counterexample.

dFGLM O d 3n F5OFigure 1 :

 3n1 Figure 1: Dominant step in the complexity (ordinate axis) of the PoSSo problem.

  Finally, if deg(μ)=D one has μ = hn. Computing h1,...,hn-1. Let us write hi = D-1 k=0 c i,k x k n where the c i,k are unknown. By noting that xi -hi(xn) ∈Ione

  |r where the notation (r1| ...|r k ) is the matrix with D rows and k columns obtained by joining the column vectors ri vertically. As a consequence, we obtain the following result. PROPOSITION 3. Let I be an ideal of K[x1,...,xn].IfI (resp. the radical of I)isinShape Position then given the reduced Gröbner basis of I w.r.t. a monomial ordering > and the associated multiplication matrix Tn there exists a probabilistic (resp. deterministic) algorithm which computes the LEX Gröbner basis of I (resp. of the radical of

2 height 1 Figure 2 :

 212 Figure 2: Intersection of sections of the quotient ring RI by x d 1 1 ,...,x

  plateau) and Bi = Bi+1 for μ<i<δand i ≡ δ mod 2 (depth two); b. The leading term of the polynomials in G> drl of degree 0 in xn have degree at most σ +1= σ; c. The leading term of the polynomials in G> drl of degree α in xn with μ<α≤ δ +1with α ≡ δ mod 2 are all of total degree d + α where d =m a x ( d e g ( m) | m ∈ Bα-1). Moreover, all these leading terms are exactly given by t = mx α n for all m ∈ Bα-1 of degree d (height one); d. There is no leading term of polynomials in G> drl of degree 1,...,μin xn (plateau) or of degree α in xn with α>δ+1or μ ≤ α ≤ δ and α ≡ δ mod 2 (depth two).

COROLLARY 14 .

 14 Let K be an infinite field of characteristic p ≥ 0. Let I = f1,...,fn be a zero-dimensional ideal of K[x1,...,xn] s.t. (f h 1 ,...,f h n ) is a regular sequence. There exists a non-empty Zariski open subset U of GL (K,n) such that for all g ∈ U , the arithmetic complexity of computing the multiplication matrix by xn of g •I given its DRL Gröbner basis can be done without arithmetic operation. If p>0 this is true only if deg xn (m) ≡ 0m o d p for all m ∈ E> drl (g •I). Consequently, under the same hypotheses and if I is a radical ideal, the complexity of computing the LEX Gröbner basis of g•I given its DRL Gröbner basis can be bounded by O(log D(D ω +nD log D log log D)) (or O(nD ω log D) with a deterministic algorithm) arithmetic operations in K.

REMARK 16 .

 16 The test in Line 5 in Algorithm 1 is performed by the beginning of the deterministic algorithm of Proposition 3. Indeed, this algorithm computes for sure the univariate polynomial in K[xn] in the LEX Gröbner basis of g •S . If this polynomial is of degree D then the ideal is in Shape Position. REMARK 17. At Line 6 of Algorithm 1 we use the deterministic version of the change of ordering for Shape Position ideals (Section 3) so that the probability of failure of Algorithm 1 does not Algorithm 1: Fast PoSSo.

THEOREM 18 .

 18 Let K be a field of characteristic zero or a finite field Fq of sufficiently large characteric p. Let S = {f1,...,fn}⊂ K[x1,...,xn] be a polynomial system generating a zero-dimen-sional radical ideal I = S of degree D.I f(f h 1 ,...,f h n ) is a regular sequence such that the degree of each polynomial is uniformly bounded by a parameter d then there exists a Las Vegas algorithm which solves the PoSSo problem in O(ne ωn d ωn + n log D(D ω + D log D log log D)) arithmetic operations. PROOF. When f h 1 ,...,f h n is a regular sequence of polynomials the complexity of computing the DRL Gröbner basis of S or g •S is bounded by [1, 20] O n nd+1 n ω = O (ne ωn d ωn ) arithmetic operations in K. From this DRL Gröbner basis, according to Corollary 14, the multiplication matrix Tn can be computed without arithmetic operations in K. Finally, from Tn and the DRL Gröbner basis, thanks to Proposition 3 and Corollary 14 the LEX Gröbner basis can be computed by a probabilistic (respectively deterministic) algorithm in O(D log D(D ω-1 + n log D log log D)) (respectively O(nD ω log D)) arithmetic operations in K.

  mN } is the set of monomials in R d .I n[ 2, 7], the polynomial PU d defining U d is constructed as a particular minor of size t d of M . Since each coefficient in M is a polynomial in K[g1,1,...,gn,n] of degree d, the degree of PU d is d•t d . Finally, since U d is open and dense for all d =1 ,...,δ we deduce that U = ∩ δ d=1 U d is a non-empty Zariski open set whose defining polynomial, PU , is of degree δ d=1 d • t d ≤ δ δ d=1 t d . Moreover, D =d i m K (K[x1,...,xn]/

Table 1 :

 1 Comparison of the usual algorithm for solving the PoSSo problem and Algorithm 1, the proposed algorithm. Computation with FGb on a 3.47 GHz Intel Xeon X5677 CPU.

	System	n	D	Algorithm Generic case	G> drl	Tn	#NF	Density	G> lex	Total
	Random d =2	15 32 768	usual This work	× Ye s	1 580s 1 580s	41.5s 41.5s	0 0	18.52% 18.52%	1 330s 1 330s	2 950s 2 950s
	Random d =6	6	46 656	usual This work	× Ye s	632s 632s	20.3s 20.3s	0 0	8.36% 8.36%	1 700s 1 700s	2 350s 2 350s
	Random d =30	3	27 000	usual This work	× Ye s	48.7s 48.7s	0.9s 0.9s	0 0	2.20% 2.20%	95.6s 95.6s	145s 145s
	Oakley F 2 31	5	4 096	usual This work	× No	2.97s 2.85s	Rem. 21 0.08s	480 0	6.79%	2.44s	5.37s
		13	2 048	usual This work	× No	28.2s 12.0s	36.5s 0.18s	1 153 0	12.09% 27.52%	0.43s 0.23s	65.1s 12.4s
	Eco	14	4 096	usual This work	× No	176s 57.0s	1 100s 0.74s	2 353 0	11.50% 26.41%	1.47s 1.23s	1 280s 59.0s
		15	8 192	usual This work	× No	1 030s 348s	> 2 days 3.47s	4 853 0	24.95%	30.6s	> 2 days 382s
	Edwards	5	65 536	usual This work	× No	12 300s 12 300s	> 2 days 40.8s	0	9.31%	7 820s	> 2 days 20 200s
	Edwards weights	5	65 536	usual This work	× Ye s	566s 566s	15.1s 15.1s	0 0	3.30% 3.30%	2 150s 2 150s	2 730s 2 730s
		9	512	usual This work	× No	0s < 0.01s	12.8s < 0.01s	255 0	32.81% 23.68% < 0.01s 0.01s	12.8s < 0.01s
	Pathological	11	2 048	usual This work	× No	0s 5.02s	7 520s 0.15s	1 023 0	31.93% 21.53%	23.0s 0.13s	7 540s 5.28s
		16 65 536	usual This work	× No	0s 38 100s	> 2 days 32 767 195s 0	18.33%	14 300s	> 2 days 52 600s

ACKNOWLEDGMENTS

The authors would like to thanks André Galligo and Daniel Lazard for fruitful discussions about generic initial ideals and Vanessa Vitse for providing us with the pathological example. This work was partly supported by the HPAC grant of the French National Research Agency (HPAC ANR-11-BS02-013).