Luk Bettale
email: l.bettale@oberthur.com

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

Ludovic Perret
email: ludovic.perret@lip6.fr

Solving Polynomial Systems over Finite Fields: Improved Analysis of the Hybrid Approach

The Polynomial System Solving (PoSSo) problem is a fundamental NP-Hard problem in computer algebra. Among others, PoSSo have applications in area such as coding theory and cryptology. Typically, the security of multivariate public-key schemes (MPKC) such as the UOV cryptosystem of Kipnis, Shamir and Patarin is directly related to the hardness of PoSSo over finite fields. The goal of this paper is to further understand the influence of finite fields on the hardness of PoSSo. To this end, we consider the so-called hybrid approach. This is a polynomial system solving method dedicated to finite fields proposed by Bettale, Faugère and Perret (Journal of Mathematical Cryptography, 2009). The idea is to combine exhaustive search with Gröbner bases. The efficiency of the hybrid approach is related to the choice of a trade-off between the two methods. We propose here an improved complexity analysis dedicated to quadratic systems. Whilst the principle of the hybrid approach is simple, its careful analysis leads to rather surprising and somehow unexpected results. We prove that the optimal trade-off (i.e. number of variables to be fixed) allowing to minimize the complexity is achieved by fixing a number of variables proportional to the number of variables of the system considered, denoted n. Under some natural algebraic assumption, we show that the asymptotic complexity of the hybrid approach is 2 (3.31-3.62 log 2 (q) -1 ) n , where q is the size of the field (under the condition in particular that log(q) n). This is to date, the best complexity for solving PoSSo over finite fields (when q > 2). We have been able to quantify the gain provided by the hybrid approach compared to a direct Gröbner basis method. For quadratic systems, we show (assuming a natural algebraic assumption) that this gain is exponential in the number of variables. Asymptotically, the gain is 2 1.49 n when both n and q grow to infin-

INTRODUCTION

The purpose of this paper is to study the complexity of solving the Polynomial System Solving (PoSSo) problem over finite fields. This problem, that will be denoted by PoSSo q , is as follows: Polynomial System Solving over Finite Fields (PoSSo q ) Let q = p k , where p is prime and k > 0. Input: f 1 (x 1 , . . . , x n ), . . . , f m (x 1 , . . . , x n ) ∈ F q [x 1 , . . . , x n ]. Goal: find a vector z 1 , . . . , z n ∈ F n q such that:

