Dongdai Lin

Jean-Charles Faugère

Ludovic Perret

Tianze Wang

On Enumeration of Polynomial Equivalence Classes and Their Application to MPKC

Keywords: multivariate public key cryptography, polynomial isomorphism, finite geometry, equivalence classes, superfluous keys

The Isomorphism of Polynomials (IP) is one of the most fundamental problems in multivariate public key cryptography (MPKC). In this paper, we introduce a new framework to study the counting problem associated to IP. Namely, we present tools of finite geometry allowing to investigate the counting problem associated to IP. Precisely, we focus on enumerating or estimating the number of isomorphism equivalence classes of homogeneous quadratic polynomial systems. These problems are equivalent to finding the scale of the key space of a multivariate cryptosystem and the total number of different multivariate cryptographic schemes respectively, which might impact the security and the potential capability of MPKC. We also consider their applications in the analysis of a specific multivariate public key cryptosystem. Our results not only answer how many cryptographic schemes can be derived from monomials and how big the key space is for a fixed scheme, but also show that quite many HFE cryptosystems are equivalent to a Matsumoto-Imai scheme.

Introduction

Multivariate cryptography comprises all the cryptographic schemes using multivariate polynomials. The use of polynomial systems in cryptography dates back to the mid eighties with the design of C * [START_REF] Matsumoto | Public quadratic polynomial-tuples for efficient signatureverification and message-encryption[END_REF], later followed by many other proposals [START_REF] Patarin | The Oil and Vinegar signature scheme[END_REF][START_REF] Patarin | C * -+ and hm: Variations around two schemes of t.matsumoto and h.imai[END_REF][START_REF] Patarin | Quartz, 128-bit long digital signatures[END_REF][START_REF] Wolf | Taxonomy of Public Key Schemes based on the problem of Multivariate Quadratic equations[END_REF]. Schemes based on the hard problem of solving systems of multivariate equations over a finite field could be secure against the quantum computer threat, whereas it is well known that number theoretic-based schemes like RSA, DH, and ECDH are [START_REF] Shor | Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[END_REF]. The general method of building multivariate public key schemes is to choose a system of quadratic polynomials, called central function F , and then hide this central function by using two invertible affine transformations T and L. The composition T • F • L will be used as a public key and the pair (T, L) is considered as a secret key. We shall say that T • F • L is a scheme derived from the central function F . We can see that the cryptographic scheme is uniquely determined by its central function and two secret affine transformations. But the converse is not true. Let us look at the following two examples.

Example 1. Let F :    u 1 = v 2 1 + α 2 v 1 v 2 + αv 1 v 3 + α 2 v 2 v 3 + αv 2 3 u 2 = α 2 v 1 v 2 + α 2 v 2 2 + α 2 v 2 v 3 + v 2 3 u 3 = αv 1 v 3 + αv 2 2 + αv 2 v 3 + αv 2 3
and G :

   u 1 = v 2 1 + αv 1 v 2 + α 2 v 1 v 3 + α 2 v 2 v 3 + v 2 3 u 2 = αv 1 v 2 + αv 2 2 + αv 2 v 3 + α 2 v 2 3 u 3 = α 2 v 1 v 3 + α 2 v 2 2 + α 2 v 2 v 3 + α 2 v 2 3 ,
where α is the defining element of F 4 with α 2 + α + 1 = 0. One can check that, for

T 1 :    y 1 = α 2 u 2 + α 2 u 3 y 2 = u 1 + α 2 u 2 + αu 3 y 3 = u 1 + u 2 + u 3 L 1 :    v 1 = αx 1 + α 2 x 3 v 2 = αx 1 v 3 = αx 1 + α 2 x 2
and T 2 :

   y 1 = α 2 u 1 + u 3 y 2 = u 1 + α 2 u 2 y 3 = u 1 + α 2 u 2 + α 2 u 3 L 2 :    v 1 = x 1 + x 2 v 2 = α 2 x 1 + αx 2 + α 2 x 3 v 3 = x 1 + αx 3 , we have T 1 • F • L 1 = T 2 • G • L 2 .
In above example, different triples (T 1 , F, L 1 ) and (T 2 , G, L 2 ) lead to the same encryption mapping (i.e. public key). For this reason, we introduce the following definition.

Definition 1. Let F and G be two central functions. We shall say that the MPKC schemes derived from F and G are equivalent if there are two pairs (T 1 , L 1 ) and (T 2 , L 2 ) of invertible affine transformations such that

T 1 • F • L 1 = T 2 • G • L 2 .
Example 2. Let F , T 1 and L 1 be as in Example 1. Let

T 3 :    y 1 = u 1 + u 3 y 2 = αu 1 + α 2 u 2 + α 2 u 3 y 3 = α 2 u 1 + u 2 + α 2 u 3 L 3 :    v 1 = x 1 + x 2 v 2 = x 1 + α 2 x 2 v 3 = α 2 x 1 + x 2 + α 2 x 3 . Then T 1 • F • L 1 = T 3 • F • L 3 , i.e. (T 1 , L 1
) and (T 3 , L 3 ) induce the same public key F :

   y 1 = α 2 x 2 1 + αx 1 x 2 + α 2 x 1 x 3 + α 2 x 2 2 + αx 2 x 3 y 2 = α 2 x 1 x 2 + α 2 x 2 2 + αx 2 x 3 + αx 2 3 y 3 = αx 2 1 + αx 1 x 2 + αx 2 2 + αx 2 3 .
The above example shows that, for a fixed central function, different secret keys can lead to the same encryption mapping(i.e. public key). For this reason, we have Definition 2. Let F be a central function, (T 1 , L 1 ) and (T 2 , L 2 ) be two different pairs of secret keys. We shall say that (T 1 , L 1 ) and (T 2 , L 2 ) are equivalent keys of the scheme derived from F if

T 1 • F • L 1 = T 2 • F • L 2 .
The above two examples show that neither different central functions nor different secret pairs can guarantee leading to different encryption mappings. Equivalent schemes have the same set of encryption mappings, and so can be considered as the same scheme.

Having a large private (and consequently public) key space is a desirable property for any public key scheme. We emphasize that the existence of equivalent keys shrink the key space as only one equivalent key are useful and others are superfluous, and so it will have a smaller private and public key space than initially expected.

A similar notation of superfluous keys has been introduced by Wolf and Preneel in [START_REF] Wolf | Large superfluous keys in multivariate quadratic asymmetric systems[END_REF]. More precisely, superfluous keys in the Wolf-Preneel terminology are triples of central function and affine transformations that can induce the same encryption mappings. So, it is, in fact,the combination of equivalent schemes and equivalent keys in our framework, our approach is finer and more general.

Whilst the Multivariate Public Key Cryptosystems (MPKC) are considered to be a good candidate for the post-quantum era, the security of such schemes is still hard to establish. This is evidenced by the successful cryptanalysis of several pioneering schemes, namely C * [START_REF] Patarin | Cryptoanalysis of the matsumoto and imai public key scheme of eurocrypt'88[END_REF], HFE [START_REF] Faugère | Algebraic cryptanalysis of Hidden Field Equation (HFE) cryptosystems using Gröbner bases[END_REF] and SFLASH [START_REF] Dubois | Cryptanalysis of sflash with slightly modified parameters[END_REF][START_REF] Dubois | Practical cryptanalysis of sflash[END_REF]. Although there are several proposals of MPKC which are assumed to be secure (QUARTZ [START_REF] Patarin | Quartz, 128-bit long digital signatures[END_REF] and UOV [START_REF] Kipnis | Unbalanced oil and vinegar signature schemes[END_REF] for instance), there is a global feeling of insecurity for such schemes. In this context, it is important to have a deeper understanding of MPKC. Up to now, most papers about MPKC analyze the security of a specific scheme, only few papers are related to the study of secret key size and the potentiality of MPKC schemes.

In this paper, we present a new framework for counting how many (non-equivalent) different schemes we can construct and how many equivalent keys (a.k.a. superfluous keys [START_REF] Wolf | Large superfluous keys in multivariate quadratic asymmetric systems[END_REF]) there are for a specific scheme. Clearly, both equivalent schemes and equivalent keys are tightly connected to the counting problem of the following mathematical problem:

Problem. Given two polynomial systems F and G, to find, if any, a pair of invertible affine transformations (T, L)

such that T • F • L = G.
The above problem is called IP problem [START_REF] Patarin | Hidden fields equations (hfe) and isomorphisms of polynomials (ip): Two new families of asymmetric algorithms[END_REF]. From an algorithmic point of view, IP and its variants have been thoroughly investigated, e.g. [START_REF] Faugère | Polynomial equivalence problems: Algorithmic and theoretical aspects[END_REF][START_REF] Levy | Polynomial equivalence problems and applications to multivariate cryptosystems[END_REF][START_REF] Pierre-Alain Fouque | Practical cryptanalysis of the identification scheme based on the isomorphism of polynomial with one secret problem[END_REF][START_REF] Fouque | Key recovery on hidden monomial multivariate schemes[END_REF]. The authors of [START_REF] Faugère | Polynomial equivalence problems: Algorithmic and theoretical aspects[END_REF] proposed the first efficient (i.e. allowing to solve cryptographic challenges) algorithm for solving random instances of IP. Recently, new algorithms for IP and its variants have been proposed [START_REF] Pierre-Alain Fouque | Practical cryptanalysis of the identification scheme based on the isomorphism of polynomial with one secret problem[END_REF]. These new algorithms combine (discrete) differential and Gröbner bases techniques permitting to further increase the number of instances of IP which can be solved efficiently. Interesting enough, it was observed experimentally in [START_REF] Faugère | Polynomial equivalence problems: Algorithmic and theoretical aspects[END_REF] that the difficulty of IP seems to be linked to the size of the automorphism group, which is related to the number of solutions of an IP instance.

In this paper, however, we consider the counting problem associated to IP. As we know, IP induces an equivalence relation among the polynomial systems, so a set of polynomial systems can be divided into disjoint union of equivalence classes, thus we can count both the cardinality of an equivalence class and the number of equivalence classes of polynomial systems, which is equivalent to counting the number of "equivalent" secret keys in a multivariate scheme and the total number of different multivariate cryptographic schemes respectively.

To this end, we will extensively use tools of finite geometry [START_REF] Wan | On the symplectic invariants of a subspace of a vector space[END_REF][START_REF] Wan | On the orthogonal invariants of a subspace of a vector space over a finite field of odd characteristic[END_REF][START_REF] Wan | Anzahl theorems in finite singular symplectic, unitary and orthogonal geometries[END_REF][START_REF] Wan | Further studies of singular symplectic, unitary and orthogonal geometries over finite fields[END_REF][START_REF] Wan | Geometry of classical groups over finite fields[END_REF]. Geometries over finite fields study in particular the standard form of quadratic form over finite fields under some linear transformation, which is related to the IP problem.

Organization of the Paper. In Section 2, we recall the definition of IP and introduce the connection between IP and the matrices congruence problem . This is the key point of the paper. In Section 3, we study the enumeration problem of polynomial isomorphism classes in two different cases: char(F q ) = 2 and char(F q ) = 2. In each case, we provide a lower bound on the total number of (linearly) equivalence classes. Finally, in Section 4 we will give some basic results for this enumeration problem and consider their application to some specific multivariate cryptographic system (C * and HFE). In particular, we provide a partial answer about how many different cryptographic schemes can be derived from a monomial central function, and how many pairs of secret keys we can choose for a fixed scheme/central function, which is the real scale of its private key space.

Preliminary

In this section, we recall the definition of IP problem introduced in [START_REF] Patarin | Hidden fields equations (hfe) and isomorphisms of polynomials (ip): Two new families of asymmetric algorithms[END_REF] and a useful theorem given by Kipnis and Shamir in [START_REF] Kipnis | Cryptanalysis of the hfe public key cryptosystem by relinearization[END_REF] (restated by Ding in his book [START_REF] Ding | Multivariate Public Key Cryptosystems (Advances in Information Security)[END_REF]) which is about the relation between polynomials system and univariate polynomial over extension field. We also introduce a new notation called friendly mapping. Both the theorem and friendly mapping provide the key ingredient to connect our new tool to IP problem.

Isomorphism of Polynomials

Let F q be a finite field with q elements and F q [x 1 , . . . , x n ] be the ring of polynomials in n ≥ 1 indeterminates over F q .

Definition 3. We denote by P the set of all the transformations F : (x 1 , . . . ,

x n ) → (f 1 , . . . , f n ) from F n q to F n q , where f i = n s=1 s t=1 c i,st x s x t ∈ F q [x 1 , • • • , x n ].
We say that F 1 ∈ P and F 2 ∈ P are equivalent if there exist two invertible linear transformations (T, L)

∈ GL n (F q ) × GL n (F q ) such that F 2 = T • F 1 • L.
Clearly, the above relation is an equivalence relation on the elements of P. Thus, P can be written as a disjoint union of different equivalence classes. The problem of recovering the transformations T and L is known as IP with two secrets. A restricted problem called IP with one secret (IP1S)(see [START_REF] Patarin | Hidden fields equations (hfe) and isomorphisms of polynomials (ip): Two new families of asymmetric algorithms[END_REF]) involves only one transformation on the variables, namely to find L ∈ GL n (F q ) such that F 2 = F 1 • L. Generally, this simplification will induce more equivalence classes. Indeed, linear transformation T mixes some classes together.

Remark 1. Note that, in the case of q = 2, it holds that x 2 k = x k . As as a consequence, the f i 's in Definition 3 are not always homogeneous. They are, in fact, quadratic polynomials without constant terms. For simplicity and by abuse of language, we still refer to such polynomials as homogeneous in this paper. IP (as well as IP1S) can also be interpreted as a group action. Let G = GL n (F q ) × GL n (F q ) be the direct product of GL n (F q ) and GL n (F q ), then G forms a group under the operation:

(T 1 , L 1 ) • (T 2 , L 2 ) = (T 1 • T 2 , L 2 • L 1 )
. Considering G acting on the set P, we can define the invariant group of F ∈ P as follows:

H = {(T, L) : T • F • L = F }. Then T 1 •F •L 1 = T 2 •F •L 2 iff (T -1 1 •T 2 )•F •(L 2 •L -1 1 ) = F , hence (T -1 1 •T 2 , L 2 •L -1 1 ) ∈ H.
This means that in order to study equivalent keys, it suffices to study the invariant group H of F . H is a subgroup of G and each coset of this subgroup corresponds to a non-equivalent private key. Different cryptographic schemes are just the orbits of this group action [START_REF] Faugère | Polynomial equivalence problems: Algorithmic and theoretical aspects[END_REF]. Alternatively, we can view IP from a geometric point of view: thinking the indeterminates x 1 , x 2 , . . . , x n as the coordinates of a point in some coordinate system. The linear transformation can be considered as a coordinate transformation of the coordinate system. The polynomial equivalence problem can then be considered as the study of geometric object defined by the polynomial system under the coordinate transformation. In this paper, we follow the geometric way and adopt results/techniques of finite geometry (or geometries over finite fields) to study IP and IP1S

Considering IP over Extension Fields

Let g(x) ∈ F q [x] be an irreducible polynomial of degree n over F q , then F q n ≃ F q [x]/(g(x)). Let φ : F q n → F n q be the map defined by:

φ(α 0 + α 1 x + . . . + α n-1 x n-1 ) = (α 0 , α 1 , . . . , α n-1 ). (1)
It is easy to check that φ is a F q -vector space isomorphism between F q n and F n q . The following lemma is from literature (we refer the reader to [START_REF] Kipnis | Cryptanalysis of the hfe public key cryptosystem by relinearization[END_REF] and [START_REF] Ding | Multivariate Public Key Cryptosystems (Advances in Information Security)[END_REF] for its proofs).

Lemma 1.

1) Let L be a linear transformation of F n q , then φ -1 • L • φ is of the form:

φ -1 • L • φ(X) = n-1 i=0 α i X q i , where α i ∈ F q n . (2)
2) Let F ∈ P as in Definition 3, then φ -1 • F • φ is of the form:

φ -1 • F • φ(X) = n-1 i=0 i j=0 α ij X q i +q j , where α ij ∈ F q n . (3)
The converse of the results is also true.

We shall say that (2) (resp. (3)) is the univariate representations of the corresponding maps.

From above lemma, we can see that there is a 1-1 correspondence between the polynomial mappings of P (resp. linear transformations) and the univariate representation (3) (resp.

(2)). Thus, we sometimes identify

φ -1 • F • φ (resp. φ -1 • L • φ) with F (resp. L).
Hereafter, we will use F to denote the set of mappings represented by (3) and use L to denote the set of invertible mappings represented by [START_REF] Patarin | The Oil and Vinegar signature scheme[END_REF]. Then F = φ -1 • P • φ and the definition of IP1S can be restated in univariate representation over extension field as follows:

Definition 4. Let F (X) = n-1 i=0 i j=0 a ij X q i +q j , G(X) = n-1 i=0 i j=0 b ij X q i +q j ∈ F.
We say that F and G are linearly equivalent if and only if there exists

L(X) = n-1 i=0 a i X q i ∈ L such that F L(X) = G(X), for all X ∈ F q n . Let L(X) = n-1 i=0 a i X q i be
a polynomial over F q n . We associate a matrix L over F q n to L as follows:

L =       a 0 a q n-1 . . . a q n-1 1 a 1 a q 0 . . . a q n-1 2 . . . . . . . . . . . . a n-1 a q n-2 . . . a q n-1 0       n×n . (4)
It holds that:

Lemma 2. Let L(X) = n-1
i=0 a i X q i be a polynomial over F q n . Then L ∈ L if and only if the matrix L associated to L is invertible. Let B denote the set of all such invertible matrices of the form (4), then B is a subgroup of GL n (F q n ) and is isomorphic to GL n (F q ). Proof. Please refer to the discussion on page 361-362 of [START_REF] Lidl | Finite fields[END_REF].

Definition 5. Let M n×n (F q n ) be the set of all n × n matrices over F q n . A mapping Ψ from F to M n×n (F q n ) is called friendly mapping if for every L ∈ L and F ∈ F: Ψ(F • L) = LΨ(F ) LT ,
where superscript "T" means the transpose of a matrix.

The definition of "friendly mapping" is in fact a method to connect IP over the extension field to the transformations of matrices. Under friendly mapping, the IP problem can be viewed as a congruence problem on matrices. A natural candidate of friendly mapping is given below: Lemma 3. Let F q n be a finite field with q n elements. For any

F = n-1 i=0 i j=0 a ij X q i +q j ∈ F, we define Ψ 1 (F ) ∈ M n×n (F q n ) as Ψ 1 (F ) =      2a 00 a 10 . . . a n-1,0 a 10 2a 11 . . . a n-1,1 . . . . . . . . . . . . a n-1,0 a n-1,1 . . . 2a n-1,n-1      .
Then Ψ 1 is a friendly mapping.

Proof. It is easy to see from Lemma 2.4.1 of [START_REF] Ding | Multivariate Public Key Cryptosystems (Advances in Information Security)[END_REF].

From the definition of Ψ 1 , we can see that Ψ 1 maps polynomials in F into symmetric matrices. When char(F q n ) = 2, these matrices are not only symmetric matrices, but also anti-symmetric matrices whose diagonal elements are all 0. This kind of matrices has a particular name: Definition 6. Let K be a n × n matrix over F q n , if K T = -K, then K is called antisymmetric matrix. Anti-symmetric matrices with all diagonal elements equal to 0 are called alternative matrices.

When char(F q n ) = 2, Ψ 1 maps polynomials in F to alternative matrices, and no entry in the matrix reflects the terms of the form aX 2q i . It is somehow unreasonable to allow a friendly mapping to throw away the terms of the form aX 2q i . But this does not affect much on the analysis of corresponding scheme as already shown in the book [START_REF] Ding | Multivariate Public Key Cryptosystems (Advances in Information Security)[END_REF]. In order to keep these terms and get a finer classification, one can choose other friendly mapping such as the mapping to the residue classes of coefficient matrices modulo alternative group.

Some Bounds on the Number of IP Classes

In this section, we use finite geometry to investigate the number of equivalence classes.

3.1. Isomorphism Equivalence Classes when char(F q ) = 2

Here, we discuss the IP problem for a field F q of characteristic 2. Thanks to the friendly mapping Ψ 1 , introduced in the previous section, we have a correspondence between polynomials in F and the set of n×n matrices. Hence, we can shift from a functional point of view to a matrix point of view. According to the definition of friendly mapping Ψ 1 , we know that the matrices associated to the polynomials in F are alternative matrices. Thus, if two polynomials of F are linearly equivalent, then their associated alternative matrices are congruent. Note that the congruence considered is not under the general linear group GL n (F q n ) as usual but under its subgroup B (as defined in Lemma 2).