f 1 (z 1 , . . . , z n ) = • • • = f m (z 1 , . . . , z n ) = 0.
PoSSo q typically arises in area such as cryptography and coding theory (but not limited to). In cryptology, the hardness of PoSSo q is now a subject of major interest, e.g. [START_REF] Kipnis | Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization[END_REF][START_REF] Faugère | Algebraic cryptanalysis of Hidden Field Equation (HFE) cryptosystems using Gröbner bases[END_REF][START_REF] Faugère | Algebraic cryptanalysis of mceliece variants with compact keys[END_REF][START_REF] Courtois | Cryptanalysis of block ciphers with overdefined systems of equations[END_REF][START_REF] Dinur | Cube attacks on tweakable black box polynomials[END_REF][START_REF] Cid | Algebraic aspects of the advanced encryption standard[END_REF][START_REF] Courtois | Algebraic cryptanalysis of the data encryption standard[END_REF][START_REF] Faugère | Improving the Complexity of Index Calculus Algorithms in Elliptic Curves over Binary Field[END_REF][START_REF] Albrecht | Polly cracker, revisited[END_REF][START_REF] Kipnis | Unbalanced oil and vinegar signature schemes[END_REF][START_REF] Courtois | SFLASHv3, a fast asymmetric signature scheme[END_REF][START_REF] Sakumoto | Public-key identification schemes based on multivariate quadratic polynomials[END_REF][START_REF] Sugita | Algebraic cryptanalysis of 58-round SHA-1[END_REF][START_REF] Faugère | Cryptanalysis of minrank[END_REF]. In one hand, this problem is used as a trapdoor to design many cryptographic primitives, mostly in multivariate cryptography [START_REF] Matsumoto | Public quadratic polynomial-tuples for efficient signature-verification and message-encryption[END_REF][START_REF] Patarin | Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): two new families of asymmetric algorithms[END_REF][START_REF] Wolf | Taxonomy of Public Key Schemes based on the problem of Multivariate Quadratic equations[END_REF]. On the other hand, the security of many cryptosystems reduce trough algebraic attacks [3,[START_REF] Faugère | Algebraic cryptanalysis of Hidden Field Equation (HFE) cryptosystems using Gröbner bases[END_REF][START_REF] Sala | Gröbner Bases, Coding, and Cryptography[END_REF] to PoSSo q .

From a complexity-theoretical point of view, PoSSo q is NP-Hard independently of the size q [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]. Thus, any algorithm for PoSSo q should be exponential in the worth case. However, this does not exclude that large family of PoSSo q instances can be solved in subexponential or polynomial complexity. In addition, the exact exponent occurring in algorithms of exponential complexity is often a critical question in applications.

The general question we want to address here is how much the restriction to finite fields influence the hardness of PoSSo ?

Hybrid Approach. In [START_REF] Bettale | Hybrid approach for solving multivariate systems over finite fields[END_REF], we have described a rather simple Gröbner-basis based method taking advantage of the finite field structure: the so-called hybrid approach. The idea is to mix exhaustive search and Gröbner bases [START_REF] Buchberger | Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal[END_REF][START_REF] Buchberger | Computer algebra symbolic and algebraic computation[END_REF][START_REF] Buchberger | Bruno buchberger's phd thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal[END_REF] computation. In what follows, hybrid approach will always refer to the Gröbnerbasis based method described in [START_REF] Bettale | Hybrid approach for solving multivariate systems over finite fields[END_REF]. The principle of such approach is to fix k -which is a parameter -among the n variables of the system considered and then compute q k Gröbner bases of smaller systems to recover the set of solutions. The efficiency of the hybrid approach depends upon a proper choice of the tradeoff k between the number of variables to be fixed and the cost of computing a Gröbner basis of the smaller sub-systems. At first glance, it is even not clear that a non-trivial trade-off exists (i.e. whether k = 0?). A first contribution of [START_REF] Bettale | Hybrid approach for solving multivariate systems over finite fields[END_REF] is to show that the hybrid approach brings a significant improvement in practice (with respect to a direct Gröbner basis computation). As an application, we have shown that the parameters of many multivariate schemes (which are directly based on the hardness of PoSSo q ) must be refined to achieve a cryptographic security level (i.e. > 2 80 operations). For instance, the hybrid approach has been used to attack previously recommended parameters of the UOV scheme [START_REF] Kipnis | Unbalanced oil and vinegar signature schemes[END_REF] (for instance, [START_REF] Bettale | Hybrid approach for solving multivariate systems over finite fields[END_REF][Table 4, first row] in a complexity as small as 2 37.75 . Remark that experiments performed in [START_REF] Bettale | Hybrid approach for solving multivariate systems over finite fields[END_REF] suggest that the optimal trade-off seems to be achieved for a small and constant value of k. We show in this paper that this intuition is actually false.

We mention that [START_REF] Bettale | Hybrid approach for solving multivariate systems over finite fields[END_REF] also laid the foundation for a theoretical analysis of the hybrid approach. It has been shown that the hybrid approach is beneficial (i.e. a non-trivial trade-off exists) if q is less than 2 0.62 ω n , where ω, 2 ω 3 is the linear algebra constant.

Related Works. The complexity of solving solving binary quadratic equations has been more particularly investigated in [START_REF] Yang | Theoretical analysis of xl over small fields[END_REF][START_REF] Yang | On asymptotic security estimates in xl and gröbner bases-related algebraic cryptanalysis[END_REF][START_REF] Bardet | On the complexity of solving quadratic boolean systems[END_REF]. The authors of [START_REF] Yang | Theoretical analysis of xl over small fields[END_REF] proposed an heuristic method -based on the so-called XL [START_REF] Kipnis | Cryptanalysis of the hfe public key cryptosystem by relinearization[END_REF] algorithm -of complexity O 2 0.875 n for solving PoSSo 2 (with quadratic equations). They propose to combine exhaustive search with XL. This is the so-called FXL. As pointed in [START_REF] Ars | Comparison between xl and gröbner basis algorithms[END_REF] XL can be viewed as a sub-optimal version of F 4 [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases (F4)[END_REF] (and consequently, FXL is a sub-optimal version of the hybrid approach). In addition, the exact assumptions that have to be verified by the input systems are unclear. Also, similar results have been announced in [START_REF] Yang | On asymptotic security estimates in xl and gröbner bases-related algebraic cryptanalysis[END_REF][Section 2.2], but there analysis relies on algorithmic assumptions (e.g., row echelon form of sparse matrices in quadratic complexity) that are not known to hold currently. Under these assumptions, the authors show that the most favorable trade-off between exhaustive search and row echelon form computations in the FXL algorithm is obtained by specializing 0.45 n variables (for q = 2). Recently, [START_REF] Bardet | On the complexity of solving quadratic boolean systems[END_REF] used an hybrid approach -and additional techniquesto further improve the solving of quadratic binary systems. The authors of [START_REF] Bardet | On the complexity of solving quadratic boolean systems[END_REF] proposed a deterministic algorithm for solving PoSSo 2 in O 2 0.841 n when m = n (i.e. same number of equations and variables). A probabilistic variant of their algorithm (Las Vegas type) has expected complexity O 2 0.792 n . They roughly estimate the actual threshold between their method and exhaustive search (whose cost is 4 log 2 n 2 n operations [START_REF] Bouillaguet | Fast exhaustive search for polynomial systems in f 2[END_REF]), which is as low as 200. Note that the complexity analysis in [START_REF] Bardet | On the complexity of solving quadratic boolean systems[END_REF] requires an algebraic assumption which is similar to [START_REF] Bettale | Hybrid approach for solving multivariate systems over finite fields[END_REF]. Such assumption will be also used here. From now on, we will always assume that q > 2.

The question of solving PoSSo q for a bigger q is quickly addressed in [START_REF] Yang | On asymptotic security estimates in xl and gröbner bases-related algebraic cryptanalysis[END_REF][Section 2.1]. More precisely, [START_REF] Yang | On asymptotic security estimates in xl and gröbner bases-related algebraic cryptanalysis[END_REF][Proposition 7, p. 5] describes an implicit method for finding the optimal number of variables to be fixed in FXL. For q = 2 8 , the best-tradeoff in FXL is obtained by fixing 0.049 n variables (assuming ω = 2). Using a different technique, we present also here an implicit method for finding the best-tradeoff with the hybrid approach. For example with q = 2 8 , we get the most favorable trade-off is obtained by fixing 0.07 n variables (assuming ω = 2.4).

The goal of this paper is to further improve the theoretical analysis initiated in [START_REF] Bettale | Hybrid approach for solving multivariate systems over finite fields[END_REF]. In particular, we address the following issues:

• What is the explicit asymptotic value of the best trade-off ?

• What is the asymptotic complexity the hybrid approach ?

• What is the gain of the hybrid approach over a direct Gröbner basis method ?

Organization of the Paper. After this introduction, the paper is organized as follows. Sect. 2 recalls some results from [START_REF] Bettale | Hybrid approach for solving multivariate systems over finite fields[END_REF] needed for our new analysis. We also define a general framework for our study. We emphasize that all our results are based on a rather natural algebraic assumption about the sub-systems considered during the hybrid approach, i.e. we assume that semi-regular system remains semi-regular after having specialized some variables (this is similar to [START_REF] Bettale | Hybrid approach for solving multivariate systems over finite fields[END_REF][START_REF] Bardet | On the complexity of solving quadratic boolean systems[END_REF]). This is formalized in Hypothesis 1 (Section 2.1). In Section 2.2, we present a first new result about the hybrid approach. Surprisingly enough, we have been able to show that fixing a number of variables k which is proportional to the initial number of variables of the system considered yields a better trade-off than the one in [START_REF] Bettale | Hybrid approach for solving multivariate systems over finite fields[END_REF]. In Section 3, we provide an explicit form of the best trade-off. We show that it is asymptotically1 equivalent to:

n 10.86 ω 2 (4.16 log 2 (q) -3.14 ω) 2 ,
where ω, 2 ω 3 is the linear algebra constant. This result allows to derive an asymptotical equivalent for the cost of the hybrid approach. Precisely, the complexity is asymptotically equivalent to 2 n ω (1.38-0.44ω log(q) -1 ) , when n → ∞, q → ∞ and log (q) n.

Finally, we quantify in Section 4 the gain of the hybrid approach with respect to a direct Gröbner basis computation. Once again, we arrive to a rather unexpected result. The hybrid approach providesunder some conditions -an exponential speed-up. More precisely, when n → ∞, q → ∞ and as long as n log(q), the gain of the hybrid approach compared to the direct Gröbner basis approach is asymptotically 2 0.62 ω n . To the knowledge of the authors, this makes the hybrid approach the method with the best asymptotical complexity for solving PoSSo q (for q > 2).

PRELIMINARIES

We review in this part some useful results obtained in [START_REF] Bettale | Hybrid approach for solving multivariate systems over finite fields[END_REF]. Throughout the paper, we always use the following notations: q is the size of the field, n is the number of variables, m is the number of equations and k is the trade-off (number of fixed variables in the hybrid approach). We will always assume that m ≥ n. We denote by ω, 2 ω 3 the linear algebra constant. We write O for the "big O" notation. We also use the o for the "little-o" notation, i.e.

f (n) = o g(n) if lim n→∞ f (n) g(n) = 0. Finally, we say that f and g are asymptotically equivalent, denoted f ∼ g, if f -g = o(g) (or equivalently, lim n→∞ f (n) g(n) = 1 if f and g are positive real valued functions).

Complexity of the Hybrid Approach

We recall in this part the general expression of the hybrid approach cost [START_REF] Bettale | Hybrid approach for solving multivariate systems over finite fields[END_REF]. To do so, let C F 5 n, m, d reg be the complexity of computing the Gröbner basis of a system of m equations in n variables using the F 5 algorithm2 [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases without reduction to zero (F5)[END_REF], where d reg is the degree of regularity of the system. Informally, the degree of regularity is the maximum degree reached during the Gröbner basis computation. Note that this degree depends on n, m and q. The complexity of the hybrid approach [START_REF] Bettale | Hybrid approach for solving multivariate systems over finite fields[END_REF] is as follows.

PROPOSITION 2.1. Let { f 1 , . . . , f m } ⊂ F q [x 1 , . . . , x n ] be an al- gebraic system of equations with respective degrees d 1 • • • d m .
Let k be a non-negative integer and d max reg (k) (resp. D max (k)) be the maximum degree of regularity (resp. maximum number of solutions in the algebraic closure of F q counted with multiplicities) of all the systems:

{ f 1 (x 1 , . . . , x n-k , v 1 , . . . , v k ), . . . , f m (x 1 , . . . , x n-k , v 1 , . . . , v k )} for any (v 1 , . . . , v k ) ∈ F k q .
The complexity of the hybrid approach is bounded from above by:

min 0 k n   q k C F 5 n -k, m, d max reg (k) Gröbner basis + O ((n -k) D max (k) ω ) change of ordering    . (1)
This is the complexity of computing q k (DRL) Gröbner bases with F 5 of polynomial systems having m equations, nk variables, respective degrees d 1 • • • d m , plus the cost of performing a change of ordering with FGLM [START_REF] Faugère | Efficient computation of zero-dimensional gröbner bases by change of ordering[END_REF].

In order to study the asymptotical behavior of the hybrid approach, we assume -as in [START_REF] Bettale | Hybrid approach for solving multivariate systems over finite fields[END_REF] -a regularity condition about the sub-systems arising during the hybrid approach.

HYPOTHESIS 1. Let { f 1 , . . . , f m } ⊂ F q [x 1 , . . . , x n ] be random algebraic equations of respective degrees d 1 • • • d m .
Let β min , 0 < β min < 1 be a value that will be specified later. Then, for any k, 0 k β min n , and for each vector (v 1 , . . . , v k ) ∈ F k q , the system:

{ f 1 (x 1 , . . . , x n-k , v 1 , . . . , v k ), . . . , f m (x 1 , . . . , x n-k , v 1 , . . . , v k )}
is semi-regular for n large enough.

Note that systems verifying such hypothesis are in particular semiregular (k = 0). We refer the reader to [START_REF] Bardet | Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems[END_REF][START_REF] Bardet | Études des systèmes algébriques surdéterminés[END_REF][START_REF] Bardet | On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations[END_REF][START_REF] Bardet | Complexity study of Gröbner basis computation[END_REF] for more information on semi-regular systems. In practice, a randomly picked system is semi-regular with high probability. Assuming Fröberg's conjecture [START_REF] Fröberg | An inequality for Hilbert series of graded algebras[END_REF], this can be proven more formally. We emphasize that Hypothesis 1 has been experimentally verified [START_REF] Bardet | On the complexity of solving quadratic boolean systems[END_REF] for a large amount of random quadratic binary systems. In [START_REF] Bettale | Hybrid approach for solving multivariate systems over finite fields[END_REF], such assumption has been verified for larger q on algebraic systems coming coming from multivariate schemes such as UOV [START_REF] Kipnis | Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization[END_REF]. However, such systems are naturally under-defined. Thus, the total number of variables to be fixed (m-n variables to have a square system plus k variables due to the hybrid approach) is sufficiently big to assume that the algebraic systems obtained after specialization behave as a random system. Note also that we performed some experiments to check this assumption for random systems of equations. We experimentally verified that Hypothesis 1 holds for random square systems with various values of n, 6 ≤ n ≤ 16, and with parameters q, β min as in Table 2.

One interesting feature of semi-regular systems is that their degree of regularity is known in advance. Indeed, let { f 1 , . . . , f m } ⊂ F q [x 1 , . . . , x n ] be a semi-regular system. Its regularity is given by the index of the first non-positive coefficient of

∑ k≥0 c k z k = ∏ m i=1 (1 -z d i ) (1 -z) n .
In addition, asymptotical equivalents are known [START_REF] Bardet | Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems[END_REF][START_REF] Bardet | Études des systèmes algébriques surdéterminés[END_REF][START_REF] Bardet | On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations[END_REF][START_REF] Bardet | Complexity study of Gröbner basis computation[END_REF] for the degree of regularity. These allow to perform the analysis in [START_REF] Bettale | Hybrid approach for solving multivariate systems over finite fields[END_REF], and will be further used in this paper. Note that assuming Hypothesis 1, all the sub-systems solved during the hybrid approach have -for a fixed k -the same degree of regularity. We denote this regularity by d reg (k) (i.e. d max reg (k) = d reg (k). Furthermore, the number of solutions of an over-determined semi-regular system of equations is always 0 or 1 (i.e. 0 ≤ D max (k) ≤ 1 as soon as k > 0). This allows to neglect the cost of the change ordering algorithm in the complexity.

Best Trade-Off for Quadratic Systems ?

Throughout this paper, we denote by k 0 the optimal value for k, that is, the parameter that minimizes the complexity of the hybrid approach. The goal of this part is to have the asymptotic trend of the best trade-off. To simplify the analysis, we focus our attention to quadratic systems. Such systems are widespread in many applications (especially cryptography), making their study of main interest.

To find the best trade-off, we want to minimize the complexity of the hybrid approach. To do so, we first consider the complexity C hyb (k) of the hybrid approach as a continuous function of k ∈ R. When this function reaches its minimum, its derivative C hyb (k) with respect to k vanishes. A root k 0 of C hyb (k) with k 0 , 0 k 0 n gives then the best tradeoff. Finally, as C hyb (k) is a complexity, it is always positive. It is thus equivalent to look for a root of its logarithmic derivative

C hyb (k) C hyb (k) . Let C 1 (n, k) = (n -k -1) ,C 2 (n, k) = 3 n-k 2 -1 - √ n k and C 3 (n, k) = n+k 2 - √ n k .
The authors of [START_REF] Bettale | Hybrid approach for solving multivariate systems over finite fields[END_REF] obtain that the best trade-off k 0 is a root of ∆(k) where

∆(k) = log (q) + ω log C 1 (n, k) + 1 2C 1 (n, k) - ω 2 1 + n/k log C 2 (n, k) + 1 2C 2 (n, k) - ω 2 1 -n/k log C 3 (n, k) + 1 2C 3 (n, k) . (2)
To push further the asymptotical analysis, we need to assume -a priori -what it is the global trend of k. At first glance, it seems (rather) natural to believe that k is going to be small and should be then a constant. This is what was assumed in [START_REF] Bettale | Hybrid approach for solving multivariate systems over finite fields[END_REF]. Surprisingly enough, we will see that the best trade-off is obtained asymptotically by fixing β 0 n variables, where β 0 is independent of n.

To do this, we first write k = β n with 0 β 1, and we show that β tends to a constant when n grows to infinity. By substituting k by β n in (2), and factoring by n in each log terms we obtain that

∆(β ) = log (q) + ω log (n) + log 1 -β - 1 n + 1 2C 1 (n, β n) - ω 2 1 + 1/β log (n) + log 3 -β 2 - 1 n -β + 1 2C 2 (n, β n) - ω 2 1 -1/β log (n) + log 1 + β 2 -β + 1 2C 3 (n, β n) . (3)
The coefficient of log (n) in this expression is:

ω - ω 2 1 + 1/β - ω 2 1 -1/β = 0.
We remark that C 1 (n, β n),C 2 (n, β n) and C 3 (n, β n) go to infinity when n tends to infinity. As a consequence:

∆ (β ) ∼ log (q) + ω (log (1 -β )) - ω 2 1 + 1/β log 3 -β 2 -β - ω 2 1 -1/β log 1 + β 2 -β .
Observe that n does not appear in the asymptotic expansion of ∆ (β ). Thus, a solution of ∆ (β ) = 0 at infinity is unrelated to n. As a consequence, the best (asymptotic) trade-off can be written k 0 = β 0 n, where β 0 is unrelated to n. This is a contradiction with our prior assumption [START_REF] Bettale | Hybrid approach for solving multivariate systems over finite fields[END_REF]: k 0 is not a constant. To have a precise analysis, we should look for the best asymptotic trade-off assuming k = β n. This is one of the reasons motivating a new analysis.

COMPLEXITY OF HYBRID APPROACH

In this part, we investigate the complexity of the hybrid approach. The goal is to have an expression of the complexity as explicit as possible. To this end, we first derive an asymptotical equivalent of this complexity depending of the degree of regularity. According to Section 2.2, we have the global trend of the best trade-off. It is of the form k = β n (with β unrelated to n). Then, we derive an asymptotically equivalent formula for the regularity of the subsystems involved in the hybrid approach. Finally, we put everything together to get an asymptotic equivalent for hybrid approach cost.

A First Asymptotic Equivalent

We recall that the complexity of F 5 as stated in [START_REF] Bardet | Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems[END_REF]:

C F 5 n, d reg = O n + d reg d reg ω . (4)
Remark that this complexity does not involve explicitly the number of equations (m). But, remember the regularity depends on m. This cost is slightly different from the one used in [START_REF] Bettale | Hybrid approach for solving multivariate systems over finite fields[END_REF]. The reason is that (4) is more accurate for semi-regular systems. Using Stirling's formula, i.e.

n! ∼ √ 2 π n n e n ,
we can derive a first expression for complexity of the hybrid approach. Since

C hyb (k) = q k C F 5 n -k, dreg(k) , it is not difficult to see that C hyb (k) ∼ q k   1 √ 2 π • n -k + dreg(k) n-k+dreg(k)+ 1 2 n -k n-k+ 1 2 dreg(k) dreg(k)+ 1 2   ω . (5)
By abuse of language, we will always refer to (5) (asymptotic equivalent) as the complexity of the hybrid approach.

Asymptotic Equivalent of the Regularity

From now on, we set m = α n (α ≥ 1 is a constant). According to Section 2.2, the best trade-off is obtained for a k of the form β • n. Thus, the hybrid approach considers sub-systems having n = n(1β ) variables and a number of equations m = α 1-β (1β ) n = θ n . For such systems, we have an asymptotic equivalent of the degree of regularity [START_REF] Bardet | Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems[END_REF], i.e.:

d reg (n , m) ∼ θ - 1 2 -θ (θ -1) n + O n 1/3 . ( 6
)
Note that in [START_REF] Bettale | Hybrid approach for solving multivariate systems over finite fields[END_REF], we have used a different asymptotic expansion of the degree of regularity. Experiments performed in [START_REF] Bettale | Hybrid approach for solving multivariate systems over finite fields[END_REF] seem to suggest that the optimal number of variables (i.e. trade-off) to be fixed is a constant. As discussed in Section 2.2, this intuition is incorrect. Thus, assuming a trade-off of the form β • n, we get that any subsystem occurring in the hybrid approach has a degree of regularity asymptotically equivalent to γ n + O n 1/3 , with:

γ = α - 1 -β 2 -α (α + β -1) . ( 7
)

Implicit Form of the Best Trade-Off

In this part, we show that the best trade-off at infinity k 0 = β 0 n can be obtained by solving an implicit equation. The idea is to derive an equivalent of the logarithmic derivative of C hyb using the regularity [START_REF] Bardet | On the complexity of solving quadratic boolean systems[END_REF]. Let D = 1β + γ. By combining ( 2) and ( 7), we get that

C hyb (β n) C hyb (β n) ∼ n log (q) + ω n log (n) + log (1 -β ) + 1 2 n (1 -β ) - ω n 2 1 + α α + β -1 log (n) + log (D) + 1 2 n D - ω n 2 1 - α α + β -1 log (n) + log (γ) + 1 2 n γ .
The terms in log(n) cancel out in this expression. Since n > 0, β 0 is then a root of

A(β ) = 1 n • C hyb (β n) C hyb (β n)
. By ignoring constant terms at infinity:

A(β ) ∼ A ∞ (β ), (8)
with

A ∞ (β ) = log (q) + ω log (1 -β ) - ω 2 1 + α α + β -1 log D 1 (α, β ) - ω 2 1 - α α + β -1 log D 2 (α, β ) ,
where

D 1 (α, β ) = α + 1-β 2 -α (α + β -1) and D 2 (α, β ) = α -1-β 2 -α (α + β -1)
. This leads to the following result.

PROPOSITION 3.1. Let F = { f 1 , . . . , f m } ⊂ F q [x 1 , . . . ,
x n ] be a system of quadratic equations verifying Hypothesis 1. Let A ∞ be as defined in [START_REF] Bardet | Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems[END_REF]. The best trade-off for solving F with the hybrid approach is asymptotically to fix k 0 = β 0 n variables, where β 0 is a root of A ∞ such that β 0 , 0 < β 0 1. The coefficient β 0 is independent on the number of variables n.

A root β 0 of A ∞ (β ) can be computed numerically (for instance using a computer algebra software like MAPLE). In Table 2 (Appendix), we present the best trade-off β 0 obtained for various values of α and q.

Square Quadratic Systems

In this part, we focus on the common case m = n (i.e., α = 1, square system). This allows to further refine Proposition 3.1. First, we simplify A ∞ (β ) as defined in (8) by setting α = 1. Second, we make the change of variable β ← 1 ν 2 . Finally, by expending

B ∞ (ν) = A ∞ 1 ν 2 , we get that: B ∞ (ν) = log (q) + ω log (2 ν + 2) + ω log ν -1 2 ν 2 - ω 2 (1 + ν) log (3 ν + 1) - ω 2 (1 + ν) log ν -1 2 ν 2 - ω 2 (1 -ν) log (ν -1) - ω 2 (1 -ν) log ν -1 2 ν 2 .
We observe that the terms in log ν-1 2 ν 2 cancels out. Finally:

A(β ) ∼ B ∞ (β ), (9)
with

B ∞ (ν) = log (q) + ω log (2 ν + 2) - 1 + ν 2 log (3 ν + 1) - 1 -ν 2 log (ν -1) .
For square systems, Proposition 3.1 can be refined as follows.

PROPOSITION 3.2. Let F = { f 1 , . . . , f n } ⊂ F q [x 1 , . . . , x n ] be a system of quadratic equations verifying Hypothesis 1. Let B ∞ be as defined in [START_REF] Bettale | Hybrid approach for solving multivariate systems over finite fields[END_REF]. The best trade-off for solving F with the hybrid approach is asymptotically to fix k 0 = n

ν 2 0 variables, where ν 0 is a root of B ∞ (ν) such that ν 0 , 0 < β 0 1. The coefficient β 0 = 1 ν 2 0 is independent of n.
We show in Table 1 the value of β 0 = 1 ν 2 0 with respect to several usual sizes of field q. We compare these values with the exact ratio β 0 when n = 100 and n = 200 (once the parameters are fixed, we can compute exact value β exact 0 minimizing the complexity of the hybrid approach). The table shows that our approximation matches well with the expected value.

Table 1: Sample values for β 0 for several field sizes with ω = 2.4. We need less variables to reach the best trade-off when the field is bigger.

q 2 2 2 3 2 4 2 5 2 6 2 8 2 16
β 0 0.52 0.35 0.24 0.17 0.12 0.071 0.017

β exact 0
, n = 100 0.59 0.35 0.25 0.14 0.12 0.08 0.02 β exact 0 , n = 200 0.55 0.39 0.24 0.17 0.17 0.09 0.02

Note that the the proportion of variables which needs to be fixed tends to 0 when the size of the field increases. This is consistent with the intuition that the exhaustive search becomes less interesting for too big fields.

Complexity of the Hybrid Approach -An Asymptotic Equivalent

We derive in this part an explicit (asymptotic) equivalent of the hybrid approach complexity. The only element which is missing to get this equivalent is an explicit form of the β 0 discussed in Section 3.3. Table 1 suggests that when q grows, β 0 = 1 ν 2 0 decreases. This means that ν 0 → ∞ when q → ∞. This remark combined with Proposition 3.2 leads to the following result. PROPOSITION 3.3. Let F = { f 1 , . . . , f n } ⊂ F q [x 1 , . . . , x n ] be a system of quadratic equations verifying Hypothesis 1. Asymptotically, the best trade-off for solving F with the hybrid approach is to fix k 0 = n β 0 variables, with:

β 0 = 3 ω log (3) 6 log (q) + 6 ω log (2) -4 ω -3 ω log (3) 2 , = 10
.86 ω 2 (4.16 log 2 (q) -3.14 ω) 2 PROOF. Let B ∞ (ν) be as defined in Proposition 3.2. We get that

B ∞ (ν) ∼ ν→∞ log(q) - 1 2 ω log(3) ν + ω log (2) - 2 3 - 1 2 log (3) .
Let ν 0 be a root of B ∞ (ν) at infinity (i.e. ν → ∞). We get:

ν 0 = 6 log (q) + 6 ω log (2) -4 ω -3 ω log (3) 3 ω log (3) . ( 10
)
Then, as

k 0 = n β 0 = n ν 2 0
, we recover the result announced.

Note that when q is too small, β 0 becomes greater than one and the approximation is not valid.

We are now in position to derive the (asymptotical) complexity of the hybrid approach. We use the value of β 0 provided in Proposition 3.3 together with [START_REF] Bardet | On the complexity of solving quadratic boolean systems[END_REF] to have an asymptotic of the regularity.

It is a multiple of n, and we denote by γ 0 the corresponding factor. Precisely:

γ 0 = 1 + β 0 2 -β 0 . (11)
Finally, we obtain the asymptotic complexity of the hybrid approach -with the best tradeoff -using the complexity [START_REF] Bardet | Complexity study of Gröbner basis computation[END_REF]. Let

D 0 = 1 -β 0 + γ 0 , we have C hyb (k 0 ) = C hyb (β 0 n) ∼ q β 0 n √ 2 π ω • (n -β 0 n + γ 0 n) n-β 0 n+γ 0 n+ 1 2 (n -β 0 n) n-β 0 n+ 1 2 (γ 0 n) γ 0 n+ 1 2 ω , ∼ q β 0 n √ 2 π ω • 1 ( √ n) ω •   D n-β 0 n+γ 0 n+ 1 2 0 (1 -β 0 ) n-β 0 n+ 1 2 γ γ 0 n+ 1 2 0   ω , ∼ q β 0 n √ 2 π n ω • D 0 (1 -β 0 ) γ 0 ω 2 • D D 0 0 (1 -β 0 ) 1-β 0 γ γ 0 0 ω n . (12)
This leads to: THEOREM 3.1. The complexity of the hybrid approach -using the trade-off k 0 = β 0 n of Proposition 3.3 -is asymptotically equivalent to 2 n ω (1.38-0.63ω log 2 (q) -1 ) , when n → ∞, q → ∞ and log (q) n.

PROOF. From [START_REF] Buchberger | Bruno buchberger's phd thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal[END_REF] and using the value k 0 in Prop. 3.3:

log 2 C hyb (k 0 ) ∼ n K -ω log 2 √ 2 π n + O (1) (13)
with K = log 2 (q)

ν 2 0 + ω 3 2 - 1 2 ν 2 0 - 1 ν 0 log 2 3 2 - 1 2 ν 2 0 - 1 ν 0 -ω 1 - 1 ν 2 0 log 2 1 - 1 ν 2 0 -ω 1 2 + 1 2 ν 2 0 - 1 ν 0 log 2 1 2 + 1 2 ν 2 0 - 1 ν 0 . When q → ∞, K tends to 3 2 ω log 2 (3) -ω - 1 4 ω 2 log 2 (3) 2 log 2 (q) = 1.38 ω -0.63 ω 2 log 2 (q) .
The first term in ( 13) is dominant, so the complexity of the hybrid approach is asymptotically 2 n K .

If ω = 2.4 for instance, the complexity of the hybrid approach is:

2 n 3.31-3.62 log 2 (q) -1 .

ASYMPTOTIC GAIN OF THE HYBRID APPROACH

The purpose of this part is to quantify the gain of the hybrid approach with respect to a direct approach. We restrict our attention here to the case m = n (i.e. α = 1).

The degree of regularity of a square quadratic system of n equations is n + 1 [START_REF] Bardet | Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems[END_REF]. Using Stirling's formula in (4):

C F 5 ∼ 1 √ 2 π • (2 n + 1) 2 n+ 3 2 n n+ 1 2 (n + 1) n+ 3 2 ω .
To simplify this expression, we use:

(2 n + 1) 2 n+ 3 2 (2 n) 2 n+ 3 2 = 1 + 1 2 n 2 n+ 3 2 ∼ e. Thus, C F 5 ∼ 1 √ 2 π • e (2 n) 2 n+ 3 2 n n+ 1 2 e n n+ 3 2 ω ∼ 1 √ 2 π • n 2 n+ 3 2 2 2 n+ 3 2 n n+ 1 2 n n+ 3 2 ω ∼ 1 √ 2 π • 2 2 n+ 3 2 n 1 2 ω .
Finally:

C F 5 ∼ 2 √ π n ω • 2 2 ω n . (14)
Let k 0 be as defined in Proposition 3.3. Using ( 12) and ( 14), we get that

C F 5 C hyb (k 0 ) ∼ 2 √ π n ω × 2 2 ω n √ 2 π n ω q β 0 n (1 -β 0 ) γ 0 1 -β 0 + γ 0 ω 2 (1 -β 0 ) 1-β 0 γ γ 0 0 (1 -β 0 + γ 0 ) 1-β 0 +γ 0 ω n .
This last expression can be written as follows:

2 √ 2 ω • (1 -β 0 ) γ 0 1 -β 0 + γ 0 ω 2 • 1 q β 0 2 2 • (1 -β 0 ) 1-β 0 γ γ 0 0 (1 -β 0 + γ 0 ) 1-β 0 +γ 0 ω n .
As a consequence:

C F 5 C hyb (k 0 ) ∼ 1 q β 0 n 2 2 • (1 -β 0 ) 1-β 0 γ γ 0 0 (1 -β 0 + γ 0 ) 1-β 0 +γ 0 ω n . ( 15
)
This corresponds to the asymptotic gain of the hybrid approach.

To simplify our notations, we denote by Q = log 2

C F 5
C hyb (k 0 ) the logarithm of the gain. It holds that Q ∼ nC, with:

C = -β 0 log 2 (q) + 2 ω log 2 (2) + ω log 2 (1 -β 0 ) 1-β 0 γ γ 0 0 (1 -β 0 + γ 0 ) 1-β 0 +γ 0 .
Note that C does not depend on n. We replace β 0 and γ 0 by their respective values obtained from Prop. 3.3 and equation [START_REF] Buchberger | Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal[END_REF]. To have an approximation of this gain, one can compute an asymptotic expansion of C when q → ∞. Using the logarithmic in base 2:

C ∼ 3 ω - 3 2 ω log 2 (3) = 0.62 ω . (16)
This allows to state the following: THEOREM 4.1. Let F = { f 1 , . . . , f n } ⊂ F q [x 1 , . . . , x n ] be quadratic equations verifying Hypothesis 1. When n → ∞, q → ∞ and as long as n log 2 (q), the gain of the hybrid approach compared to a direct Gröbner basis approach is asymptotically 2 0.62 ω n . Theorem 4.1 gives a trend of the asymptotic gain. It shows the overall efficiency of the hybrid approach compared to the simple Gröbner basis approach. For ω = 2.4, we get a speed-up of 2 1.49 n as stated in the abstract.

On the other hand, the actual gain can be more precisely computed with explicit values of C hyb , the best trade-off, and C F 5 ). We compare the real gain with several of our asymptotic estimations for fields of size q = 2, 16, 256, 2 16 , 2 32 using ω = 2.4. Each figure (Fig. 1 to 5) has four curves, except when q 13, where the approximation of Proposition 3.3 is not relevant. -The theoretical gain (plain line) obtained from the explicit complexity of C F 5 [START_REF] Bardet | Études des systèmes algébriques surdéterminés[END_REF] and the best trade-off as the minimum of Proposition 2.1 for all k, 0 k n.

-The gain when n → ∞ (dashed line) obtained from ( 16) and the trade-off is computed with Proposition 3.1.

-The gain when n → ∞ with k 0 from Proposition 3.3 (loosely dashed line) obtained from (16) (relevant for q > 13).

-The asymptotic gain when n → ∞ and q → ∞ (dotted line) of Theorem 4. As expected, the gain becomes more accurate as q grows (Fig. 1 to 3). When n is not big enough compared to q, it becomes less accurate (Fig. 5).

Asymptotically, the hybrid approach is then always better than a direct solving. Eventually, when q is too big (with respect to n), the cost of an exhaustive search, even in one single variable, will be too expensive compared to Gröbner basis computation.

Figure 1 :Figure 2 :Figure 3 :Figure 4 :Figure 5 :

 12345 Figure 1: Gain when solving a system over F 2 .

A maple code corresponding to this paper can be found at http: //www-salsa.lip6.fr/~perret/Site/hybrid_issac.mpl.

Note that a similar analysis could be also performed with any algorithm solving PoSSo q and having a precise complexity estimates based on the degree of regularity, e.g.[START_REF] Buchberger | Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal[END_REF][START_REF] Buchberger | Computer algebra symbolic and algebraic computation[END_REF][START_REF] Buchberger | Bruno buchberger's phd thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal[END_REF][START_REF] Faugère | A new efficient algorithm for computing Gröbner bases (F4)[END_REF][START_REF] Faugère | A new efficient algorithm for computing Gröbner bases without reduction to zero (F5)[END_REF][START_REF] Gao | A new incremental algorithm for computing groebner bases[END_REF].

Acknowledgments. We would like to thank the referees for their meaningful comments. The work described in this paper has been supported in part by the European Commission through the ICT program under contract ICT-2007-216676 ECRYPT II. The authors were also supported in part by the french ANR under the Computer Algebra and Cryptography (CAC) project ANR-09-JCJCJ-0064-01 and the High-Performance Algebraic Computing (HPAC) project ANR-2011-BS02-013-04.

This work has been carried out when this author was PhD student at UPMC/INRIA/LIP6).

APPENDIX


Martin Albrecht

Carlos Cid
email: carlos.cid@rhul.ac.uk

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

Ludovic Perret
email: ludovic.perret@lip6.fr

On the relation between the MXL family of algorithms and Gröbner basis algorithms

Keywords: Gröbner bases, polynomial system solving, mutants

The computation of Gröbner bases remains one of the most powerful methods for tackling the Polynomial System Solving (PoSSo) problem. The most efficient known algorithms reduce the Gröbner basis computation to Gaussian eliminations on several matrices. However, several degrees of freedom are available to generate these matrices. It is well known that the particular strategies used can drastically affect the efficiency of the computations. In this work we investigate a recently-proposed strategy, the so-called "Mutant strategy", on which a new family of algorithms is based (MXL, MXL 2 and MXL 3 ). By studying and describing the algorithms based on Gröbner basis concepts, we demonstrate that the Mutant strategy can be understood to be equivalent to the classical Normal Selection strategy currently used in Gröbner basis algorithms. Furthermore, we show that the "partial enlargement" technique can be understood as a strategy for restricting the number of S-polynomials considered in an iteration of the F 4 Gröbner basis algorithm, while the new termination criterion used in MXL 3 does not lead to termination at a lower degree than the classical Gebauer-Möller installation of Buchberger's criteria. We claim that our results map all novel concepts from the MXL family of algorithms to their well-known Gröbner basis equivalents. Using previous results that had shown the relation between the original XL algorithm and F 4 , we conclude that the MXL family of algorithms can be fundamentally reduced to redundant variants of F 4 .

Introduction

The past few years have witnessed a growing interest from the cryptographic community in computational algebra methods, in particular Gröbner basis algorithms [START_REF] Buchberger | Ein Algorithmus zum Auffinden der Basiselemente des Restklassenrings nach einem nulldimensionalen Polynomideal[END_REF][START_REF] Buchberger | Bruno Buchberger's PhD thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal[END_REF]. This was motivated by the proposal of algebraic attacks against stream ciphers [START_REF] Courtois | Algebraic Attacks on Stream Ciphers with Linear Feedback[END_REF] and block ciphers [START_REF] Courtois | Cryptanalysis of block ciphers with overdefined systems of equations[END_REF][START_REF] Faugère | Algebraic cryptanalysis of Curry and Flurry using correlated messages[END_REF][START_REF] Albrecht | Algebraic techniques in differential cryptanalysis[END_REF][START_REF] Albrecht | Algebraic Precomputations in Differential Cryptanalysis[END_REF], as well as by the proposal of several public-key schemes based on systems of multivariate polynomial equations (e.g., [START_REF] Patarin | Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two new families of asymmetric algorithms[END_REF]), and the corresponding cryptanalysis using the F 5 algorithm [START_REF] Faugère | Algebraic Cryptanalysis of Hidden Field Equation (HFE) Cryptosystems using Gröbner Bases[END_REF][START_REF] Faugère | Cryptanalysis of 2Rschemes[END_REF][START_REF] Faugère | Cryptanalysis of MinRank[END_REF][START_REF] Bouillaguet | Practical cryptanalysis of the identification scheme based on the Isomorphism of Polynomial with one secret problem[END_REF]. One particular algorithm has received considerable attention from the cryptographic community: the XL algorithm [START_REF] Courtois | Efficient algorithms for solving overdefined systems of multivariate polynomial equations[END_REF] (and its several variants, e.g., [START_REF] Courtois | About the XL algorithm over GF(2)[END_REF][START_REF] Courtois | Cryptanalysis of block ciphers with overdefined systems of equations[END_REF][START_REF] Courtois | Algebraic Attacks over GF(2**k), Application to HFE Challenge 2 and Sflash-v2[END_REF]) was originally proposed by cryptographers to tackle problems arising specifically from cryptology. Although not strictly a Gröbner basis algorithm, it used a similar idea to the one proposed by Lazard [START_REF] Lazard | Gröbner Bases, Gaussian Elimination and Resolution of Systems of Algebraic Equations[END_REF]: it constructs the Macaulay matrix up to some large degree D and reduces it to obtain the solution of the system. The algorithm was shown to work only under particular conditions [START_REF] Diem | The XL-algorithm and a conjecture from commutative algebra[END_REF], while other flaws were also shown in other high-profile variants [START_REF] Cid | An Analysis of the XSL Algorithm[END_REF][START_REF] Lim | An analysis of XSL applied to BES[END_REF]. Eventually, it was shown that the XL algorithm could be described essentially as a redundant (and less efficient) variant of the F 4 algorithm [START_REF] Ars | Comparison between XL and Gröbner basis algorithms[END_REF]. That is, one can simulate the XL algorithm using a variant of the F 4 algorithm.

Despite of these results, because of its simplicity the XL algorithm continues to attract the attention of researchers working in cryptography [START_REF] Buchmann | Mu-tantXL: Solving multivariate polynomial equations for cryptanalysis[END_REF][START_REF] Thomae | Unravel XL and its variants[END_REF]. In this paper we investigate a prominent recent addition to the XL family, namely the MutantXL algorithms [START_REF] Buchmann | Mu-tantXL: Solving multivariate polynomial equations for cryptanalysis[END_REF][START_REF] Mohamed | MXL2: Solving polynomial equations over GF(2) using an improved mutant strategy[END_REF][START_REF] Mohamed | MXL3: An efficient algorithm for computing Gröbner bases of zero-dimensional ideals[END_REF][START_REF] Buchmann | Flexible partial enlargement to accelerate gröner basis computation over F2[END_REF]. The concept of Mutants was first introduced in [START_REF] Buchmann | Mu-tantXL: Solving multivariate polynomial equations for cryptanalysis[END_REF], giving rise to a family of algorithms and techniques [START_REF] Mohamed | MXL2: Solving polynomial equations over GF(2) using an improved mutant strategy[END_REF][START_REF] Mohamed | MXL3: An efficient algorithm for computing Gröbner bases of zero-dimensional ideals[END_REF][START_REF] Buchmann | Flexible partial enlargement to accelerate gröner basis computation over F2[END_REF], which showed to be particularly efficient against the MQQ multivariate cryptosystem [START_REF] Mohamed | Algebraic attack on the MQQ public key cryptosystem[END_REF]. Unlike the XL algorithm, some of the Mutant algorithms (e.g., MXL 3 [START_REF] Mohamed | MXL3: An efficient algorithm for computing Gröbner bases of zero-dimensional ideals[END_REF]) do in fact explicitly compute the Gröbner basis of the corresponding ideal, assuming it is zero-dimensional. Because of the remarkable experimental results reported in [START_REF] Mohamed | MXL3: An efficient algorithm for computing Gröbner bases of zero-dimensional ideals[END_REF], a natural question arises: what is behind such a performance? Is it due to changes in the algorithm, implementation tricks, tuning towards particular problems, or perhaps a fundamentally novel algorithmic idea?

In the MutantXL literature [START_REF] Buchmann | Mu-tantXL: Solving multivariate polynomial equations for cryptanalysis[END_REF][START_REF] Mohamed | MXL2: Solving polynomial equations over GF(2) using an improved mutant strategy[END_REF][START_REF] Mohamed | MXL3: An efficient algorithm for computing Gröbner bases of zero-dimensional ideals[END_REF][START_REF] Buchmann | Flexible partial enlargement to accelerate gröner basis computation over F2[END_REF] the observed performance gains are attributed to algorithmic advances. Hence, in order to compare the MutantXL family of algorithms to standard techniques in computational commutative algebra, we need to describe both in common terms. This will allow us to answer the question, whether mutants are a new concept or whether they can be described based on well-known computational algebra concepts. Likewise, are the new mutant strategies general enough, so that they can potentially be incorporated to existent Gröbner basis algorithms?

There has been so far no in-depth study of the mathematical properties of mutants and related strategies, and how they are connected to other Gröbner basis algorithms. Because of this, there is a considerable gap between the symbolic computation and the cryptographic communities. Both investigate efficient algorithms for solving polynomial systems but results seem incommensurable in terms of strategy.

In this work, we undertake the task to bridge this gap. In particular, we compare the MXL family with two variants of the F 4 algorithm [START_REF] Faugère | A new efficient algorithm for computing Gröbner basis (F4)[END_REF]: first, the so-called simplified F 4 which does not use Buchberger's criteria to avoid useless reductions to zero and second, the full F 4 as specified in [START_REF] Faugère | A new efficient algorithm for computing Gröbner basis (F4)[END_REF]. Considering these algorithms, we show that the Mutant strategy can be understood as essentially equivalent to the Normal Selection strategy as used in Gröbner basis algorithms, such as F 4 . Based on previous results, which showed the relation between the XL algorithm and F 4 [START_REF] Ars | Comparison between XL and Gröbner basis algorithms[END_REF], we conclude that MXL can too be described as a redundant variant of F 4 . Furthermore, we also study the "partial enlargement" strategy proposed in [START_REF] Mohamed | MXL2: Solving polynomial equations over GF(2) using an improved mutant strategy[END_REF] and demonstrate that it corresponds to selecting a subset of S-polynomials in Gröbner basis algorithms. As a result, we conclude that MXL 2 can also be described as a variant of F 4 , although a variant that diverges from known approaches about how to select the number of S-polynomials in each iteration. Finally, we consider the new termination criterion proposed in [START_REF] Mohamed | MXL3: An efficient algorithm for computing Gröbner bases of zero-dimensional ideals[END_REF] and demonstrate that it does not lead to a lower degree of termination than using Buchberger's criteria to remove useless pairs in a Gröbner basis algorithm. As a result, we reach the conclusion that MXL 3 can be reduced to a redundant variant of the full F 4 algorithm.

Our work is in the tradition of previous papers comparing different approaches for polynomial system solving [START_REF] Mandache | Gröbner bases computation and Gaussian elimination[END_REF][START_REF] Mandache | On the relationship between Involutive basis and Gröbner basis algorithms[END_REF][START_REF] Mandache | The Gröbner basis algorithm and subresultant theory[END_REF]. We stress, however, that the equivalence of algorithms presented in this work is constructive, i.e., we show that the Mutant family of algorithms can be simulated using redundant variants of the F 4 algorithm.

The remaining of this work is organised as follows. In Section 2 we recall the wellknown XL algorithm, and re-state the result showing the relation between XL and F 4 . In Section 3 we review well-known statements from commutative algebra. For the sake of exposition, we place particular emphasis on the concept of S-polynomials and the central role they play in Gröbner bases computations. In particular, we show that in XL-style algorithms any multiplication of polynomials by monomials except for those giving rise to S-polynomials is redundant. In Section 4 we review the definition of Mutants, and present our pseudocode for the MXL 3 algorithm. In Section 5 we state and prove our main result, namely that the Mutant strategy is a redundant variant of the Normal Selection strategy. We also treat partial enlargement and the termination condition of MXL 3 in Section 5. We conclude in Section 6, where we include a brief discussion on what we view as the limitations of using running times as the sole basis for comparison between Gröbner basis algorithms.

The XL Algorithm

In this section we briefly recall the well-known XL algorithm. An iterative variant of the algorithm is given in Algorithm 1. We adopt the notation from [START_REF] Mohamed | MXL3: An efficient algorithm for computing Gröbner bases of zero-dimensional ideals[END_REF] and, given a set of polynomials S, we denote by S (op)d the subset of S with elements of degree (op)d where (op) ∈ {=, <, ≤, >, ≥}.

It was shown in [START_REF] Ars | Comparison between XL and Gröbner basis algorithms[END_REF] that the XL algorithm can be emulated using the F 4 algorithm. In particular, [START_REF] Ars | Comparison between XL and Gröbner basis algorithms[END_REF] proves that: Lemma 1. XL (described in Algorithm 1) can be simulated using F 4 (described in Algorithm 3) by adding redundant pairs. A simple corollary of this result is that the following holds when both algorithms only compute up to a fixed degree D.

Corollary 1. Let G XL,D be the set of polynomials computed by the XL algorithm up to degree D. Then ∀g ∈ G XL,D , there exists f ∈ G F4,D with LM( f ) | LM(g), where G F4,D is the set of polynomials computed by the F 4 algorithm up to degree D.

Gröbner Bases Basics

In this section we recall some basic results about Gröbner bases. For a more detailed treatment, we refer the reader to, for instance, [START_REF] Cox | Ideals, Varieties, and Algorithms, 1st Edition[END_REF]. Consider a polynomial ring Input: F -a tuple of polynomials Input: D -an integer > 0 Result: a D-Gröbner basis for F begin G ←-∅;

for 1 ≤ d ≤ D do F =d ←-∅; for f ∈ F do if deg( f ) = d then add f to F =d ; else if deg( f ) < d then M =d-deg( f ) ←-all monomials of degree d -deg( f ); for m ∈ M =d-deg( f ) do 10 add m • f to F =d ; 11 G ←-the row echelon form (of the matrix) of G ∪ F =d ; 12 return G 13 end 14 Algorithm 1: XL R = F[x 0 , . . . , x n-1
] over some finite field F. We adopt some admissible ordering on monomials in R. We can then denote by LM( f ) the largest or leading monomial appearing in f ∈ R and by LC( f ) ∈ F the coefficient corresponding to LM( f ) in f . By LT( f ) we denote LC( f ) • LM( f ). In this work LV( f ) denotes the largest variableordered w.r.t. the monomial ordering -in the leading monomial LM( f ) of f , and given a set F ⊂ R, we define LV(F, x) as { f ∈ F | LV( f ) = x}. The set of leading monomials of F is defined as LM(F) = {LM( f ) | f ∈ F}, M denotes the set of all monomials in R, while M(F) is the set of all monomials appearing in the polynomials in F.

The ideal I generated by f 0 , . . . , f m-1 ∈ R, denoted f 0 , . . . , f m-1 , is defined as

m-1 ∑ i=0 h i f i | h 0 , . . . , h m-1 ∈ R .
It is well-known that every ideal I ⊆ R is finitely generated. A Gröbner basis of an ideal I is a particular set of generators.

Definition 1 (Gröbner Basis).

Let I be an ideal of F[x 0 , . . . , x n-1 ] and fix a monomial ordering. A finite subset

G = {g 0 , . . . , g m-1 } ⊂ I
is said to be a Gröbner basis of I if for any f ∈ I there exists

g i ∈ G such that LM(g i ) | LM( f ).
We note that if a set of polynomials f 0 , . . . , f m-1 has a unique root, i.e. the system of equations f 0 = 0, . . . , f m-1 = 0 has a unique solution, then computation of the Gröbner basis of the corresponding ideal allows one to solve the system (i.e. the solution can be "read" directly on the Gröbner basis). More generally, if the ideal is zero-dimensional, the solutions of a system can be computed from a Gröbner basis in polynomial-time (in the number of solutions) [START_REF] Faugère | Efficient computation of Zero-Dimensional Gröbner bases by change of ordering[END_REF]. Since the notion of Gröbner bases is defined by the existence of relatively low leading terms, the task of computing a Gröbner basis is essentially to find new elements in the ideal with lower leading terms until no more such elements can be found. Buchberger proved in his PhD thesis [START_REF] Buchberger | Ein Algorithmus zum Auffinden der Basiselemente des Restklassenrings nach einem nulldimensionalen Polynomideal[END_REF] that Gröbner bases can be computed by considering only S-polynomials. Such polynomials are designed to cancel leading terms and thus potentially produce new elements in the ideal with lower leading terms.

Definition 2 (S-Polynomial).

Let f , g ∈ F[x 0 , . . . , x n-1 ] be non-zero polynomials.

• Let LM( f ) = ∏ n-1 i=0 x α i i and LM(g) = ∏ n-1 i=0 x β i
i , with α i , β i ∈ N, denote the lead- ing monomials of f and g respectively. Set γ i = max(α i , β i ) for every 0 ≤ i < n, and denote by x γ = ∏ n-1 i=0 x γ i i . It holds that x γ is the least common multiple of LM( f ) and LM(g), written as

x γ = LCM(LM( f ), LM(g)).
• The S-polynomial of f and g is defined as

S( f , g) = x γ LT( f ) • f - x γ LT(g) • g. Now let G = {g 0 , . . . , g s-1 } ⊂ R,
and I be the ideal generated by G. We say that a polynomial f ∈ I has a standard representation w.r.t. G if there exist constants a 0 , . . . , a s-1 ∈ F and monomials t 0 , . . . ,t s-1 ∈ M such that

f = s-1 ∑ k=0 a k t k g k ,
with LM(t k g k ) ≤ LM( f ). Buchberger's main result stated that G is a Gröbner basis for I if and only if every S-polynomial S(g i , g j ) has a standard representation w.r.t. G.

Furthermore, Buchberger showed that in the computation of Gröbner bases it is sufficient to consider S-polynomials only, since any reduction of leading terms can be attributed to S-polynomials. There are many variants of this result in textbooks on commutative algebra; we give below the statement and proof based on [START_REF] Cox | Ideals, Varieties, and Algorithms, 1st Edition[END_REF] since the presentation helps to understand the close connection between XL and Gröbner basis algorithms. The proof is included for the sake of completeness.

Lemma 2. Let f 0 , . . . , f t-1 be nonzero polynomials in R. Given a monomial x δ such that LM( f i ) | x δ for all i = 0, . . . ,t -1, let x α(0) , . . ., x α(t-1) be monomials in R such that x α(i) LM( f i ) = x δ for all i. We consider the sum f = Σ t-1 i=0 c i x α(i) f i , where c 0 , . . . , c t-1 ∈ F\{0}. If LM( f ) < x δ , then there exist constants b j ∈ F such that f = t-1 ∑ i=0 c i x α(i) f i = t-2 ∑ j=0 b j x δ -τ j S( f j , f j+1 ), (1)
where x τ j = LCM(LM( f j ), LM( f j+1 )). Furthermore x δ -τ j S( f j , f j+1 ) < x δ , for all j = 0, . . . ,t -2.

PROOF. Let

d i = LC( f i ). It follows that c i d i is the leading coefficient of c i x α(i) f i . Furthermore, let p i = x α(i) f i d i
and thus LC(p i ) = 1. Consider the "telescope sum":

f = t-1 ∑ i=0 c i x α(i) f i = t-1 ∑ i=0 c i d i x α(i) f i d i = t-1 ∑ i=0 c i d i p i = t-1 ∑ i=0 i ∑ j=0 c j d j - i-1 ∑ j=0 c j d j p i = t-1 ∑ i=0 i ∑ j=0 c j d j p i - t-2 ∑ i=-1 i ∑ j=0 c j d j p i+1 = t-1 ∑ j=0 c j d j p t-1 + t-2 ∑ i=0 i ∑ j=0 c j d j (p i -p i+1 ).
All c i x α(i) f i have x δ as leading monomial. Since their sum has smaller leading monomial, we have that Σ t-1 i=0 c i d i = 0, leading to:

f = t-2 ∑ i=0 i ∑ j=0 c j d j (p i -p i+1 ). (2)
By assumption x α(i) LM( f i ) = x δ for all i = 0, . . . ,t -1, and we have:

x δ -τ j S( f j , f j+1 ) = x δ -τ j x τ j LT( f j ) f j - x τ j LT( f j+1 ) f j+1 = x α( j) d j f j - x α( j+1) d j+1 f j+1 = p j -p j+1 .
This is now plugged into the telescope sum (2) leading to:

f = t-2 ∑ i=0 i ∑ j=0 c j d j x δ -τ i S( f i , f i+1 ) = t-2 ∑ i=0 b i x δ -τ i S( f i , f i+1 ), with b i = ∑ i j=0 c j d j .
Since the polynomials p j and p j+1 have leading monomial x δ and leading coefficient 1, the difference p jp j+1 has a smaller leading monomial. Since we have that p jp j+1 = x δ -τ j S( f j , f j+1 ), this claim also holds true for x δ -τ j S( f j , f j+1 ). Thus the Lemma holds.

The following corollary is a simple generalisation of Lemma 2 to sums where not all summands have the same leading term.

Corollary 2. Let f 0 , . . . , f t-1 be polynomials in R. Consider the polynomial f as the sum f = Σ t-1 i=0 c i x α(i) f i , with coefficients c 0 , . . . , c t-1 ∈ F\{0}, such that LM( f ) < x δ = max{x α(i) LM( f i )}. Without loss of generality, we can assume that there is a t such that x α( j) LM( f j ) = x δ for j < t and x α(k) LM( f k ) < x δ for k ≥ t. Then there exist constants b

i ∈ F such that f = t-2 ∑ i=0 b i x δ -τ i S( f i , f i+1 ) + t-1 ∑ k=t c k x α(k) f k = ∑ ci x α(i) fi , where x τ j = LCM(LM( f j ), LM( f j+1 )), ci x α(i) fi = c i+1 x α(i+1) f i+1 if i ≥ t -1 and b i x δ -τ i S( f i , f i+1 ) otherwise. Furthermore, for all 0 ≤ i ≤ t -2, we have LM(x δ -τ i S( f i , f i+1 )) < x δ
and thus x α(i) LM( fi ) < x δ for all i.

Corollary 2 states essentially that whatever cancellations can be produced by monomial multiplications and F-linear combinations, they can be attributed to S-polynomials. It follows that the only cancellations that need to be considered in an XL-style algorithm are those produced by S-polynomials.

Example 1. Consider the polynomials f

= xy + x + 1, g = x + 1 and h = z + 1 ∈ F 127 [x, y,
z], a pathological example constructed to demonstrate the role of S-polynomials. We fix the degree reverse lexicographical term ordering. To compute a Gröbner basis, we start by constructing two S-polynomials of degree two, namely: fy • g = xy + 1 and z • gx • h = -x + z. We note that the latter trivially reduces to zero and would be detected and avoided by Buchberger's first criterion [START_REF] Cox | Ideals, Varieties, and Algorithms, 1st Edition[END_REF]. Ignoring this optimisation, in matrix notation, we would have to consider the six rows corresponding to f , y • g, z • g, x • h, g and h. For comparison, XL would consider the following polynomials up to degree two.

f = xy + x + 1, x • g = x 2 + x, y • g = xy + y, z • g = xz + z, x • h = xz + x, y • h = yz + y, z • h = z 2 + z, g = x + 1, h = z + 1.
In matrix notation we have

A =            
0 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 1

            and E =            
1 0 0 0 0 0 0 0 -1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 -1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 -1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0

            .
Of course, the system f = 0, g = 0, h = 0 is straightforwardly solved by evaluating f at x = -1 as implied by g. We note, however, that this computation is equivalent to reducing the S-polynomial S( f , g) by g, i.e., the first step in Buchberger's algorithm.

Note that Lemma 2 does not state that LM( f ) = max{LM(S( f j , f j+1 ))}, but rather that the leading terms of summands decrease once rewritten using S-polynomials. In the following example, we consider the case when LM( f ) < max{LM(S( f j , f j+1 ))}.

In this case, we can reapply Lemma 2 to f ′ i = S( f i , f j ) as the following example emphasizes.

Example 2. Consider the polynomials f = xy + a, g = yz + b, and h = ab + 1 in the polynomial ring F 127 [x, y, z, a, b]. We consider the degree reverse lexicographical term ordering. There are three possible S-polynomials S( f , g), S( f , h) and S(g, h). Two of them -S( f , h) and S(g, h) -trivially reduce to zero and would be detected and avoided by Buchberger's first criterion. However, one S-polynomial does not reduce to zero:

s 0 = z • f -x • g = za -xb. From s 0 we can then construct s 1 = b • s 0 -z • h = -xb 2 -z,
among others, also at degree 3, which is an element of the reduced Gröbner basis. The XL algorithm at degree 3 will produce

{m • p | m ∈ {1, x, y, z, a, b}, p ∈ { f , g, h}},
which reduces to

x 2 y + xa, xy 2 + ya, xyz + xb, y 2 z + yb, yz 2 + zb, xya + a 2 , yza -1, xyb -1, yzb + b 2 , xab + x, yab + y, zab + z, a 2 b
• (z • f -x • g) -z • h = (bz) • f -(bx) • g -z • h, but we have that deg(bz • f ) = 4.
We note that this behaviour of XL was the motivation for the Mutant concept.

Mutants and MXL algorithms

Let F = { f 0 , . . . , f m-1 } ⊂ F[x 0 , . . . , x n-1 ], and I = f 0 , . . . , f m-1 be the ideal generated by F. Recall that any element f ∈ I can be written as

f = m-1 ∑ i=0 h i • f i , with h i ∈ F[x 0 , . . . , x n-1 ].
Note that this representation is usually not unique. Following the terminology of [START_REF] Buchmann | Mu-tantXL: Solving multivariate polynomial equations for cryptanalysis[END_REF], we call the level of the representation

∑ f i ∈F h i • f i of f the maximum degree of {h i • f i | f i ∈ F}.
We call the level of f the minimal level of all its representations. We can then define the concept of a mutant [START_REF] Buchmann | Mu-tantXL: Solving multivariate polynomial equations for cryptanalysis[END_REF][START_REF] Mohamed | MXL2: Solving polynomial equations over GF(2) using an improved mutant strategy[END_REF][START_REF] Mohamed | MXL3: An efficient algorithm for computing Gröbner bases of zero-dimensional ideals[END_REF]. Definition 3. Given a set of generators F of an ideal I , a polynomial f ∈ I is a mutant if its total degree is strictly less than its level.

A mutant corresponds to a "low-degree" relation occurring during XL or more generally during any Gröbner basis computation. It follows from the discussion in Section 3 that, in the language of commutative algebra, a mutant occurs when an S-polynomial has a lower-degree leading monomial after reduction by F and if this new leading monomial was not in the set LM(F) before reduction.

The concept of mutant has recently motivated the proposal of a family XL-style algorithms [START_REF] Buchmann | Mu-tantXL: Solving multivariate polynomial equations for cryptanalysis[END_REF][START_REF] Mohamed | MXL2: Solving polynomial equations over GF(2) using an improved mutant strategy[END_REF][START_REF] Mohamed | MXL3: An efficient algorithm for computing Gröbner bases of zero-dimensional ideals[END_REF][START_REF] Buchmann | Flexible partial enlargement to accelerate gröner basis computation over F2[END_REF]. We discuss below the most prominent, namely the MXL 3 algorithm.

MXL 3 Algorithm

The MXL family of algorithms improves the XL algorithm using the mutant concept. In particular, the MXL 3 (Algorithmm 2) differs from XL in the following respects:

1. Instead of "blindly" increasing the degree in each iteration of the algorithm, the MXL algorithms treat mutants at the lowest possible degree, (cf. line 9 in Algorithm 2). This is the key contribution of the MXL algorithm [START_REF] Buchmann | Mu-tantXL: Solving multivariate polynomial equations for cryptanalysis[END_REF]. 2. Instead of considering all elements F =d of the current degree d, MXL 3 only considers a subset of elements per iteration. It incrementally adds more elements of the current degree, if the elements of the previous iteration did not suffice to solve the system (cf. lines 24-26 in Algorithm 2). This is called partial enlargement in [START_REF] Mohamed | MXL2: Solving polynomial equations over GF(2) using an improved mutant strategy[END_REF][START_REF] Mohamed | MXL3: An efficient algorithm for computing Gröbner bases of zero-dimensional ideals[END_REF]. This is the key contribution of the MXL 2 algorithm [START_REF] Mohamed | MXL2: Solving polynomial equations over GF(2) using an improved mutant strategy[END_REF]. 3. XL terminates at the user-provided degree D, while MXL 3 does not require to fix the degree a priori. Instead, the algorithm will terminate once a Gröbner basis was found using a new criterion (cf. line 18 in Algorithm 2). This is the key contribution of the MXL 3 algorithm [START_REF] Mohamed | MXL3: An efficient algorithm for computing Gröbner bases of zero-dimensional ideals[END_REF].

The pseudocode presented in Algorithm 2 is a slightly simplified variant of the MXL 3 algorithm; we use this presentation in Section 5 to compare it with the F 4 algorithm (Algorithm 3). Our pseudocode has some minor differences with the pseudocode presented in [START_REF] Mohamed | MXL3: An efficient algorithm for computing Gröbner bases of zero-dimensional ideals[END_REF]; we list these below: Partial enlargement. We disregard any partial enlargement strategy in the case when mutants were found. This matches the pseudocode in [START_REF] Mohamed | MXL3: An efficient algorithm for computing Gröbner bases of zero-dimensional ideals[END_REF]. However, the actual implementation of MXL 3 does indeed use the partial enlargement when Mu = ∅ (i.e. mutants exist) [START_REF] Mohamed | [END_REF]. We note that our pseudocode and that in [START_REF] Buchmann | Mu-tantXL: Solving multivariate polynomial equations for cryptanalysis[END_REF] are equivalent to MXL [START_REF] Buchmann | Mu-tantXL: Solving multivariate polynomial equations for cryptanalysis[END_REF] in this case. Since our work is mainly concerned with the concept of mutants, maintaining this simplification seems appropriate.

Choice of y.

In line 11 we set y to max{LV( f

) | f ∈ F ≤k+1 } instead of max{LV( f ) | f ∈ Mu =k }
since this allows reductions among all elements of degree k + 1 instead of only those in Mu =k+1 . Restricting reduction to the elements of Mu =k+1 could lead to incomplete reductions and thus results. The actual implementation of MXL 3 uses "partial enlargement" in this step and thus increases y iteratively [START_REF] Mohamed | [END_REF].

Incomplete reductions.

In line 25 we removed the optimisation that only variables ≤ x are used for multiplication in the extension step. This optimisation can lead to an incorrect result as some reductions are never performed. As an example, consider f = ab + 1, g = bc + a + b and h = c. The reduced Gröbner basis of the ideal f , g, h over F 2 [a, b, c] with respect to a degree lexicographical term ordering is {a + 1, b + 1, c}. However, the pseudocode of MXL 3 as described in [START_REF] Mohamed | MXL3: An efficient algorithm for computing Gröbner bases of zero-dimensional ideals[END_REF] will not perform the necessary reductions. The leading variable of h is c, thus h ∈ LV(F, c) and h is never extended using any variable except c, since a > c and b > c.

Furthermore, the S-polynomial S( f , g) = c • fa • g = (abc + c) -(abc + ab + a) = ab+a+c is not constructed since ag requires multiplication of g in LV(F, b) by a but a > b. Thus, on termination the output of MXL 3 is not a Gröbner basis.

Our change matches Proposition 3 from [START_REF] Mohamed | MXL3: An efficient algorithm for computing Gröbner bases of zero-dimensional ideals[END_REF], which requires that for H ←-{t • g | g ∈ G,t a term and deg(t • g) ≤ D + 1} the reduced row echelon form of H is G. However, this property is not enforced by MXL 3 as presented in pseudocode in [START_REF] Mohamed | MXL3: An efficient algorithm for computing Gröbner bases of zero-dimensional ideals[END_REF], since some t • g are prohibited from being constructed if deg(t) = 1 and t > LV(g). We confirmed with the authors of [START_REF] Mohamed | MXL3: An efficient algorithm for computing Gröbner bases of zero-dimensional ideals[END_REF] that their implementation catches up on those missing multiplications when newExtend = True [START_REF] Mohamed | [END_REF].

We also present a simplified version of the F 4 algorithm in Algorithm 3. For this, we need however to introduce the required notation.

Definition 4. Let F ⊂ F[x 0 , . . . , x n-1 ], and ( f , g) ∈ F × F with f = g. We denote: PAIR( f , g) = LCM(LM( f ), LM(g)), m f , f , m g , g , where LCM(LM( f ), LM(g)) = LM(m g • g) = LM(m f • f ). Now, let P = {PAIR( f , g) | ∀( f , g) ∈ P × P with g > f }, P = PAIR( f , g) ∈ P.
We define LEFT and RIGHT as:

LEFT(P) = (m f , f ) RIGHT(P) = (m g , g),
LEFT(P) = P∈P LEFT(P) RIGHT(P) = P∈P RIGHT(P).

Relationship between the MXL Algorithms and F 4

In this section we discuss the relation between MXL 3 and F 4 . It was shown in [START_REF] Ars | Comparison between XL and Gröbner basis algorithms[END_REF] that XL can be understood as a redundant variant of F 4 (cf. Lemma 1). Thus, we know that the "framework" of MXL 3 is compatible with F 4 . In particular, we know that in each iteration of the main loop XL will not compute any non-redundant polynomials not computed by F 4 . Thus in order to study the connection between the two algorithms, we only have to consider the modifications made in MXL 3 compared to XL. That is, we consider each of these modifications independently and argue that these still perform the same useful computations as the F 4 algorithm.

Mutants

The most visible change to XL in MXL 3 is the special treatment given to mutants, i.e. when Mu = ∅. That is, instead of increasing the degree d in each iteration, if there is a fall of degree, then these new elements are treated at the current or perhaps a smaller degree before the algorithm proceeds to increase the degree as normally. Thus, compared to XL, the MXL family of algorithms may terminate at a lower degree.

On the other hand, the F 4 algorithm does not specify how to choose polynomials in each iteration of the main loop. Instead, the user passes a function SEL which specifies how to select pairs of polynomials. However, in [START_REF] Faugère | A new efficient algorithm for computing Gröbner basis (F4)[END_REF] it is suggested to choose the normal selection strategy [4, p. 225] for most inputs. We recall here how the normal strategy has been adopted in F 4 .

Definition 5 (Normal Strategy).

Let F = { f 0 , . . . , f m-1 }. We shall say that a pair ( f i , f j ) ∈ F × F with f i = f j is a critical pair. Let then P ⊂ F × F be the set of critical pairs. We denote by LCM(p i j ) the least common multiple of the leading monomials of the critical pair p i j = ( f i , f j ) ∈ P. We also call deg(LCM(p i j )) the degree of the critical pair p i j . Further, let

d = min{deg(LCM(p)) | p ∈ P}
be the minimal degree of those least common multiples of p in P. Then the normal selection strategy selects the subset

P ′ = {p ∈ P | deg(LCM(p)) = d}.
We can now state our main result.

Theorem 1. Let both MXL 3 and F 4 compute a Gröbner basis with respect to the same degree compatible ordering on the same input. Assume that until iteration i (inclusive)

of the main loop both F 4 and MXL 3 computed the same list of polynomials except for redundant polynomials, i.e., the leading monomials appearing in F 4 divide the leading monomials appearing in MXL 3 . Furthermore, assume that Mu = ∅ in Algorithm 2 at line 9 and define k to be the minimal degree of a polynomial in Mu. The set of polynomials F ≤k+1 considered by MXL 3 in the next iteration of the main loop is a superset of the polynomials considered by F 4 when using the Normal Selection Strategy in the next iteration i + 1. Furthermore, every polynomial in F ≤k+1 not in the set considered by F 4 is redundant in this iteration.

PROOF. We note that it follows from Corollary 1 that the first assumption of the theorem will be satisfied while Mu = ∅. Now assume we have Mu = ∅. First consider the F 4 algorithm, and let SEL be the Normal Selection Strategy. Then, the set P i+1 will contain the S-polynomials of lowest degree in P. Every S-polynomial in P i+1 will have at least degree k + 1, since the set Mu =k is in row echelon form and k is the minimal degree in Mu. If there exists an S-polynomial of degree k + 1 then it is of the form t i f it j f j with deg(t i f i ) = k + 1 and deg(t j f j ) = k + 1, where at least one of t i ,t j has degree 1. MXL 3 , on the other hand, constructs all multiples t i j f i with deg(t

i j ) = 1 if deg( f i ) = k. Furthermore,
it considers all elements of degree k + 1 in the next iteration which covers the case that one of t i ,t j is 1. Hence, both components of the S-polynomial are included in F ≤k+1 .

In the Symbolic Preprocessing phase F 4 also constructs all components of potential S-polynomials that could arise during the elimination. These are always of the form f it j f j where deg( f i ) = deg(t j f j ). Since MXL 3 considers all monomial multiplies of all f j up to degree k + 1 in the next iteration, these components are also included in the set F k+1 .

Recall from Corollary 2 that all f = Σ t-1 i=0 c i x α(i) f i can be rewritten as

f = t-2 ∑ j=0 b j x δ -τ j S( f j , f j+1 ) if f < max{x α(i) f i }. Note that deg(x δ ) ≤ k + 1 for F ≤k+1 and that deg(x τ j ) = k + 1 for all S-polynomials contained in F ≤k+1 . It follows that deg(x δ -τ j ) = 0 if b j = 0.
That is, any f with a smaller leading term than its representation Σ t-1 i=0 c i x α(i) f i can be computed by an F-linear combination of S-polynomials: f = ∑ t-2 j=0 b j S( f j , f j+1 ). It follows immediately from Corollary 2 that any multiple of f i which does not correspond to an S-polynomial is redundant in this iteration since it cannot lead to a drop of a leading monomial.

For the MXL algorithm, which only differs from XL when Mu = ∅, the following corollary is a direct consequence of Theorem 1 and Corollary 1.

Corollary 3. MXL can be simulated using F 4 (described in Algorithm 3) by adding redundant pairs and using the Normal Selection Strategy.

We note however that the MXL 3 algorithm may improve upon MXL when Mu = ∅ by using a "partial enlargement" strategy, which we discuss below.

Partial Enlargement

The "partial enlargement" technique was introduced in MXL 2 and is also applied in MXL 3 . Instead of multiplying every polynomial f i ∈ F by all variables x 0 , . . . , x n-1 only a subset LV(F, x) is considered. This subset is increased in each iteration by increasing x. In the language of linear algebra, the algorithm first computes the row echelon form of a submatrix in the lower right corner. If that does not suffice to produce elements of smaller degree, a larger submatrix is considered.

This corresponds to selecting a subset of S-polynomials with small least common multiple in SEL instead of selecting all polynomials of minimal degree. We note that both the POLYBORI package [START_REF] Brickenstein | PolyBoRi: A framework for Gröbner-basis computations with Boolean polynomials[END_REF] and MAGMA computer algebra system [START_REF] Bosma | The MAGMA Algebra System I: The User Language[END_REF] accept an option to restrict the number of S-polynomials considered in each iteration. However, the strategy for how the number of S-polynomials is chosen in MAGMA and POLY-BORI is different from MXL 3 . In the former ones, a constant number of S-polynomials is chosen as specified by the user; in the latter (MXL 3 ) a changeable number of Spolynomials is chosen based on the partition by leading variable. The strategy employed in MXL 3 will consider S-polynomials S( f , g) where both f and g have leading variable at most x (inclusive). That is, if there is an S-polynomial S( f , g) = t f • f -t g • g with LV( f ) < LV(g), MXL 3 will construct t f • f when considering LV(F, LV( f )) and t g • g when considering LV(F, LV(g)). Since F ≤d contains all elements of degree at most d, both components are included in the matrix when LV(F, LV(g)) are considered.

It is currently not clear which strategy for selecting subsets of S-polynomials is beneficial under which conditions. It should be noted however that if the size of the matrix is the main concern then selecting exactly the smallest S-polynomial in each iteration would be optimal; just as Buchberger's algorithm does. On the other hand, the contribution of algorithms such as F 4 is to improve performance by considering more than one S-polynomial in each iteration. Thus, it is not certain that using matrix sizes as a main measure of comparison gives an adequate picture of the performance of these algorithms.

Termination Criterion

The key contribution of the MXL 3 algorithm is the introduction of a new criterion to detect when a Gröbner basis is found. Since the MXL family does not use the concept of critical pairs, standard termination criteria such as an empty list of pairs are not immediately applicable. In Lemma 3 we give an equivalent variant of this criterion, rephrased to be more suitable for our discussion.

Lemma 3 (Proposition 3 in [33]

). Let G = {g 0 , . . . , g s-1 } be a finite subset of F[x 0 , . . . , x n-1 ] with D being the highest degree of its elements. Suppose that the following hold:

1. all monomials of degree D in F[x 0 , . . . , x n-1 ] are divisible by a leading monomial of some g i ∈ G; and

2. if H = G ∪ {t • g i | g i ∈ G,t a monomial and deg(t • g i ) ≤ D + 1}, there exists H - a row echelon form of H -such that LM( H≤D ) ⊂ LM(G) .
Then G is a Gröbner basis.

Note that condition 1 implies that the ideal generated by G is 0-dimensional. The MXL 3 algorithm uses a termination criterion based on Lemma 3 and thus will consider matrices up to degree D + 1 (where D is defined as in Lemma 3). The F 4 algorithm, on the other hand, will terminate once the list of critical pairs is empty. It is obvious that no new pairs will be created after the Gröbner basis is found, since all reductions will lead to zero in this situation. However, if we consider F 4 as given in Algorithm 3, one can see that the algorithm may consider pairs of degree > D + 1 after a Gröbner basis is discovered, if those pairs were constructed before the Gröbner basis is found. Put differently, the simplified F 4 variant considered in this work does not prune the list of critical pairs based on the current basis G. However, the full F 4 algorithm as specified in [20, p. 69] does indeed prune the list P by calling a subroutine called UPDATE. In [START_REF] Faugère | A new efficient algorithm for computing Gröbner basis (F4)[END_REF] a reference to [4, p. 230] is made -which applies Buchberger's first and second criteria using the Gebauer-Möller installation -as an example of such a routine.

The question thus becomes whether Buchberger's first and/or second criterion will remove all pairs of degree > D + 1 if the conditions (1) and (2) of Lemma 3 hold. An algorithmic variant of Buchberger's second criterion is given in the Lemma below.

Lemma 4 (Buchberger's second criterion). Let p, g 1 , g 2 ∈ F[x 0 , . . . , x n-1 ] be such that LM(p) | LCM(LM(g 1 ), LM(g 2 )). and S(g 1 , p), S(g 2 , p) have already been considered. Then S(g 1 , g 2 ) does not need to be considered and can be discarded.

We can now prove that the full F 4 algorithm will not consider pairs of higher degree than the MXL 3 when applying Buchberger's second criterion. Proposition 1. We assume a degree compatible ordering on F[x 0 , . . . , x n-1 ]. If during a Gröbner basis computation using the full F 4 algorithm conditions (1) and ( 2) of Lemma 3 hold, then Buchberger's second criterion will remove any pair of degree > D + 1 from the list of critical pairs. As a result F 4 will consider critical pairs of degree at most D + 1.

Our proof follows very closely the original proof of Lemma 3 in [START_REF] Mohamed | MXL3: An efficient algorithm for computing Gröbner bases of zero-dimensional ideals[END_REF].

PROOF. Let G = {g 0 , . . . , g s-1 } be a finite subset of F[x 0 , . . . , x n-1 ] with D being the highest degree of its elements such that:

1. all monomials of degree D in F[x 0 , . . . , x n-1 ] are divisible by a leading monomial of some

g i ∈ G; and 2. if H = G ∪ {t • g i | g i ∈ G,t a monomial and deg(t • g i ) ≤ D + 1}, there exists H -a row echelon form of H -such that LM( H≤D ) ⊂ LM(G) .
We denote the S-polynomial S(g i , g j ) by f , and let d = deg( f ). We only have to consider pairs of degree d > D + 1.

To do so, let m = LCM(LM(g i ), LM(g j )). There exist monomials m i , m j such that m

= m i • LM(g i ) = m j • LM(g j ). It is clear that GCD(m i , m j ) = 1.
By assumption deg(g i ) and deg(g j ) are at most equal to D. This implies that deg(m j ) ≥ 2 (resp. deg(m j ) ≥ 2) since d > D + 1. It is then possible to write m i = m i,1 • m i,2 such that deg(g i ) + deg(m i,2 ) = D + 1 and deg(m i,1 ) ≥ 1. A similar decomposition can be found for m j = m j,1 • m j,2 . Thus, we have that all monomials m i,1 , m i,2 , m j,1 • m j,2 are of degree ≥ 1. Now, let m * = m m i,1 and deg(LCM(LM(g), LM(g j )) < deg(m). Thus, S(g, g i ) and S(g, g j ) are being considered at a lower degree than D + 1.

Finally, m * divides m = LCM(LM(g i ), LM(g j )) by construction. It then follows from Buchberger's second criterion that f = S(g i , g j ) does not need to be considered and is discarded.

Conclusion

In this work we have studied the MXL family of algorithms, and their connections to Gröbner bases theory. We demonstrated that the mutant strategy as used in the MXL algorithms is in fact a redundant variant of the Normal Selection Strategy. Furthermore, we showed that the partial enlargement strategy proposed in [START_REF] Mohamed | MXL2: Solving polynomial equations over GF(2) using an improved mutant strategy[END_REF] corresponds to selecting a subset of S-polynomials of minimal degree in each iteration of algorithms such as F 4 . As a result, we conclude that both the MXL and MXL 2 algorithms can be seen as redundant variants of the F 4 algorithm, although the latter may select critical pairs differently from usual F 4 implementations. Finally, we studied the novel termination criterion proposed in [START_REF] Mohamed | MXL3: An efficient algorithm for computing Gröbner bases of zero-dimensional ideals[END_REF] and concluded that it does not allow the algorithm to terminate at a lower degree than F 4 . Consequently, we conclude that MXL 3 too can be understood as a redundant variant of the F 4 algorithm. However, here too we emphasise that it might selects S-polynomials differently from standard F 4 implementations due to the partial enlargement strategy.

We conclude with a brief discussion on what we view as the limitations of using running times as the basis for comparison between Gröbner basis algorithms. Linear algebra-based Gröbner bases algorithms allow several degrees of freedom to the designer and implementer of the algorithm to generate the matrices, and selection of strategies can drastically affect the efficiency of the computations. Furthermore, the specific implementation details and sub-algorithms used in the implementation (e.g., the package used for performing the Gaussian reductions, the internal representation of sparse matrices, etc.) will also have great effect on running times and memory requirements (cf., Appendix A for an example).

In fact, we claim that three almost-independent aspects will affect running times of such algorithms: the mathematical details of the algorithm itself, the strategies and heuristics used in the implementation, and the low-level implementation details. The first aspect was the main focus of interest in this paper, but it should be clear that our results do not preclude that particular implementations of MutantXL algorithms can outperform particular implementations of F 4 /F 5 in some situations. On the other hand, we are aware that it is difficult to compare the complexity of Gröbner basis algorithms and strategies and that designers often have little choice but to resort to experimental data to demonstrate the viability of their approach.

Input: F -a list of polynomials f 0 , . . . , f m-1 ∈ F[x 0 , . . . , x n-1 ] spanning a zero-dimensional ideal.

Algorithm 2 :Algorithm 3 :

 23 Result: A Gröbner basis for f 0 , . . . , f m-1 . begin D ←-max{deg( f ) | f ∈ F}; d ←-min{deg( f ) | f ∈ F}; Mu ←-∅; newExtend ←-True; x ←x 0 ; CL ←d; while True do F≤d ←the row echelon form (or matrix form) of F ≤d ;Mu ←-Mu ∪ { f ∈ F≤d | deg( f ) < d and LM( f ) ∈ LM(F ≤d )}; F ≤d ←-F≤d ; // did we find mutants? if Mu = ∅ then k ←-min{deg( f ) | f ∈ Mu}; y ←-max{LV( f ) | f ∈ F ≤k+1 }; Mu + =k ←-Multiply all elements of Mu =k by all variables ≤ y; Mu ←-Mu \ Mu =k ; F ←-F ∪ Mu + =k ; d ←k + 1;else // does the basis contain all monomials of some degree d t ? if d < CL and M =d t ⊆ LM(F) for some 1 ≤ d t ≤ d then // We found a Gröbner basis return F; // did we do all enlargements at this degree already?if newExtend = True then D ←-D + 1; x ←-min{LV( f ) | f ∈ F =D-1 }; newExtend ←-False; else // do partial enlargement and eliminate x ←-min{LV( f ) | f ∈ F =D-1 and LV( f ) > x}; F + ←-Multiply all elements of LV(F, x) by all variables ≤ x without redundancies; F ←-F ∪ F + ; if x = x 0 then newExtend ←-True; CL ←-D; d ←-D; end MXL 3 (simplified)Input: F -a tuple of polynomials f 0 , . . . , f m-1 Input: SEL -a selection strategy Result: a Gröbner basis for F beginG, i ←-F, 0; F+ i ←-F; P ←-{PAIR( f , g) | ∀ f , g ∈ G with g > f }; while P = ∅ do i ←i + 1; P i ←-SEL(P); P ←-P \ P i ; L i ←-Left(P i ) Right(P i ); // Symbolic Preprocessing F i ←-{t • f | ∀(t, f ) ∈ L i };Done ←-LM(F i ); while M(F) = Done do m ←an element in M(F) \ Done; add m to Done; if ∃ g ∈ G such that LM(g) | m then u = m/LM(g); add u • g to F i ; // Gaussian Elimination Fi ←the row echelon form of F i ; F+ i ←-{ f ∈ Fi | LM( f ) ∈ LM(F)}; for h ∈ F+ i do P ←-P {PAIR( f , h) : ∀ f ∈ G}; add h to G; return G; end F 4 (simplified)

  Thus, XL did produce xb 2 + z in one step at degree 4 but it could not produce xb 2 + z at degree 3 since this element corresponds to b

+ a, ab 2 + b, xy + a, yz + b, zaxb, and ab + 1 by Gaussian elimination. Note that xb 2 + z is not in that list. However, if we increase the degree of XL to 4, the list returned is which does contain xb 2 + z.

  •m j,[START_REF] Albrecht | Algebraic techniques in differential cryptanalysis[END_REF] . By construction, we have LCM(m * , LM(g i )) = m/m i,1 (resp. LCM(m * , LM(g j )) = m/m j,1 ), which divides m properly. We also have deg(m * ) ≤ D. Since m 1 and m 2 must be distinct, we have that m * cannot be equal to either LM(g i ) or LM(g j ). By condition 1, there exists g ∈ G \ {g 1 , g 2 } such that with LM(g) = m * . In addition deg(LCM(LM(g), LM(g i )) < deg(m)

x 3 y + x 2 a, x 2 y 2a 2 , xy[START_REF] Ars | Comparison between XL and Gröbner basis algorithms[END_REF] + y 2 a, x 2 yz + x 2 b, xy 2 z + 1,y 3 z + y 2 b, xyz 2 + xzb, y 2 z 2b 2 , yz 3 + z 2 b, x 2 ya + xa 2 , xy 2 a + ya 2 , xyzax, y 2 zay, yz 2 az, xya 2 + a 3 , yza 2a, x 2 ybx, xy 2 by, xyzbz, y 2 zb + yb 2 , yz 2 b + zb 2 , x 2 ab + x 2 , xyaba, y 2 ab + y 2 , xzab + xz. yzabb, z 2 ab + z 2 , xa 2 b + xa, ya 2 b + ya, za 2 b + xb, a 3 b + a 2 , xyb 2b, yzb 2 + b 3 , xab 2 + xb, yab 2 + yb, zab 2 + zb, a 2 b 2 -1, ab 3 + b 2 , x 2 y + xa, xy 2 + ya, xyz + xb, y 2 z + yb, yz 2 + zb, xya + a 2 , xzax 2 b, yza -1, z 2 axzb, za 2 + x, xyb -1, yzb + b 2 , xab + x, yab + y, zab + z, a 2 b+ a, xb 2 + z, ab 2 + b, xy + a, yz + b, zaxb and ab + 1,

Acknowledgements

The work described in this paper has been supported by the Royal Society grant JP090728. We would like to thank Stanislav Bulygin, Jintai Ding and Mohamed Saied Emam Mohamed for helpful comments and discusssions on earlier drafts of this work.

Appendix A. Effect of Linear Algebra Implementations on Gröbner Basis Computations

To show the effect of the linear algebra implementation, we compare two implementations of the F 4 algorithm. The only difference is the linear algebra package used to perform the Gaussian elimination step. We compare the original FGb implementation with the new linear algebra package described in [START_REF] Faugère | Parallel Gaussian Elimination for Gröbner bases computations in finite fields[END_REF]. However, to make the comparison fair we only use a sequential version of the package described in [START_REF] Faugère | Parallel Gaussian Elimination for Gröbner bases computations in finite fields[END_REF]. To compare, we consider the reduction of the 7th matrix occurring in the computation of a Gröbner basis of the standard benchmark Katsura 12 over F 65521 , as well as the full Gröbner basis computation. Typically, it takes 326.1 sec and 250 Mbytes to reduce the 7th matrix with FGb and 83.7 seconds and 682 Mbytes using FGb with the library from [START_REF] Faugère | Parallel Gaussian Elimination for Gröbner bases computations in finite fields[END_REF].