Definition 7. Let A n be the set of alternative matrices of order n over F q n . We say that S 1 ∈ A n and S 2 ∈ A n are linearly equivalent if there exits M ∈ B such that

S 2 = M S 1 M T .
As B forms a group under the matrix multiplication, the linear equivalence is indeed an equivalence relation. Hence, the set A n can be written as a disjoint union of linear equivalence classes, namely

A n = L 1 ∪ L 2 ∪ • • • ∪L m , (5)
where m is the total number of linear equivalence classes. Our goal is to find the number m as well as the number of matrices in each class. To address this enumeration problem, we first determine the congruent equivalence classes of A n under the group action of the general linear group GL n (F q n ). We then try to partition these congruent classes into disjoint union of linear equivalence classes.

Lemma 4. Let F q be a finite field with q elements, K be an n × n alternative matrix over F q , then the rank of K must be even. Conversely, if Rank(K) = 2ν, then K must be congruent under GL n (F q ) to a matrix of the following form:

  0 (ν) I (ν) -I (ν) 0 (ν) 0 (n-2ν)   .
Two n × n alternative matrices are congruent if and only if they have the same rank.

Proof. See Page 107, Theorem 3.1 of [START_REF] Wan | Geometry of classical groups over finite fields[END_REF].

Using the congruent equivalence relation under GL n (F q n ), we can divide A n into ⌊ n 2 ⌋ + 1 partitions, i.e. ⌊ n 2 ⌋ + 1 congruent equivalence classes, each class contains alternative matrices having the same rank. Suppose these equivalence classes are

G 0 = {O n×n }, G 2 , • • • , G 2⌊ n 2 ⌋
, where G t contains alternative matrices with rank t. Then

A n = G 0 ∪ G 2 ∪ • • • ∪ G 2⌊ n 2 ⌋
. Usually, we do not consider the class G 0 . In the terminology of group theory, A n is the target set and GL n (F q n ) is the group acting on A n . Every set G t is an orbit under this group action. We know then the total number of orbits is ⌊ n 2 ⌋ + 1 . Next, we want to determine the length of each orbit. Namely, we try to count how many elements there are in each congruent equivalence class. To do this, we introduce the concept of extended symplectic group.

Definition 8. Let K e = K 0 2ν×(n-2ν) 0 (n-2ν)×2ν
0 (n-2ν) be an alternative matrix over F q , where K = 0 (ν) I (ν) -I (ν) 0 (ν) . The extended symplectic group Sp n,ν (F q ) is the set of all non-singular n × n matrices T satisfying T K e T T = K e .

Matrices in the extended symplectic group are of the following form.

Lemma 5. Sp n,ν (F q ) consists of matrices of the form:

T 11 T 12 0 (n-2ν)×2ν T 22
with the requirement that T 11 KT T 11 = K and T 22 is an invertible matrix of order n -2ν, where K is as in Definition 8.

This will be used in Section 4. The following well known facts (for instance, you can see in [START_REF] Wan | Geometry of classical groups over finite fields[END_REF]) will be also useful.

Lemma 6.

1) The number of invertible n × n matrices over F q is

|GL n (F q )| = q n(n-1) 2 n i=1 (q i -1).
2) The number of matrices in the extended symplectic group Sp n,ν (F q ) is

|Sp n,ν (F q )| = ν i=1 (q 2i -1) ℓ i=1 (q i -1)q ν 2 +2νℓ+ ℓ(ℓ-1)

2

, where ℓ = n -2ν. Now, we are ready to compute the length of the orbit G 2ν .

Theorem 1. The number of different elements in G 2ν is

|GL n (F q n )| |Sp n,ν (F q n )| = n i=1 (q ni -1)q n 2 (n-1) 2 ν i=1 (q 2ni -1) ℓ i=1 (q ni -1)q n(ν 2 +2νℓ+ ℓ(ℓ-1)
2

)
,

where ℓ = n -2ν.

Proof. According to Lemma 4, every matrix in G 2ν must be congruent to an alternative n × n matrix K e as defined in Definition 8. Thus, each matrix in G 2ν has the form of M K e M T , where M is an invertible n × n matrix over F q n . Therefore, if two elements

M 1 K e M T 1 = M 2 K e M T 2 , it follows that K e = (M -1 1 M 2 )K e (M -1 1 M 2 ) T , hence M -1 1 M 2 ∈ Sp n,ν (F q n ). Then the number of different elements in G 2ν is |GL n (F q n )|/|Sp n,ν (F q n )|.
We now consider the partition of (5). As B is a subgroup of GL n (F q n ), every L i must be contained in some G j . This means that each G j must be a disjoint union of some L i 's. Suppose that G t has m t partitions, i.e.

G t = L t,1 ∪L t,2 ∪ • • • ∪L t,mt . Then, m = m 0 + m 2 + • • • + m 2⌊ n 2 ⌋
. Now, we try to estimate the value of m t . We provide a lower bound of m t and then derive a lower bound of m.

Theorem 2. The number of elements in L t,j is upper bounded by the order of B, i.e.

|L t,j | ≤ n i=1 (q i -1)q n(n-1) 2
.

Proof. The orbit equation yields |L t,j | = [B : T t,j ], where T t,j is the stabilizer of some matrix in L t,j under the group action of B. Obviously |T t,j | ≥ 1, and thus |L t,j | ≤ |B|.

From Lemma 2, B ∼ = GL n (F q ) and we conclude by using 1) of Lemma 6.

In the proof, the number of elements in L t,j are obtained using the stabilizer of some matrix in L t,j under the group action of B. This is somewhat the core difficulty of enumeration problems in general. By combining Theorem 1 and Theorem 2, we get:

Theorem 3. It holds that m 2ν is at least |G2ν | |GLn(Fq)| for 1 ≤ ν ≤ ⌊ n 2 ⌋, i.e. m 2ν ≥ n i=1 (q ni -1)q n 2 (n-1) 2 ν i=1 (q 2ni -1) ℓ i=1 (q ni -1)q n(ν 2 +2νℓ+ ℓ(ℓ-1) 2 ) n i=1 (q i -1)q n(n-1) 2
, where ℓ = n -2ν.

Proof. Since G 2ν = L 2ν,1 ∪L 2ν,2 ∪ • • • ∪L 2ν,m2ν , Theorem 2 yields |G 2ν | = m2ν i=1 |L 2ν,i | ≤ m2ν i=1 |B| = m 2ν |B|.
Corollary 1. A lower bound for the number of linear equivalence classes is

⌊ n 2 ⌋ ν=1 n i=1 (q ni -1)q n 2 (n-1) 2 ν i=1 (q 2ni -1) ℓ i=1 (q ni -1)q n(ν 2 +2νℓ+ ℓ(ℓ-1) 2 ) n i=1 (q i -1)q n(n-1) 2 + 1,
where ℓ = n -2ν.

Isomorphism Equivalence Classes when char(F

q ) = 2
We suppose here that the characteristic of F q is odd. As in the previous subsection, we try to get a lower bound on the number of all linear equivalence classes. Here, we use orthogonal geometry over finite fields. Let S be a non-singular symmetric matrix over F q . We shall say that an invertible matrix T is an orthogonal matrix with respect to S if T ST T = S. The set of all orthogonal matrices forms a group under matrix multiplication. We call this group orthogonal group of order n with respect to S. It will be denoted by O n (F q , S).

Lemma 7. Every symmetric matrix over F q is congruent to exactly one of the following matrices:

M (n, 2ν, ν) = S 0 (n-2ν) , M (n + 1, 2ν + 1, ν, 1) =   S 1 0 (n-2ν)   , M (n + 1, 2ν + 1, ν, z) =   S z 0 (n-2ν)   , M (n + 2, 2ν + 2, ν) =     S 1 -z 0 (n-2ν)     ,
where S = 0 (ν) I (ν) I (ν) 0 (ν) and z is a fixed non-square element in F * q .

For the proof, we refer again to [START_REF] Wan | Geometry of classical groups over finite fields[END_REF]. Let S be the set of all symmetric matrices of order n over F q n . According to Lemma 7, we can divide S into 2n + 1 congruent equivalence classes under the general linear group GL n (F q n ). We have to compute how many linear equivalence classes are in each congruent equivalence class and how many different matrices in each linear equivalence class.

Let S e = S 0 (2ν+δ)×ℓ 0 ℓ×(2ν+δ) 0 (ℓ) , where S = M (2ν + δ, 2ν + δ, ν, ∆) is the canonical form as defined in Lemma 7 and ∆ represents the definite fixed part of the corresponding form. The set of all (2ν + δ + ℓ) × (2ν + δ + ℓ) invertible matrices T such that T S e T T = S e forms a group. This group is the extended orthogonal group, written as O 2ν+δ+ℓ,2ν+δ,ν,∆ (F q ) or O 2ν+δ+ℓ,∆ (F q ) in short. The general form of such matrices is given below:

Lemma 8. O 2ν+δ+ℓ,∆ (F q ) consists of matrices of the form:

T 11 T 12 0 ℓ×(2ν+δ) T 22
with the requirement that T 11 ST T 11 = S and T 22 is an invertible matrix of order ℓ, where

S = M (2ν + δ, 2ν + δ, ν, ∆). Lemma 9. The order of O 2ν+δ+ℓ,∆ (F q ) is |O 2ν+δ+ℓ,∆ (F q )| = ν i=1 (q i -1) ν+δ-1 i=0 (q i + 1) ℓ i=1
(q i -1)q ν(ν+δ-1)+ℓ(2ν+δ)+ ℓ(ℓ-1)

2

.

Again, we refer to [START_REF] Wan | Geometry of classical groups over finite fields[END_REF] for a proof.

Corollary 2. Let S n,2ν+δ,ν,∆ (F q n ) be the set of all symmetric matrices congruent to M (n, 2ν + δ, ν, ∆), then

|S n,2ν+δ,ν,∆ (F q n )| = |GL n (F q n )| |O 2ν+δ+ℓ,∆ (F q n )| .
According to Theorem 2, each congruent class must be a disjoint union of some linear equivalence classes, and each one contains at most |GL n (F q )| different elements. Thus:

Theorem 4. The number of linear equivalence classes contained in S n,2ν+δ,ν,∆ (F q ) is lower bounded by:

|GL n (F q n )| (|O 2ν+δ+ℓ,∆ (F q n )|)(|GL n (F q )|)
,

where ℓ = n -2ν -δ.
Finally, by running on all the possibilities of choices of ν, δ and ∆, we get:

Corollary 3.
A lower bound of the number of linear equivalence classes is:

⌊ n 2 ⌋ i=1 |GL n (F q n )| (|O 2i+0+(n-2i),∆ (F q n )|)(|GL n (F q )|) + |GL n (F q n )| (|O 2(i-1)+2+(n-2i),∆ (F q n )|)(|GL n (F q )|) + ⌈ n 2 ⌉-1 i=0 2|GL n (F q n )| (|O 2i+1+(n-2i-1),1 (F q n )|)(|GL n (F q )|) + 1.

Tightness of the bounds

The lower bounds given in this section are very rough. When char(F q ) = 2, Ψ 1 throws away the terms of the form X 2q i . Thus the target set A n is much smaller than the original target set F. We actually estimate the lower bound of number of linear equivalence class of polynomials of the form n-1 i=0 α ij X q i +q j with i = j, but this does not affect much on the analysis of corresponding scheme as already shown in the book [START_REF] Ding | Multivariate Public Key Cryptosystems (Advances in Information Security)[END_REF].

Another reason for the untightness is that we roughly use the order of GL n (F q ) as the cardinality of each linear equivalence class. Actually, different equivalence classes may have different cardinalities, that means there may be many linear equivalence classes whose cardinalities are much smaller than |GL n (F q )|. As an example, please see Corollary 4 and Corollary 5 of Section 4. As a result, even if we can compute the exact size of some equivalence classes, we still can not take advantage of the results to compute the sizes of other classes. The size of each equivalence class depends much on the properties of the polynomials of the class. We note that the size of the equivalence class containing permutation polynomials must be exactly |GL n (F q )|, but for some non-permutation polynomials, its orbit can also contain |GL n (F q )| elements. How to characterize such polynomials is still an open problem. From the viewpoint of finite geometry, the IP problem is related to identifying the standard form of alternative matrices (resp. symmetric matrices) when char(F q ) = 2 (resp. char(F q ) = 2) under the congruence action of special group B (see Lemma 2). As some elementary matrices are not in B, such problem become difficult and many classical results of finite geometry are not appliable in such cases.

Applications to Multivariate Public-Key Crytptography

In this section, we count the number of different schemes and equivalent keys that can be derived from monomials over extension field. This kind of schemes is a generalization of Matsumoto-Imai scheme (a.k.a. C * scheme) whose central function is of the form X q t +1 with gcd(q n -1, q t + 1) = 1 [START_REF] Matsumoto | Public quadratic polynomial-tuples for efficient signatureverification and message-encryption[END_REF]. We call such generalization MI-type schemes. Definition 9. Let F q be finite field with q elements and n be a positive integer. We shall say that L 1 •F •L 2 is a MI-type scheme if L 1 and L 2 are invertible linear transformations over F n q and F is a monomial over F q n of the form aX q i +q j , for i, j, 0 ≤ i, j ≤ n -1 and a ∈ F * q n . For such schemes, our goal is to identify all its equivalence classes and count the number of elements in each class. We emphasize that the purpose of the generalization is not to increase the security of the scheme. The basic Patarin's bi-linear attack [START_REF] Patarin | Cryptoanalysis of the matsumoto and imai public key scheme of eurocrypt'88[END_REF] against C * still works for MI-type schemes. Let F be as defined in Section 2. Under the linear equivalence relation, F can be divided into disjoint equivalence classes. In the sequel, we call a monomial of F a "monomial point" and the equivalence class an "orbit". For all f ∈ F q n [X], we can associate a polynomial mapping

f : c → f (c) from F q n into F q n . Let R(f ) = {f (c)|c ∈ F * q n } and ker(f ) = {c ∈ F * q n |f (c) = 1}
, here we use f to denote both the polynomial and the associated mapping. Then R(X q i+t +q t ) = R(X q i +1 ) and |R(X q i+t +q t )| = |R(X q i +1 )| = q n -1 gcd(q i +1,q n -1) for any t, 0 ≤ t ≤ n -1.

Number of Orbits Containing Monomials

In this subsection, we determine how many equivalence classes contain monomials. Before stating the main results of this part, we give several intermediate results which will be used through this section.

Hereafter, we will use E i (c) to denote the elementary matrix obtained by multiplying the i-th row of identity matrix by c, E ij the elementary matrix obtained by interchanging the i-th row and j-th row of identity matrix, and E ij (c) the elementary matrix obtained by adding the i-th row multiplied by c to the j-th row of identity matrix.

Lemma 10. Let a, b ∈ F * q n and 0 ≤ i ≤ n -1. The monomial aX 2q i can not be linearly equivalent to bX q u +q v for any u = v.

Proof. By contradiction, assume there exists an invertible linear transformation L(X) such that aX 2q i • L(X) = bX q u +q v . By the definition of Ψ 1 , we have LΨ 1 (aX

2q i ) LT = Ψ 1 (bX q u +q v ). It follows Rank LΨ 1 (aX 2q i ) LT = Rank Ψ 1 (bX q u +q v ) .
But Rank Ψ 1 (bX q u +q v ) = 2. On the other hand:

Rank( LΨ 1 (aX 2q i ) LT ) = Rank(Ψ 1 (aX 2q i )) = 0 , char(F q ) = 2, 1 , char(F q ) = 2,
which leads to a contradiction. Thus the lemma is proved.

Lemma 11. Let 0 ≤ i, j ≤ n -1 and L(X) be a linear transformation:

(i) L(X) is a monomial if and only if X q i • L(X) • X q j is a monomial; (ii) L(X) is a permutation polynomial of F q n if and only if X q i • L(X) • X q j is a permutation polynomial of F q n .
Proof. This lemma is trivial from the truth that X q i and X q j are both permutation polynomials over F q n and their inverse polynomials are also monomials.

Lemma 12. If there exists an invertible linear transformation L(X) = n-1 k=0 c k X q k such that aX 2q i • L(X) = bX 2q j with 0 ≤ i, j ≤ (n -1) and a, b ∈ F * q n , then L(X) must be a monomial.

Proof. When char(F q ) = 2:

bX 2q j = aX 2q i • L(X) = a n-1 k=0 c k X q k 2q i = n-1 k=0 ac 2q i k X 2q k+i .
Thus c 2q i j-i = a -1 b and the others coefficients of L(X) must be zero, where the index of c i is computed modulo n. When char(F q ) = 2: by assumption, we have

aX 2q i • L(X) = bX 2q j ⇔ X 2 • (X q i • L(X) • X q n-j ) = a -1 bX 2 .
By Lemma 11, it is sufficient to prove that if there exists an invertible linear transformation L(X) such that X 2 • L(X) = cX 2 , then L(X) must be a monomial.

By the very definition of Ψ 1 , we have that LΨ 1 (X 2 ) LT = Ψ 1 (cX 2 ), where L is the associated matrix to L(X) and thus L ∈ B as in Lemma 2. By letting X = 1 in X 2 • L(X) = cX 2 it follows that c = (L(1)) 2 . Thus c must be a square element of F q n . Now, let c = α 2 , we have

α I (n-1) 2 I (n-1) α I (n-1) = 2c I (n-1) , i.e. E 1 (α)Ψ 1 (X 2 )E 1 (α) T = Ψ 1 (cX 2 ). Thus LΨ 1 (X 2 ) LT = E 1 (α)Ψ 1 (X 2 )E 1 (α) T , (E 1 (α) -1 L)Ψ 1 (X 2 )(E 1 (α) -1 L) T = Ψ 1 (X 2 ). Therefore L ∈ E 1 (α)O n F q n , Ψ 1 (X 2 ) . By Lemma 8, L ∈ E 1 α)O n (F q n , Ψ 1 (X 2
) must be in the following form:

αa 11 αT 12 0 (n-1)×1 T 22 .
with a 2 11 = 1 and T 22 invertible. The fact that L ∈ B implies that L is a diagonal matrix. Hence, the linear polynomial L(X) corresponding to L is a monomial.

The following result is about the monomial bX q u +q v , with u = v. Lemma 13. If there exists an invertible linear transformation L(X) = n-1 k=0 c k X q k such that aX q s +q t • L(X) = bX q u +q v with s = t, u = v, then L(X) must be a monomial.

Proof. Clearly, by Lemma 11, it is sufficient to prove that if there exists an invertible linear transformation L(X) such that X q i +1 • L(X) = cX q j +1 where 1 ≤ i, j ≤ n -1, then L(X) must be a monomial. Without loss of generality we can suppose that 1 ≤ i ≤ j ≤ n -1. Now we first consider the case char(F q ) = 2.

By the definition of Ψ 1 , we have LΨ 1 (X q i +1 ) LT = Ψ 1 (cX q j +1 ), where L ∈ B is the matrix associated to L as in Lemma 2. Since

E j+1 (c)E i+1,j+1 Ψ 1 (X q i +1 )E T i+1,j+1 E j+1 (c) T = Ψ 1 (cX q j +1 ), we have L ∈ E j+1 (c)E i+1,j+1 Sp n (F q n , Ψ 1 (X q i +1 )). Since Sp n F q n , Ψ 1 (X q i +1 ) = E 2,i+1 Sp n F q n , Ψ 1 (X q+1 ) E 2,i+1
, so, by Lemma 5, a matrix in Sp n F q n , Ψ 1 (X q i +1 ) must be of the form:

                a 11 a 1,
a n3 • • • a nn    = 0. Thus, L ∈ E j+1 (c)E i+1,j+1 Sp n F q n , Ψ 1 (X q i +1 ) is of the form                      a 11 a 1,
                    
.

Note that L ∈ B and any diagonal of a matrix in B is of the form {α, α q , α q 2 , • • • , α q n-1 } with some α ∈ F q n . Hence, there are at most two diagonals in L whose elements all are not zeros and elements in other diagonals are all zeros. These two non-zero diagonals are diagonals containing a 11 and ca 21 respectively. Now we investigate L in two cases: Case 1. i = n 2 , i.e. i = n -i.

• If j ∈{i, n -i}, then L is a zero matrix since there is a zero on each diagonal.

• If j = i, then the only nonzero diagonal is the main diagonal. Thus L(X) = a 11 X.

• If j = n -i, then the only nonzero diagonal of L is the one containing ca 21 . Thus L(X) = ca 21 X q n-i .

Case 2. i = n 2 , i.e. i = n -i.

• If j = n 2 , then L is a zero matrix since there is no non-zero diagonal.

• If j = n 2 , then there are two nonzero diagonals of L. One is the main diagonal, the other is the one containing ca 21 . Thus L(X) =c 1 X + c 2 X q n 2 . By hypothesis that

X q i +1 • L(X) = cX q j +1 , i.e. X q n 2 +1 • L(X) = cX q n 2 +1 , we have cX q n 2 +1 = X q n 2 +1 • L(X) = (c 1 X + c 2 X q n 2 ) q n 2 +1 = (c q n 2 +1 1 + c q n 2 +1 2 )X q n 2 +1 + c 1 c q n 2 2 X 2 + c q n 2 1 c 2 X 2q n 2 . Thus c q n 2 +1 1 + c q n 2 +1 2 = c and c 1 c q n 2 2 = c q n 2 1 c 2 = 0, which implies that c 1 = 0 or c 2 = 0, i.e. L(X) is c 1 X or c 2 X q n 2 .

Length of Orbits Containing Monomial Points

We compute here the length of orbits containing monomial points. As already pointed out, this is equivalent to describe non-equivalent keys of a MPKC scheme. In particular, we show that some HFE instances, i.e. with more than one monomial occurring in the central function, can be equivalent to MI-type schemes. Thus, considering the insecurity of MI-type schemes, we have of course to avoid such weak instances. To compute the length of an orbit, we have to identify the stabilizer of such monomial under the action of invertible linear transformations.

Definition 10. The stabilizer of F ∈ F is defined as the set of all invertible linear transformation L(X) ∈ L defined in Section 2.3 such that F • L(X) = F .

Clearly, the stabilizer of F is a subgroup of L which is isomorphic to GL n (F q ). If the mapping induced by F is bijective, then the stabilizer of F has only one element, i.e. X. For a monomial point, we can describe its stabilizer as follows.

Theorem 8. Let 1 ≤ i ≤ n -1 and a ∈ F * q n . The stabilizer of aX q i +1 is {cX|c q i +1 = 1, c ∈ F * q n } when i = n 2 and {cX q t |c q i +1 = 1, c ∈ F * q n and t = 0 or n 2 } when i = n 2 .
Proof. By definition, the stabilizer of aX q i +1 is the set of all invertible linear transformation L(X) such that aX q i +1 • L(X) = aX q i +1 . From Lemma 12 and Lemma 13, it follows that L(X) = cX q k . We have then

aX q i +1 = aX q i +1 • L(X) = aX q i +1 • cX q k = ac q i +1 X q i+k +q k .
This leads to the following equivalent conditions : c q i +1 = 1 and two systems of congruence equations:

(I) i + k ≡ i (mod n) k ≡ 0 (mod n) or (II) i + k ≡ 0 (mod n) k ≡ i (mod n)
From (I), we get that k = 0. From (II), we see that i = k = n 2 . This mean that when i = n 2 the stabilizer is {cX|c q i +1 = 1, c ∈ F * q n }. On the other hand, when i = n 2 , the stabilizer is {cX q t |c q n 2 +1 = 1, c ∈ F * q n and t = 0 or n 2 }.

By noticing that the order of the stabilizer of aX q i +1 is |ker(X q i +1 )| for i = n 2 and 2|ker(X q i +1 )| when i = n 2 , we get:

Corollary 4. Let 1 ≤ i ≤ n -1 and a ∈ F * q n .
The length of the orbit containing the monomial point aX

q i +1 is |GLn(Fq)| |ker(X q i +1 )| when i = n 2 and |GLn(Fq)| 2|ker(X q i +1 )| when i = n 2 .
In the special case of F (X) = aX 2q i , we have:

Theorem 9. Let 0 ≤ i ≤ n -1 and a ∈ F * q n . The stabilizer of aX 2q i is reduced to X when char(F q ) = 2 and ±X when char(F q ) = 2.

Proof. As in the proof of Theorem 8, we can suppose that L(X) = cX q k . This leads to aX 2q i = aX 2q i • cX q k = ac 2q i X 2q i+k . Then, we have c 2q i = 1 and i + k ≡ i (mod n). It follows that k = 0, c = 1 when char(F q ) = 2 and c = ±1 when char(F q ) = 2.

Corollary 5. Let 0 ≤ i ≤ n -1 and a ∈ F * q n . The length of the orbit containing the monomial point aX 2q i is |GL n (F q )| for char(F q ) = 2 and |GLn(Fq)| 2

for char(F q ) = 2.

According to Corollary 4 and Corollary 5, the number of equivalent keys of a scheme derived from a monomial aX q u +q v is related to the kernel of X q u +q v . If the monomial induces a permutation, then there is no equivalent keys at all. This means that for a fixed central function, different keys will lead to different encryption maps.

Implication of the Results of this Section

Comparing with MI scheme whose central function has only one term in its univariate representation, HFE schemes have several terms in order to avoid the linearized attacks that MI schemes suffer from. Surprisingly enough, the results of this section show that although the central function is restricted to a monomial in MI-type scheme, its equivalent schemes can be in HFE category, i.e. with more than one monomial occuring in the central function. In other words, we show that HFE is not always more secure than MI schemes which is supposed to be. In fact, by Lemma 14 and Corollary 4, the linear equivalence class of aX q u +q v contains n|R(X q u-v +1 )| different monomials if u -v = n 2 and n 2 |R(X q 2|ker(X q u-v +1 )| -n 2 |R(X q u-v +1 )| if u -v = n 2 , polynomials containing more than one term and so belonging to the HFE category. The above arguments show that, in each class containing monomial, quite portion of the polynomials contain more than one term. This implies that, in each class, there are several HFE instances -seemingly complex and hard to solve -which are actually as easy as MI-type instances. Precisely, there are n+1 2 |GL n (F q )| different polynomials in F which are linearly equivalent to some monomials. Note that F contains some linear polynomials of the form aX 2q k when q = 2, the number of quadratic polynomials in F linearly equivalent to some monomial is exactly n+1 2 |GL n (F q )| (resp. n-1 2 |GL n (F q )|) when q > 2 (resp. q = 2), among them there are 1 2 n(n + 1)(q n -1) resp. 1 2 n(n -1)(q n -1) monomials. Thus the number of all HFE instances, i.e. quadratic polynomials which has more than two terms, linearly equivalent to some monomial is n+1 2 |GL n (F q )| - 1 2 n(n + 1)(q n -1), for q > 2, n-1 2 |GL n (F q )| -1 2 n(n -1)(q n -1), for q = 2.

In summary, the results of this section not only answer how many cryptographic schemes at most we can derive from monomials (Theorem 7) but also show that quite many HFE cryptosystems are equivalent to MI-type schemes. In such way, by identifying equivalent schemes, we can rule out several HFE schemes from possible use. However, it is not clear how to decide efficiently if a HFE scheme is equivalent to a MI-type scheme.

Conclusion and Future works

In this article, we brought a new question related to the IP problem, i.e. to determine the number of all the isomorphism equivalence classes of quadratic homogeneous polynomial systems. This question is equivalent to counting the equivalent keys and equivalent schemes of multivariate cryptography. In terms of cryptography, more equivalent keys exist means smaller key space and the number of equivalence classes means the number of different schemes we can have with same parameter, both of them are very important in practice as having a large number of private keys and more choices of instances of cryptographic schemes is always desirable properties for public key cryptography. By adopting a new tool of finite geometry, we have provided a framework for approaching to the question. Though determining all the equivalence classes is still an open problem, it seems that finite geometry is a good language to study it.

n 2 +1

 2 )| different monomials if u -v = n 2 .Therefore, there are|GLn(Fq)| |ker(X q u-v +1 )| -n|R(X q u-v +1 )| if u -v = n 2 ,and |GLn(Fq)|

Acknowledgement

The authors would like to thank anonymous referees and Shuhong Gao for their valuable comments and discussions. This work was supported by the National 973 Program of China under Grant 2011CB302400, the National Natural Science Foundation of China under Grant 60970152, the Grand Project of Institute of Software under Grant YOCX285056.

For the case of char(F q ) = 2, the analysis is similar but we need replacing the extended symplectic group with the extended orthogonal group.

By Lemma 10, we know that αX q u +q v (u = v) and βX 2q i can not be in the same orbit, so in the following of this section, we will study the two types of monomials seperately. First we will show the number of orbits containing some monomial of the form aX q u +q v (u = v) and the number of monomials in each of these orbits.

Lemma 14. The number of monomials in the orbit containing a fixed monomial aX

Proof. The number of monomials in the orbit containing a fixed monomial aX q i +1 is exactly the number of monomials linearly equivalent to aX q i +1 . If a monomial bX q s +q t is linearly equivalent to aX q i +1 , then there exists a L(X) such that bX q s +q t = aX q i +1 • L(X). From Lemma 12 and Lemma 13, it follows that L(X) = cX q k . Thus all monomials linearly equivalent to aX q i +1 come from aX q i +1 • cX q k . Let

Then S = k S k and the coefficients of monomials in S k are exactly a coset of R(X q i +1 ) in the group

. Now let us consider when S k1 = S k2 . It is east to see that the degrees of monomials in S k are all (q i+k + q k ) mod (q n -1), hence for 0 ≤ k 1 , k 2 ≤ n -1, if S k1 = S k2 , then q i+k1 + q k1 ≡ q i+k2 + q k2 mod (q n -1), i.e.

(I)

i

From (I), we get that k 1 = k 2 . From (II), we get that i = n 2 and k 1 ≡ n 2 + k 2 (modn). So it follows that:

Theorem 5. The number of orbits containing some monomial aX q u +q v (0

any monomial aX q u +q v is linearly equivalent to aX q u-v +1 . It is then sufficient to determine the number of orbits that contains some monomials of the form aX q k +1 . Let

Then M = n-1 k=1 M k . From Lemma 13, we have αX q i +1 and βX q i +1 are linearly equivalent iff α and β are in the same coset of R(X q i +1 ) in the group F * q n , therefore M k is distributed in |F * q n /R(X q k +1 )| different orbits. Since aX q k +1 • X q n-k = aX q n-k +1 , aX q k +1 and aX q n-k +1 are in the same orbit . Thus the orbits containing monomials in M k also contains monomials in M n-k , i.e. monomials in

For monomials of the form aX 2q i , we have: Theorem 6. When char(F q ) = 2, all monomials of the form aX 2q i are in one orbit, in which there are n(q n -1) monomials. When char(F q ) = 2, all monomials of the form aX 2q i are in two orbits, in each of them there are exact 1 2 n(q n -1) monomials.

Proof. From Lemma 12, we can deduce that two monomials αX 2q u and βX 2q v are in the same orbit if and only if α -1 β is a square element of F q n . When char(F q ) = 2, all elements of F * q n are square elements. Hence two arbitrary monomials αX 2q u and βX 2q v are in the same orbit since α -1 β is always a square element. And therefore there are n(q n -1) monomials of the form aX 2q i in the orbit. When char(F q ) = 2, there are exact 1 2 (q n -1) square elements and 1 2 (q n -1) non-square elements of F * q n . For two elements α and β, α -1 β is a square element if and only if both α and β are square elements or non-square elements simultaneously. Thus all monomials aX 2q i whose coefficients are square elements (resp. non-square elements) are in the same orbits. Then the conclusion follows immediately.

To summarize: Theorem 7. The number of orbits containing monomial points is:

Proof. The proof is obtained thanks to Theorem 5 and Theorem 6.

In the formulae of Theorem 7,

represents the number of orbits containing monomial of the form aX q u +q v (u = v). The rest part represents the number of orbits containing monomial of the form aX 2q i in function of the characteristic.


Alexandru Cornel Brezoescu

Tadeo Espinoza

Pedro Castillo
email: castillo@hds.utc.fr

Rogelio Lozano
email: rlozano@hds.utc.fr

Adaptive Trajectory Following for a Fixed-Wing UAV in Presence of Crosswind

Keywords: Adaptive control, Fixed-wing UAV, Lyapunov stability

établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Unmanned Aerial Vehicles (UAVs) represent an area of great interest in the automatic control community. The absence of the pilot renders them best suited to solve dangerous situations. However, it requires signicant attention in the ight control design since the vehicle may experience large parameter variations and external disturbances. The largest use of the UAVs is within military applications but they are also used in a growing number of civil applications such as reghting, digital mapping or monitoring. To increase the usefulness of UAVs, the capability of the autonomous controller to track a reference path is essential. Moreover, the robustness with respect to environmental disturbances must be considered. For example, small UAVs are signicantly sensitive to wind since its magnitude may be comparable to the UAVs speed.

A wide range of trajectory tracking controllers for autonomous vehicles could be found in literature. In [START_REF] Silvestre | On the design of gain-scheduled trajectory tracking controllers[END_REF], the authors addressed the problem of trajectory tracking as a gain scheduling control problem. The proposed methodology was illustrated for an autonomous underwater vehicle that was scheduled on yaw rate and path angle. A nonlinear design was obtained from the interpolation of six linear controllers computed for dierent values of the gain scheduling variables. The problem of external disturbances was not addressed in this paper.

In gain scheduling theory the system dynamics are considered slowly varying [2] [START_REF] Shamma | Guaranteed Properties of Gain Scheduled Control of Linear Parameter-Varying Plants[END_REF] which reduces the ight capabilities of an airplane. Trajectory linearization control (TLC) was used in [START_REF] Adami | 6DOF ight control of xed-wing aircraft by Trajectory Linearization[END_REF] to avoid the use of gain scheduling and to enable operation across the full ight-envelope for a 6DoF xed-wing aircraft model. The controller design combined dynamic inversion of the nonlinear equations of motion, to generate nominal force and torque commands, with a linear time varying tracking error regulator to account for model uncertainty. Simulations results were presented for a climbing, bank-to-turn maneuver.

A method based on the vector eld approach was proposed in [START_REF] Nelson | Vector eld path following for small unmanned air vehicles[END_REF] for the case where the time dimension of the reference trajectory is removed. Path following was achieved for straight-lines and circular arcs and orbits in the presence of constant wind disturbances. The algorithm was validated through simulations and real ight tests of a xed-wing miniature air vehicle.

When accurate knowledge of the vehicle dynamics is not available, adaptive control design can be employed in order to estimate the uncertain parameters. Many of the results in adaptive control are derived from Lyapunov stability theory [START_REF] Slotine | Applied Nonlinear Control[END_REF]- [START_REF] Krstic | Nonlinear and Adaptive Control Design[END_REF]. Several ight control algorithms which combines adaptation with other control tools, such as backstepping, neural networks or sliding mode control, can be found in the literature. For instance in [START_REF] Harkergard | Backstepping and Control Allocation with Applications to Flight Control[END_REF], ight control laws for two dierent control objectives were designed employing backstepping technique: maneuvering purpose and automatic control for the ight path angle. Also, two schemes based on adaptive backstepping and nonlinear observer design were proposed for estimating model errors. The proposed controllers were evaluated through simulations.

Likewise, a Lyapunov-based adaptive backstepping approach with online estimation of the uncertain aerodynamic forces and moments was used in [START_REF] Sonneveldt | Adaptive Backstepping Flight Control for Modern Fighter Aircraft[END_REF] to design a ight-path controller for a nonlinear high-delity F-16 model. It was shown that trajectory control can still be accomplished with these uncertainties while good tracking performance is maintained. On the other hand, in [START_REF] Gavilan | Control of the longitudinal ight dynamics of an UAV using adaptive backstepping[END_REF] the authors introduced the design of an adaptive backstepping controller for longitudinal ight-path control when the aerodynamic coecients are not known exactly. The system followed references in velocity and ight path angle and showed good performance in simulations.

Even if there are many adaptive approaches to ight control design, only few have been developed to realize airplane directional control in presence of unknown wind gusts. The goal of this work is to stabilize an airplane under crosswind and to realize the convergence to zero of the cross track error with respect to a desired trajectory. Moreover, the adaptive controller must be robust, by construction, with respect to external and unknown disturbances. We focus mainly in the lateral dynamic of the plane, for this, an analysis of this dynamic is presented in section 2. Likewise, in this section we introduce the airframe addressed in this paper, the cross track error and the dynamic velocity of the plane with respect to the desired path. An adaptive control strategy is developed and presented in section 3 in order to follow the trajectory in presence of wind. Besides, the stability properties of the controller are discussed at the end of this section. The validation of the proposed control scheme is done in simulations and the main results are depicted in graphs in section 4. Additionally, an embedded control system was developed to validate the control algorithm, the main characteristics of this hardware platform are described in section 5. And nally in section 6, the conclusion and future work are discussed.

Aircraft system

The dynamic characteristics of an airplane strongly depend on many parameters such as altitude, speed, conguration or environmental disturbances. As a result, its complete dynamic is nonlinear, uncertain and complex for control purposes. In this section we rst introduce the airframe employed, then the lateral dynamics of the airplane in a non-steady atmosphere is derived.

A robust airframe possessing reliable ight characteristics is essential for real ight tests. Long duration ight and sucient payload capacity to carry the weight of sensors and batteries are two features of great interest. Fig. 1 shows the commercially available Multiplex Twinstar II model used in our study. Its conguration is based on the classic aerodynamic layout and it is made of molded Elapor foam. Two brushless motors were mounted on the airfoil-shaped wings to power the airplane. A couple of ailerons, an elevator and a rudder are used as control surfaces and are actuated by servo motors. The technical characteristics of the Multiplex Twinstar II are given in Table 1. A payload of approximately 300 g, consisting of sensors and a central processing unit, was added to the airframe as the embedded electronics. The developed hardware platform is described in detail in section 5.

Airplane dynamics

The problem of trajectory following becomes complex when considering the complete dynamics of the airplane. In order to simplify the analysis and to better state the problem, let us explore only the airplane lateral motion and to consider that the path to be followed is a straight-line, as shown in Fig. 2. In addition, we assume that the airplane has a control system to hold the longitudinal variables stabilized to y in level ight. That implies constant velocity, small roll and pitch angles and zero ight path angle , γ, see [START_REF] Etkin | Dynamics of Atmospheric Flight[END_REF]. Consequently, the airplane velocity and the roll and pitch angles vary slowly compared to the other parameters and their time derivatives can be neglected in the ight dynamics. Under the above assumptions, the control problem to be solved simplies to producing the yawing moment required for an airplane to change its direction according to the desired trajectory. Two reference frames are used in order to derive the equations of motion: the Earth-xed frame, denoted by F E , and the body-xed frame represented by F B . F E and F B have two dimensions since only the lateral dynamics are considered in this study. The origin of F B coincides with the vehicle's center of mass and the direction of its axes is according to Fig. 2. F E is employed as an inertial frame and one of its axis is chosen northwards while the other points East.

In real conditions, the performance of an airplane is modied by environmental disturbances like wind. In such conditions it begins to sideslip or to be yawed out of its ight path. The classical relation of the aircraft velocity relative to the Earth is

V = V + W (1)
where V = [u v] T denotes the velocity of the aircraft relative to the local atmosphere and W represents the wind relative to F E . Besides, we only consider in this study the case of a crosswind which is dened as a lateral wind perpendicular to the vehicle but parallel to the ground, having North, W N , and East velocity components, W E .

Denote VB = u E v E T as the velocity of the aircraft relative to the Earth in the directions of the body frame axes. Thus, from (1) it follows

u E v E = u v + B B W N W E
where B B denes the complete transformation from F E to F B assuming constant pitch angle and it is given by

B B = c θ c ψ c θ s ψ s φ s θ c ψ -c φ s ψ s φ s θ s ψ + c φ c ψ
where s θ and c θ denote sin(θ) and cos(θ), respectively.

Then, the dierential equations for the coordinates of the ight path in

F E are ẋ ẏ = B T B VB or ẋ = u E c θ c ψ + v E s φ s θ c ψ -v E c φ s ψ ẏ = u E c θ s ψ + v E s φ s θ s ψ + v E c φ c ψ with u E = u + W N c θ c ψ + W E c θ s ψ v E = v + W N s φ s θ c ψ -W N c φ s ψ + W E s φ s θ s ψ + W E c φ c ψ
where x and y represent the inertial position in the x-axis (North) and in the y-axis (East). Remember that the pitch and roll angles are small so that sin{θ, φ} ≈ 0 and cos{θ, φ} ≈ 1. Moreover, considering a symmetrical airplane with a rigid spinning rotor placed in the front of its body, it can then be considered, without loss of generality, V acting only in the x-axis, see Fig. 2. Hence, the following expression can be stated

v << 1 u ≈ V and consequently ẋ = V cos ψ + ω cos ψ ω ẏ = V sin ψ + ω sin ψ ω
where ω cos ψ ω = W N , ω sin ψ ω = W E , ω is the wind velocity and ψ ω describes the wind direction. The motion of the airplane with respect to a stationary desired straight-line path of angle ψ d can then be expressed as

ẋ = V cos (ψ -ψ d ) + ω cos (ψ ω -ψ d ) ẏ = V sin (ψ -ψ d ) + ω sin (ψ ω -ψ d )
Notice that the above equations are relatively proportional to the variation of the yaw angle. Considering that the motors of the airplane produce the same amount of thrust, then the yaw angular acceleration can be controlled using the rudder deection. The dierential equations describing this dynamics are

ψ ≈ r ṙ ≈ cτ ψ
where r stands for yaw rate, τ ψ represents the yawing moment and c is a constant related to the aircraft moment of inertia.

Fig. 3 shows an analysis of the nonlinear model of the airplane when it ies in stable or moving atmosphere. The desired trajectory is plotted in thick dashed line while the solid path describes the real airplane trajectory. The crosswind has North and East velocity components of W N = -3 m/s and W E = 5 m/s, respectively. The airplane velocity relative to the surrounding air mass is 20 m/s. Fig. 3 Earth-Relative Aircraft Location. First, the plane ies in stable atmosphere and it is capable to follow the desired path. When the atmosphere moves relative to the Earth, the airplane diverge from the path.

Control design

The main control objective is to obtain directional control in order to follow a desired trajectory even in presence of unknown crosswind. To simplify the analysis, let assume that the desired trajectory is aligned with the North axis of the reference frame, then, the desired path angle, ψ d , is equal to zero. Therefore, the amount of the trajectory deviation will depend on the velocity of the airplane and wind and also on the angle of the wind in relation to the airplane. In addition we consider, for control design, that the wind velocity changes slowly such that it can be considered quasi-constant. However, it will be proved in simulations that the closed-loop system remains stable even with no constant wind.

Thus, without loss of generality, the airplane dynamics for trajectory following purpose can be dened as

ḋ ≡ ẏ = V sin ψ + k ω (2) ψ = r (3) ṙ = cτ ψ (4)
where k ω = ω sin(ψ ω ) is considered, for control design, quasi-constant and it is due to the wind perturbation, and d represents the cross track error from the desired trajectory.

To stabilize the system (2)-( 4), the control law will be constructed using the adaptive backstepping approach. Dene the following error variable

e 1 = d -d min (5)
where d min is the minimum constant distance from the desired trajectory. Thus,

ė1 = V sin ψ + k ω (6)

Convergence of e 1 to zero

Propose the following positive function

V L 1 = 1 2 e 2 1
thus

VL 1 = e 1 (V sin ψ + k ω )
To stabilize e 1 we introduce ψ v as a virtual control in the following form

V sin ψ v = -c 1 e 1 -kω 1
where kω 1 is the estimate of k ω and c 1 > 0 is a constant. Evaluating VL 1 when ψ → ψ v it follows that

VL 1 | ψ=ψ v = -c 1 e 2 1 + e 1 kω 1
where

kω 1 = k ω -kω 1 . Notice from the above equation that if kω 1 → k ω then VL 1 ≤ 0. Thus, rewriting V L 1 , it yields V L 1 = 1 2 e 2 1 + 1 γ 1 k2 ω 1
where γ 1 > 0 denotes a constant adaptation gain. Then

VL 1 | ψ=ψ v = -c 1 e 2 1 + e 1 - kω 1 γ 1 kω 1
Choosing the update law as

kω 1 = γ 1 e 1 (7)
It follows that

VL 1 | ψ=ψ v = -c 1 e 2 1 3.2 Convergence of ψ to ψ v
Dene the error

e 2 = V sin ψ -V sin ψ v = V sin ψ + c 1 e 1 + kω 1 (8)
and rewrite [START_REF] Slotine | Applied Nonlinear Control[END_REF] in terms of e 1 and e 2 ė1 = e 2c 1 e 1 + kω 1

This implies that

ė2 = V r cos ψ + γ 1 -c 2 1 e 1 + c 1 e 2 + c 1 kω 1 (10)
Notice that cos ψ = 1 -(sin ψ) 2 . From ( 8)

sin ψ = e 2 -c 1 e 1 -kω 1 V
and assuming thatπ 2 < ψ < π 2 it follows that (10) becomes

ė2 = rR + γ 1 -c 2 1 e 1 + c 1 e 2 + c 1 kω 1 (11)
with R = V 2 -e 2 -c 1 e 1 -kω 1

2

.

Introduce the following positive function

V L 2 = V L 1 + 1 2 e 2 2 = 1 2 e 2 1 + 1 γ 1 k2 ω 1 + e 2 2
From ( 7), ( 9) and ( 11) the derivative reads

VL 2 = -c 1 e 2 1 + e 2 c 1 e 2 + e 1 (γ 1 + 1 -c 2 1 ) + c 1 kω 1 + rR
By selecting the virtual control as

r v R = -e 2 (c 1 + c 2 ) -e 1 (γ 1 + 1 -c 2 1 ) -c 1 ( kω 2 + kω 1 ) VL 2 becomes when r → r v VL 2 | r=r v = -c 1 e 2 1 -
V L 2 = V L 1 + 1 2 e 2 2 + 1 γ 2 k2 ω 2
with γ 2 > 0 and constant. Hence VL 2 becomes

VL 2 | r=r v = c 1 e 2 1 -c 2 e 2 2 + kω 2 c 1 e 2 - kω 2 γ 2
Proposing the update law

kω 2 = γ 2 c 1 e 2
then, it follows

VL 2 | r=r v = c 1 e 2 1 -c 2 e 2 2

Convergence of r to r v

Let us dene the third error variable

e 3 = rR -r v R = rR + L 2 e 2 + L 1 e 1 + c 1 ( kω 2 -kω 1 ) (12)
where

L 1 = 1 -c 2 1 + γ 1 , L 2 = c 1 + c 2 .
Rewriting the error system representation, we obtain

ė1 ė2 = -c 1 1 -1 -c 2 e 1 e 2 + kω 1 e 3 + c 1 kω 2
thus, the derivative of e 3 yields

ė3 =cτ ψ R - r(e 2 -c 1 e 1 -kω 1 )(e 3 -L 2 e 2 -L 1 e 1 + c 1 kω 1 -c 1 kω 2 ) R + L 2 e 3 + L 3 e 2 + L 4 e 1 + c 1 L 2 kω 2 + L 1 kω 1 with L 3 = -c 1 c 2 -c 2 1 -c 2 2 + 1 + γ 1 + c 2 1 γ 2 and L 4 = -2c 1 -c 2 + c 3 1 -2c 1 γ 1 .
Finally, introduce the following Lyapunov function

V L = 1 2 e 2 1 + 1 γ 1 k2 ω 1 + e 2 2 + 1 γ 2 k2 ω 2 + e 2 3 then VL = -c 1 e 2 1 -c 2 e 2 2 + e 3 ( ė3 + e 2 ) (13)
Propose the control input as

cτ ψ = - e 3 (L 2 + c 3 ) + e 2 (L 3 + 1 -r 2 ) + e 1 (L 4 + c 1 r 2 ) R - kω 3 (L 1 + c 1 L 2 ) -kω 2 c 1 L 2 -kω 1 (L 1 -r 2 )

R

where kω 3 = k ω -kω 3 and c 3 is a positive constant gain. Notice that the unknown term k ω appears again in VL , thus we propose a correction factor in order to realize the convergence of the states.

Introducing the above into (13), we have

VL = -c 1 e 2 1 -c 2 e 2 2 -c 3 e 2 3 + e 3 (L 1 + c 1 L 2 ) kω 3 Observe that VL ≤ 0 if kω 3 → k ω . Therefore augmenting V L , it yields V L = 1 2 e 2 1 + 1 γ 1 k2 ω 1 + e 2 2 + 1 γ 2 k2 ω 2 + e 2 3 + 1 γ 3 k2 ω 3 and VL = -c 1 e 2 1 -c 2 e 2 2 -c 3 e 2 3 + kω 3 e 3 (L 1 + c 1 L 2 ) - kω 3 γ 3 Choosing kω 3 = γ 3 (L 1 + c 1 L 2 )e 3 VL becomes VL = -c 1 e 2 1 -c 2 e 2 2 -c 3 e 2 3 ( 14
)
The error representation of the closed-loop adaptive system is summarized below

  ė1 ė2 ė3   =   -c 1 1 0 -1 -c 2 1 0 -1 -c 3     e 1 e 2 e 3   +   kω 1 c 1 kω 2 L 5 kω 3       kω 1 kω 2 kω 3     =   γ 1 0 0 0 c 1 γ 2 0 0 0 L 5 γ 3     e 1 e 2 e 3   (15) where L 5 = c 1 c 2 + γ 1 + 1.
Rewriting the control input cτ ψ in terms of d, ψ, r we have

cτ ψ = tan ψ(r 2 -L 6 ) -L 7 r - L 8 d + L 9 kω 1 + L 10 kω 2 + L 11 kω 3 V cos ψ (16)
with the updated parameters

kω 1 = γ 1 d kω 2 = γ 2 c 1 V sin ψ + c 1 d + kω 1 kω 3 = γ 3 L 11 V [r cos ψ + L 2 sin ψ] + γ 3 L 11 dL 11 + c 1 kω 2 + c 2 kω 1
where

L 6 = 1 + L 2 c 3 + L 2 2 + L 3 L 7 = L 2 + c 3 L 8 = L 7 (L 1 + c 1 L 2 ) + c 1 (L 3 + 1) + L 4 L 9 = 1 -c 1 L 7 + L 3 -L 1 + L 2 L 7 L 10 = c 1 L 7 -c 1 L 2 L 11 = L 1 + c 1 L 2
Notice from ( 14) that VL ≤ 0 and it estates the global stability of the equilibrium (e i , kω i ) =(0, 0). From the LaSalle-Yoshizawa theorem, we have that e i and kω i ; i = 1, 2, 3; are bounded and go to zero as t → ∞. From ( 5) it follows that d → d min . [START_REF] Kokotovic | The joy of Feedback : Nonlinear and Adaptive[END_REF] implies that kω 1 is also bounded and

lim t→∞ ψ = arcsin - kω 1 V ( 17
)
Observe that from (12) r is bounded and r → 0. On the other hand, from (16) it follows that cτ ψ is bounded.

LaSalle's invariance principle assures that the state (e i , kω i ) converges to the largest invariant set M contained in {(e 1 , e 2 , e 3 , kω 1 , kω 2 , kω 3 ) ∈ R 6 | VL = 0}. On this invariant set, we have e i ≡ 0 and ėi ≡ 0. From (15) it yields kω i = 0 and kω i = 0. Thus, the largest invariant set M is

M ={(e i , kω i ) ∈ R 6 |e i = 0, kω i = 0} ={(d, ψ, r, kω 1 , kω 2 , kω 3 ) ∈ R 6 |(d, ψ, r, kω 1 , kω 2 , kω 3 ) = (0, arcsin(- kω 1 V ), 0, k ω , k ω , k ω )}
The manifold M is the single point d = 0, ψ = arcsin(-kω 1 V ), r = 0, kω i = k ω for i = 1, 2 and 3, which is globally asymptotically stable.

Simulation results

The proposed control strategy was validated in closed-loop system in simulations with various wind conditions. Remember that we have considered the desired trajectory aligned with the North axis of the inertial frame which makes the desired path angle ψ d = 0 • . In addition, the airplane is ying with a constant speed equal to 20 m/s and the crosswind has a direction West-East perpendicular to the desired path. For a smoother convergence we have used the following parameters in simulations:

c 1 = c 3 = 1.5; c 2 = 1.3; γ 1 = 1; γ 2 = 1.1; γ 3 = 1.4.

Case constant wind

Several simulations were performed to validate the controller and representative results are presented. The rst simulations were carried out with a constant wind velocity of 7 m/s. The initial conditions are: d = 2 m, ψ = -10 • and r = 0 rad/s. For comparative control purpose, a standard nonlinear backstepping algorithm was developed (see Appendix A) to control the system (2)-( 4) and it is given by

cτ ψ b = -3r + tan ψ(r 2 -5) - 3d + 5k ω V cos ψ (18)
In Fig. 4 we show the time evolution of the aircraft deviation from the desired trajectory for constant wind when employing the controllers ( 16) and ( 18). The wind parameter, denoted by k ω , is not known and therefore considered zero in (18). Notice from this gure that the controller proposed in ( 16) is able to provide cross track error regulation due to the adaptation laws presented in (15). For this case, the closed-loop adaptive system shows good response even in presence of unknown disturbance. Fig. 5 reveals the fact that to maintain alignment with the desired trajectory during a crosswind ight requires the controller to y the airplane at a sideslip angle. Indeed, when the position error converges to zero, the yaw angle is stabilized around a constant value and the airplane keeps moving toward North. Notice that the yaw angle is nonzero unless the atmosphere is at rest.

On the other hand, the proposed adaptation scheme guarantees the convergence of the unknown parameter estimates towards its true constant value, see Fig. 6. The Lyapunov function, plotted in Fig. 7, is semi-positive denite and continually decreasing which proves the stability properties of the system. Indeed, in Fig. 8 we illustrate the control input response. In order to demonstrate the robustness (in simulation) of the proposed control algorithm, some variations are included in the wind parameters and noise is considered in sensor measurements. For this purpose, we assume that the wind varies in magnitude and orientation, as shown in Fig. 9. Notice in this gure that, at time 20s, a sudden increase of 2 m/s is presented in speed of the wind.

The airspeed, the distance relative to the path, the yaw angle and the yaw rate are computed by sensors placed onboard whose measurements are aected by random variations. To approximate as much as possible a real life scenario, let us evaluate the controller in presence of normal gaussian noise. To this end, the outputs of the airspeed and distance sensors are perturbed by the noise represented in Fig. 10 The overall system has been simulated for the case when the path to be followed is a four straight-line segments combination. The rst segment is aligned with the reference while the angles of the three following segments are 55 • , 110 • and 160 • relative to the North axis, see Fig. 11. Initial deviation of the airplane from the path is -15 m while its initial orientation is considered as for the previous simulations.

The main results are displayed in Figures 1112131415. Observe that path following is achieved even in presence of sudden changes in path direction, variations in wind parameters and sensor noise. The wind deviates the airplane from the reference trajectory toward the wind direction but the controller ( 16) is able to recover the aircraft and to converge the position error to zero, see Fig. When aligned with the reference trajectory, the airplane is own at a sideslip angle to maintain directional control, see Fig. 13. The adaptation laws are used to estimate the value of k ω = ω sin(ψ ωψ d ), which varies mainly according to ψ d as shown in Fig. 14. Notice from this gure that the convergence time is relatively small and that the estimated unknown parameters are in agreement with the real value. The control eort is illustrated in Fig. 15. In this section we introduce an overview of the onboard hardware developed in order to carry out ight tests. The airplane used is the Multiplex TwinStar II. The central processing unit, represented by the RabbitCore RCM4300 Microprocessor, collects the measurements of the IMU (Inertial Measurement Unit employed to estimate the airplane attitude and angular rates), of the airspeed sensor and of the GPS system, to compute the control law. The control responses are sent to the servo signal generator/receiver unit and also to the two electric speed controllers to activate the brushless motors. Indeed, a modem is added to send and receive data from a base station. The electronic scheme is presented in Fig.

CONCLUSIONS AND FUTURE WORK

An adaptive control algorithm based on the backstepping approach has been proposed in this paper. The control strategy was focused on reducing the position deviation of the airplane with respect to a desired path in the lateral dynamics in presence of unknown wind. The control scheme was derived considering adaptation laws to estimate the unknown wind parameters. The closed-loop system was evaluated in several simulations and the main results, showing the good performance, were introduced by some graphs. An embedded control system was developed in order to validate the control strategy in ight tests. Future work will include real time implementation of the ight controller using the developed hardware platform.

A Standard nonlinear backstepping design

Let us rewrite the nonlinear system described by ( 2)-( 4)

ḋ = V sin ψ + kω ψ = r ṙ = cτ ψ
where kω is a constant perturbation due to the wind. We intend to achieve regulation of d(t) designing backstepping control, for this purpose we dene the following error variable The e 1 term can be stabilized if we introduce ψ v as virtual control in the form

V sin ψ v = -e 1 -kω
Evaluating VL 1 when ψ → ψ v it follows that

VL 1 | ψ=ψ v = -e 2 1
Since ψ is not the real control, let us dene the deviation from its desired value Using the virtual control r v in the form

r v R = -2e 2

Fig. 1

 1 Fig. 1 Airplane model

Fig. 2

 2 Fig. 2 Problem formulation for path following

Fig. 4

 4 Fig. 4 Position error for unknown wind. Solid line represents the proposed controller (16) whilst dashed line the standard backstepping control algorithm (18).

Fig. 5 Fig. 6

 56 Fig. 5 Yaw angle for kω = 7 m/s

Fig. 7 Fig. 8

 78 Fig. 7 Lyapunov function for kω = 7 m/s

  (a) while the outputs of the yaw angle yaw rate sensors by the noise represented in Fig. 10(b).

Fig. 9

 9 Fig. 9 Variable wind gust

Fig. 10

 10 Fig. 10 Normal Gaussian noise

12

 12

  .

Fig. 11

 11 Fig. 11 The path to be followed consists of a combination of four straight-line segments.

Fig. 12

 12 Fig. 12 Position error for variable wind and sensor noise

Fig. 13 Fig. 15

 1315 Fig. 13 Yaw angle for variable wind and sensor noise

  17

  .

Fig. 16

 16 Fig. 16 The onboard electronics

Fig. 17

 17 Fig.17The electronic scheme

  Fig.17The electronic scheme

e 1 = 1 = 1 2 e 2 1 thusVL 1 =

 1111 dd min where d min is the minimum constant distance from the desired trajectory. The dynamics of e 1 yields ė1 = V sin ψ + kω (19) Let us consider the following positive function V L e 1 (V sin ψ + kω)

e 2 = 2 ė1 = e 2 -e 1 ( 21 )V L 2 VL 2 = -e 2 1 +

 22121221 V sin ψ -V sin ψ v = V sin ψ + e 1 + kω(20) and rewrite (19) in terms of e 1 and e This implies that ė2 = V r cos ψ + e 2e 1 (22) Notice that cos ψ = 1 -(sin ψ) 2 . From (20) sin ψ = e 2e 1kω V and assuming thatπ 2 < ψ < π 2 it follows that (22) becomes ė2 = rR + e 2e 1 (23) with R = V 2 -(e 2 -e 1 -kω) 2 . Let us consider the positive denite function e 2 (e 2 + rR)

Table 1

 1 Parameters of the airplane.

	Parameter	Value
	Wingspan	1420 mm / 55.9 in
	Fuselage length	1085 mm / 42.7 in
	Wing area	43 dm 2 / 666.5 inch 2
	Weight approx.	1340 g / 47.3 oz
	Wing loading	31.2 g/dm 2 / 10.3 oz/sq.ft
	RC functions	Aileron, elevator, rudder, throttle

  c 2 e 2 2 + c 1 e 2 kω 2 where kω 2 = k ω -kω 2 , kω 2 represents a new estimate for k ω and c 2 denotes a positive constant gain. Notice that if we had employed the existing estimate kω 1 , we would have had no design freedom left to cancel the unknown parameter from VL 2 . Additionally, kω 2 could be seen as a factor correction for kω 1 . Notice from the above equation that if kω 2 → k ω then VL 2 ≤ 0. Thus, rewriting V L 2 , it yields

Let e 3 be the deviation of r from its desired value

This implies

It is more convenient to write the error system representation

Using ( 24), the control law takes the form

Thus, (28) becomes

which proves that in the (d, e 1 , e 2 ) coordinates the equilibrium (0, 0, 0) is GAS. In view of (d, ψ, r), the resulting control is cτ ψ = -3r + tan ψ(r 2 -5) -3d + 5kω

V cos ψ (32)