Sankhanil Dey
email: sankhanil12009@gmail.com

Ranjan Ghosh
email: rghosh47@yahoo.co.in

A New Algorithm to Search for Irreducible Polynomials Using Decimal Equivalents of Polynomials over Galois Field GF(p q )

In this paper a new algorithm to find the decimal equivalents of all monic irreducible polynomials (IPs) over Galois Field GF(p q ) has been introduced. This algorithm is effective to find the decimal equivalents of monic IPs over Galois Field with a large value of prime modulus and also with a large extension of the prime modulus. The algorithm introduced in this paper is much more time effective with less complexity. It is able to find monic irreducible polynomials for a large value of prime modulus and also with large extension of the prime modulus in few seconds.

Introduction.

. The use of basic arithmetic operations (i.e. addition, multiplication, and inversion) over finite fields, GF(p q ), where p is prime modulus and q is extension of the prime modulii, are dominant in many

cryptographic algorithms such as RSA algorithm [START_REF] Abdulah | Division and Inversion Over Finite Fields, Cryptography and Security in Computing[END_REF], Diffie-Hellman key exchange algorithm [START_REF] Diffie | New directions in cryptography[END_REF], the US federal Digital Signature Standard [START_REF]Digital signature standard (DSS)[END_REF], elliptic curve cryptography [START_REF] Miller | Use of elliptic curves in cryptography[END_REF] [START_REF] Koblitz | Elliptic curve cryptosystems[END_REF], and also recently pairing-based cryptography [START_REF] Boneh | Identity-based encryption from the Weil pairing[END_REF] [START_REF] Shamir | Identity-based cryptosystems and signature schemes[END_REF]. Due to elliptic curve based schemes, most efficient finite fields that are commonly used in cryptographic applications are prime fields GF(p) and binary extension fields GF (2 n ). The standard 8-bit S-Box of Advance Encryption Standard is usually generated by using a monic irreducible polynomial {11B} as the modulus in extended binary Galois Field GF (2 8 ) and a particular additive constant {63} in Binary Galois Field GF [START_REF] Lidl | Finite Fields[END_REF]. Rijndael used this particular modulus and the additive constant in the original proposal of Advance Encryption Standard . It has also been discovered that the other moduli and constants can also be used to make the generation of 8-bit S-Boxes more dynamic [START_REF] Daemen | Rijndael, Version 2[END_REF][11] [START_REF]PUB 197: the Official AES Standard[END_REF]. Recently, pairing-based cryptography based on bilinear pairings over elliptic curve points stimulated a significant level of interest in the arithmetic of ternary extension fields GF(3 n ) [START_REF] Kim | Subset Restricted Random Walks for Pollard Rho Method on F p m[END_REF].

Polynomials over finite fields have been studied since the time of Gauss and Galois [START_REF] Dörrie | Great Problems of Elementary Mathematics: Their History and Solutions[END_REF] [START_REF]Galois Theory[END_REF]. The determination of special types of polynomials such as irreducible, primitive, and permutation polynomials, is a long standing and well studied problem in the theory and application of finite fields [START_REF] Zaman | Multiplicative Polynomial Inverse over GF(73): Crisis of EEA and its Solution[END_REF] [START_REF] Zaman | An Algorithm to find the Irreducible Polynomials over Galois Field GF(pm)[END_REF] [START_REF] Mitra | On the Construction of m-Sequences via Primitive Polynomials with a Fast Identification Method[END_REF] [START_REF] Zieve | On Some Permutation Polynomials Over Fq Of The Form X r h(X (Q-1)/D )[END_REF]. On the other hand, in recent years there has been intensive use of special polynomials in many areas including algebraic coding theory for the error-free transmission of information [START_REF] Siddesh | Error Free Transport of Transmitter Payload over Ad Hoc Wireless Network Using Osculating Polynomial Cross Products[END_REF], cryptography for the secure transmission of information [10][11] [START_REF]PUB 197: the Official AES Standard[END_REF], and polynomials over finite fields appear very naturally in several areas of combinatorics. First, due to the finite number of elements, the enumeration of various special kinds of polynomials over finite fields is an interesting and extremely important research area in combinatorics, especially in design theory, polynomials are used to construct and describe cyclic difference sets and special types of designs such as group divisible designs [START_REF] Hurd | Group Divisible Designs With Two Groups and Block Size Five With Fixed Block Configuration Spencer[END_REF]. Divisibility conditions on trinomials over finite fields have been shown to produce orthogonal arrays with certain strengths [START_REF] Panario | Divisibility of Polynomials over Finite Fields and Combinatorial Applications[END_REF], and bivariate and multivariate polynomials can be used to represent and study latin squares and sets of orthogonal latin squares and hypercubes of prime power orders [START_REF] Ballif | Mutually Orthogonal Latin Squares[END_REF] [START_REF] John | Strong Forms of Orthogonality for Sts of Hypercube[END_REF]. Polynomials over finite fields are the key ingredient in the construction of error-correcting codes such as BCH [START_REF] Peterson | Error-Correcting Codes[END_REF], Goppa [START_REF] Peterson | Error-Correcting Codes[END_REF], Reed-Solomon [START_REF] Peterson | Error-Correcting Codes[END_REF], and Reed-Muller codes [START_REF] Peterson | Error-Correcting Codes[END_REF], among others. Moreover, polynomials also play a key role in other areas of coding theory such as the determination of weight enumerators [START_REF] Alexander | On Some Polynomials Related To Weight Enumerators of Linear Codes[END_REF], the study of distance distributions [START_REF] Gil | On the Distance Distribution of Codes[END_REF], and decoding algorithms [START_REF] Lin | Novel Polynomial Basis and Its Application to Reed-Solomon Erasure Codes[END_REF]. Large extensions of finite fields (especially over the two-element field) are important in cryptography . Elements in these extension fields can be represented by polynomials over the prime subfield [START_REF]A Brief Introduction to Modern Cryptography[END_REF]. Thus, constructions of extension fields and fast arithmetic of polynomials are important practical questions . In addition, polynomials over finite fields are important in engineering applications. Linear recurrence relations over finite fields produce sequences of field elements [START_REF] Hanif | Least Period of Linear Recurring Sequences over a Finite Field[END_REF]. Linear feedback shift registers are used to implement these recurrences. Characteristic polynomials over finite fields are one of the main tools when dealing with shift registers [START_REF] Li Yujuan | On the Primitivity of some Trinomials over Finite Fields[END_REF]. In particular, primitive characteristic polynomials produce sequences with large periods, and thus have found many applications in areas such as random number generation [START_REF] Wang | On The Use Of Reducible Polynomials As Random Number Generators[END_REF].

In past decades many results towards the enumeration of classes of univariate irreducible polynomials over finite field or Galois Field with certain characteristics have appeared in the literature. Such polynomials are used to implement arithmetic in extension fields found in many applications, including coding theory [33][34], cryptography [START_REF] Chor | A knapsack type public key cryptosystem based on arithmetic in finite fields[END_REF] [START_REF] Das | Generation of AES S-Boxes with various modulus and additive constant polynomials and testing their randomization[END_REF], multivariate polynomial factoring [START_REF] Kaltofen | Factorization of multivariate polynomials over finite fields[END_REF] parallel polynomial arithmetic [START_REF] Eberly | Very fast parallel matrix and polynomial arithmetic[END_REF]. Many algorithms had also been introduced along with to determine irreducible polynomials over finite fields, including a composite polynomial method to find monic irreducible polynomials by a hand on calculation over Galois field with prime modulus 2 to 7 with for extensions 1 to 11 [START_REF] Church | Tables of Irreducible Polynomials for the first four Prime Moduli[END_REF], Rabin's algorithm to find monic irreducible polynomials over Galois Field GF(p) where p is a prime integer, An improvement of Rabin's algorithm with less complexity [START_REF] Jacques | An Improvement of Rabin's Probabilistic Algorithm For Generating Irreducible Polynomials Over Gf(P)[END_REF], an algorithm that constructs a degree d irreducible polynomial over finite fields proved that under the generalized Riemann hypothesis by Adleman and Lenstra [START_REF] Adleman | Finding irreducible polynomials over finite fields[END_REF], a deterministic algorithm that runs in polynomial time for fields of small characteristic [START_REF] Shoup | New algorithms for finding irreducible polynomials in finite fields[END_REF], and recently a method that uses the concept of p-nary equivalent of multiplicative inverses of the elemental polynomials (ep) of a basic monic irreducible polynomial to determine a basic monic polynomial to be irreducible [START_REF] Zaman | An Algorithm to find the Irreducible Polynomials over Galois Field GF(p m )[END_REF].

A basic polynomial BP(x) over finite field or Galois Field GF(p q ) is expressed as, BP(x) = a q x q + a q-1 x q-1 + ---+ a 1 x + a 0.

B(x) has (q+1) terms, where a q is non-zero and is termed as the leading coefficient [START_REF] Canright | A very Compact S-box for AES[END_REF]. A polynomial is monic if a q is unity, else it is non-monic. The GF(p q ) have (p qp) elemental polynomials ep(x) ranging from p to (p q -1) each of whose representation involves q terms with leading coefficient a q-1 . The expression of ep(x) is written as, ep(x) = a q-1 x q-1 + ---+ a 1 x + a 0 , where a 1 to a q-1 are not simultaneously zero.

Many of BP(x), which has an elemental polynomial as a factor under GF(p q ), are termed as reducible. Those of the BP(x) that have no factors are termed as irreducible polynomials IP(x) [START_REF] Lidl | Finite Fields[END_REF][46] and is expressed as, IP(x) = a q x q + a q-1 x q-1 + ---+ a 1 x + a 0 , where a q ≠ 0.

In Galois field GF(p q ), the decimal equivalents of the basic polynomials of extension q vary from p q to (p q+1 -1) while the elemental polynomials are those with decimal equivalents varying from p to (p q -1). Some of the monic basic polynomials are irreducible, since it has no monic elemental polynomials as a factor.

In this paper a new algorithm to determine the decimal equivalents of monic irreducible polynomials over extended Galois fields, also for large value of prime modulus and its large extensions is demonstrated with example. In this algorithm the decimal equivalents of each of two monic elemental polynomials at a time with highest degree d and (q-d) where d = 0 to (q-1)/2, are split into the p-nary coefficients of each term of those two monic elemental polynomials. The coefficients of each term in each two monic elemental polynomials are multiplied, added with each other and modulated to obtain the p-nary coefficients of each term of the monic basic polynomial. The decimal equivalent of the resultant monic basic polynomial is termed as the decimal equivalent of a reducible monic basic polynomial. The decimal equivalents of polynomials belonging to the list of reducible polynomials are cancelled leaving behind the monic irreducible polynomials.

For convenient understanding, the proposed algorithm is presented in Sec.2 for Galois Field GF(p q ) and for clarity of understanding the algorithm is described with example of Galois Field GF(7 7 ), where p=7 and q=7 has also been demonstrated in the same section . The method is able to find all monic irreducible polynomials IP(x) over any Galois Field GF(p q ), also for large value of prime modulus and its large extension. Sec. 3 demonstrates the obtained results to show that the proposed searching algorithm is actually able to search over any Galois field GF(p q ) with any value of prime modulus and its extension, such as, p €{ 3, 5, 7,....,101,..,p} and q € { 2, 3, 5, 7,…,101,….q}. In Sec.4 and 5, the conclusion of the paper and the references are illustrated. A list of decimal equivalents of all the monic irreducible polynomials over Galois Field GF (7 5 ) is given in Appendix-1. Initial part of the list of decimal equivalents of all the monic irreducible polynomials over Galois Field GF(101 3 ) is given in Appendix-2.

Algorithm to find Decimal Equivalents of Irreducible Polynomials over Galois Field GF(p q

). In this section the new algorithm to search for Decimal equivalents of all monic Irreducible polynomials over Galois Field GF(p q ) has been described with example. The detailed structural description of the algorithm is given in sub sec.2.1. The detailed mathematical description of the algorithm is given in sub sec.2.2. The Computational Algorithm is demonstrated in sec.2.3.The example of the said algorithm for Galois Field GF(7 7 ) is given in sub sec 2.4. The analysis of time complexity is illustrated in sub sec.2.5.

Structural Description of the Algorithm.

In this algorithm the decimal equivalents of each of two monic elemental polynomials at a time with highest degree d and (q-d) where d € {0,..,(q-1)/2}, are split into the p-nary coefficients of each term of those two monic elemental polynomials. The coefficients of each term in each two monic elemental polynomials are multiplied, added respectively with each other and modulated to obtain the p-nary coefficients of each term of the monic basic polynomial. The decimal equivalent of the resultant monic basic polynomial is termed as the decimal equivalent of a reducible monic basic polynomial. The decimal equivalents of polynomials belonging to the list of reducible polynomials are cancelled leaving behind the monic irreducible polynomials. For Galois Field GF(p q ), where p is prime modulus and q is the extension of the field, the algorithm is given as follows,

Step 1. Generate Decimal Equivalents of all Monic Elemental Polynomials dec(ep(x)) over Galois Field GF(p q ).

Step 2. Split dec(ep(x 1 )), dec(ep(x 2 )) with highest degree d and (q-d) respectively where d = 1 to ((q-1)/2), are split into p-nary coefficients of each term of each monic elemental polynomial ep(x).

Step 3. Multiply and add terms with degree d to 0 and (q-d) to 0 to obtain the decimal coefficients of each term of the Basic Polynomial BP(x).

Step 4. Split coefficient of each term of BP(x) into p-nary coefficients.

Step 5. Obtain the decimal equivalent of the Basic Polynomial BP(x) or dec(BP(x)) as Decimal equivalent of Reducible Polynomial.

Step 6. The decimal equivalents of polynomials belonging to the list of monic reducible polynomials are cancelled leaving behind the monic irreducible polynomials.

Step 7. Stop.

Mathematical Structure of the Algorithm.

Here the interest is to find the monic irreducible polynomials over Galois Field GF(p q ), where p is the prime modulus and q is the extension of the prime modulus and p must be a prime integer. Since the indices of multiplicand and multiplier are added to obtain the product. The extension q can be demonstrated as a sum of two integers, d 1 and d 2 , The degree of highest degree term present in elemental polynomials of GF(p q ) is (q-1) to 1, since the polynomials with highest degree of term 0, are constant polynomials and they do not play any significant role here, so they are neglected. Hence the two set of monic elemental polynomials for which the multiplication is a monic basic polynomial, have the degree of highest degree terms d 1 , d 2 where, d 1 € {1,2,3,..,((q-1)/2)}, and the corresponding values of d 2 € {(q-1), (q-2), (q-3).,...,q-((q-1)/2)}. Number of coefficients in the monic basic polynomial BP(x) = (q+1); they are defined as BP 0, BP 1, BP 2, BP 3, BP 4, BP 5, BP 6, BP 7…….., BP q, the value of the suffix also indicates the degree of the term of the monic basic polynomial. For monic polynomials BP q = 1.

Coefficients of each term in the 1 st monic elemental polynomial EP 0 , where, d 1 € {1,2,…..,((q-1)/2)}; are defined as EP 0 0 , EP 1 0 ,……., EP ((q-1)/2-1) 0 . Coefficients of each term in the 2 nd monic elemental polynomial EP 1 where d 2 € {(q-1), (q-2), (q-3).,...,q-((q-1)/2-1)}; are defined as EP 0

1 , EP 1 1 , EP 2 1 , EP 3 1 , EP 4 1 , … , EP q-((q-1)/2-1) 1 .
The value in suffix also gives the degree of the term of the monic elemental polynomials. Total number of blocks is the number of integers in d 1 or d 2, i.e. (q-1)/2 . Now, the Mathematical Structure of (q-1)/2 th block for the algorithm is as follows, (q-1)/2 th block: BP 0 = (EP 0 0 × EP 0 1 ) mod p.

BP 1 = (EP 0 0 × EP 1 1 + EP 1 0 × EP 0 1 ) mod p. BP 2 = (EP 0 0 × EP 2 1 + EP 1 0 × EP 1 1 + EP 2 0 × EP 0 1 ) mod p. BP 3 = (EP 0 0 × EP 3 1 + EP 1 0 × EP 2 1 + EP 2 0 × EP 1 1 + EP 3 0 × EP 0 1
) mod p. ………………………………………………………………… ………………………………………………………………… BP q-1 = (EP 0 0 × EP (q-1) 1 + EP 1 0 * EP (q-2) 1 +………….+ EP (q/2-1) 0 * EP (q-1)-(q- 1)/2 1 ) mod p. BP q = (EP (q-1)/2 0 * EP q-(q-1)/2 1 ) mod p. Now the given basic monic polynomial is illustrated in Eq.1. and its decimal equivalent is calculated as in eq.2, BP(x) = BP q x q + BP q-1 x q-1 +….+ BP 5 x 5 + BP 4 x 4 + BP 3 x 3

+ BP 2 x 2 + BP 1 x 1 + BP 0 x 0 ……………………….. (1)
Decm_eqv(BP(x))= BP q ×p q + BP q-1 ×p q-1 +….+ BP 5 ×p Similarly all the decimal equivalents of all the resultant basic polynomials or reducible polynomials for all a and its corresponding b values are calculated. The polynomials belonging to the list of reducible polynomials are cancelled leaving behind the irreducible polynomials.

Description of the Computational Algorithm.

Here the Basic polynomials over Galois Field overGalois Field GF(p q ) is presented as BP(x) and Elemental polynomials over the same Galois field is presented as ep(x). For Galois Field GF(p q ) the prime modulus = p and the extension of the prime modulus = q. Highest degree term of the 1 st elemental polynomial ep(x 1 ) is d 1 € {1,2,3,…………,(q-1)/2} and second elemental polynomial ep(x 2 ) is d 2 € { (q -1), (q-2), (q-3),...,q -(q-1)/2}. Number of terms in 1 st elemental polynomial € {N(d 1 )} and number of terms in 2 nd elemental polynomial € {N(d 2 )}.

Coefficients of each ep(x) are demonstrated as EPep_ indx_i , where 1≤ i ≤2.

Here Number of terms in Basic Polynomial = p+1. Coefficients of BP(x) = BP bp _ indx, where 0≤ bp_indx ≤ q, The said Computational Algorithm is as follows,

Step 1. for block = 1 to (N(d 1 ) or N(d 2 )) do the following steps.

Step 2. for ep_index_1 = 1 to (q-1)/2 do the following steps.

Step 3. for ep_index_2 = (q-1) to (q-((q-1)/2)) do the following steps.

Step 4. for bp_index = 0 to q do the following steps. ). Means it is much faster as Rabin's algorithm [START_REF] Jacques | An Improvement of Rabin's Probabilistic Algorithm For Generating Irreducible Polynomials Over Gf(P)[END_REF] for larger value of prime modulus and its modification [START_REF] Jacques | An Improvement of Rabin's Probabilistic Algorithm For Generating Irreducible Polynomials Over Gf(P)[END_REF]. Since the time complexity of the both Rabin's algorithm and its modification depends upon the value of prime modulus so it becomes a slow algorithm for large value of the prime modulus. But the new algorithm is much effective and works better as the value of prime modulus and the extension of prime modulus grows larger since time complexity depends only on the value of the extension of the Galois field. So this algorithm is suitable to find monic Irreducible polynomials of higher value of prime modulus and the extension of prime modulus .

Description of the Computational Algorithm for Galois Field GF(7 7 ).

Here the Basic polynomials over Galois Field overGalois Field GF(7 7 ) is presented as BP(x) and Elemental polynomials over the same Galois field is presented as ep(x). For Galois Field GF(7 Step 1. for block = 1 to 3 do the following steps.

Step 2. for bp_index = 1 to 8 do the following steps.

Step 3. for ep_index_1 = 1 to 3 do the following steps.

Step 4. for ep_index_2 = 6 to4 do the following steps.

Step 5. for P 1 = 2 to 4 and P 2 = 7 to 5 do the following steps.

Step 6. BP bp_indx = (Σ(EP ep _ indx_1 p1 ×EP ep _ indx_2 p2

)) mod p; Step 7. Stop.

Results.

The algebraic method or the above pseudo code has been tested on GF(3 3 ),GF( 73 ),GF( 113

), GF(101 3 ), GF (3 5 ), GF (7 5 ), GF(3 7 ), GF(7 7 ),. Numbers of monic Irreducible polynomials given by this algorithm are same as in hands on calculation by the theorem to count monic irreducible polynomials over Galois Field GF(p q ) [START_REF] Church | Tables of Irreducible Polynomials for the first four Prime Moduli[END_REF]. The list of Numbers of monic irreducible polynomials for a particular Galois Field are given below for all of the above ten Extended Galois Fields. The list of all Irreducible monic basic polynomials of ten extended Galois fields are available in reference [START_REF] Dey | The list of Decimal Equivalents of All the Monic Irreducible Polynomials over Galois Field GF(3^3)[END_REF] 7 ) is given in Appendix and also available in the link given in [START_REF] Dey | The list of Decimal Equivalents of All the Monic Irreducible Polynomials over Galois Field GF(7^7)[END_REF].

Ex.GF. GF(3 3 ) GF( 73 ) GF( 113 ) GF(101

Conclusion.

To the best knowledge of the present authors, there is no mention of a paper in which the composite polynomial method is translated into an algorithm and turn into a computer program. The new algorithm is a much simpler to find monic irreducible polynomials over Galois Field GF(p q ). It is able to determine decimal equivalents of the monic irreducible polynomials over Galois Field with a large value of prime modulus, also with large extensions of the prime modulii. So this method can reduce the time complexity to find monic Irreducible Polynomials over Galois Field with large value of prime modulii and also with large extensions of the prime modulii. So this would help the crypto community to build S-Boxes or ciphers using irreducible polynomials over Galois Fields with a large value of prime modulii, also with the large extensions of the prime modulii.

Step 5 . 4

 54 for P 1 = 1 to N(d 1 ) and P 2 = 1 to N(d 2 ) do the following steps. Step 6. BP bp_indx = (Σ(EP ep _ indx_1 p1 ×EP Time Complexity of the New Algorithm. This Algorithm have a time complexity of O(n 5

  Comparison of time complexity of the new algorithm with other Algorithms is given below,

	Algorithms Time Complexity	New Algorithm O(n 5 )	Rabin's Algorithm O(n 4 (log P) 3 )	Rabin's Algorithm(mod) 0(n 4 (log p) 2 + n 3 (log P) 3 )

  [START_REF] Dey | The list of Decimal Equivalents of All the Monic Irreducible Polynomials over Galois Field GF(7^3)[END_REF][49][START_REF] Dey | The list of Decimal Equivalents of All the Monic Irreducible Polynomials over Galois Field GF(101^3)[END_REF][51][START_REF] Dey | The list of Decimal Equivalents of All the Monic Irreducible Polynomials over Galois Field GF(7^5)[END_REF][53][START_REF] Dey | The list of Decimal Equivalents of All the Monic Irreducible Polynomials over Galois Field GF(7^7)[END_REF]. A part of the list of monic Irreducible Polynomial over GF[START_REF] Koblitz | Elliptic curve cryptosystems[END_REF]

Statement Regarding Conflict of Interest in Authors.

This is regarding manuscript 1962424 titled "A New Algorithm to Search for Irreducible Polynomials Using Decimal Equivalents of Polynomials over Galois Field GF(p^q)" submitted to International Scholarly Research Notices "The author(s) declare(s) that there is no conflict of interest regarding the publication of this paper.

Sankhanil Dey and Ranjan Ghosh


MURAD Nour Mohammad

Loic Guegan

Sylvain Bonhommeau
email: sylvain.bonhommeau@ifremer.fr

Why satellite localization beacons are not adapted for marine turtles' study: a sea wireless sensors network solution

This article shows the effects of various parameters like the radio channel conditions or even the modulation on sea turtles trajectory estimated by terrestrial localization algorithms. This work is part of wireless sensors networks domain in the marine and terrestrial environment in the world of living beings. It allows to identify and understand the parameters that lead to inaccuracies over the sea turtles trajectory. Another important part of this project is to better understand the morphology of the sea turtles and his environment. It also proposes another way to localized sea turtles.

I. INTRODUCTION

Assessing functional habitats (feeding and reproduction areas) for marine species is critical for conservation and management purposes. Since the 1990s, the development of tags that records the positions of marine species has enabled scientist to better determine these habitats. These devices have been developed to track sea turtles which are currently on the list of endangered species by the International Union for Conservation of Nature (IUCN). There is hence critical needs for conservation measures and better scientific knowledge about these species' ecology.

There are different positioning system modules for the localization of sea turtles available on the market. But they are most often expensive which limits the number of animals that can be tracked and hence the statistical robustness of results. Moreover, researchers have no access to the algorithms used to estimate animal positions. Recent advance in the data transfer for "Internet of Things" applications open new avenues for using this technology in marine application. This technology also offers ways to geolocate objects using algorithms based on the emission power or time from the gateways and transceivers. To overcome the disadvantages of current devices tracking animals, several radio modules are chosen to transfer data to a fixed array of ground stations called gateways based on the LoRa technology [1]. We test different localization algorithms [START_REF] Evennou | Techniques et Technologies de Localisation Avancées Pour Terminaux Mobiles Dans Les Environnements Indoor[END_REF] that involve best turtles position estimation and optimal gateways position on the coast or earth. The distances between sea turtles and gateways (GW) will be in the order of kilometers, which is acceptable for this type of localization. Juvenile turtles that we focus the study on are generally foraging in coastal areas.

In order to better understand or apprehend errors on the estimation of the trajectory of the turtles, it is essential to know first of all the biology of the animal and then in a second time to model and to correctly integrate the physical parameters of the channel radio transmission [START_REF] Guegan | Integrating Over Sea Radio Channel for Sea turtles Localization in the Indian Ocean[END_REF]. Thus, from the biological perspective sea turtles swim at different speeds. They may spend very short times at the surface to breath in the millisecond range and more longer times around two or three minutes [START_REF] Southwood | Heart Rates and Diving Behavior of Leatherback Sea Turtles in the Eastern Pacific Ocean[END_REF]. In addition from the sea turtle environment perspective, it is necessary to take into account the radio conditions of the over sea environment, which may be extreme in some cases [START_REF] Huang | Multipath Channel Model for Radio Propagation over Sea Surface[END_REF], [START_REF] Wu | Ray Tracing Based Wireless Channel Modeling over the Sea Surface near Diaoyu Islands[END_REF]. Wind, waves and sea spray are factors that can alter the signal. This is why we have decided to integrate the over sea radio channel conditions, in order to adapt the algorithms used to attain the best possible accuracy on turtle localization. Thus, our contribution consists in:

• Design a robust radio transmission against the sea meteorological condition in choosing a robust modulation • Design a reliable transmitter module for sea turtle • Show the impact of the number of gateway and their distribution on the trajectory accuracy • Improve the accuracy of sea turtles trajectories estimation using a better knowledge about the marine radio channel The rest of the paper is structured as follows. In section III an introduction to sea biology turtle and its behavior are done in order to define constraints on the beacon design. Next the section IV presents the localisation algorithms and the one used in this paper. The section V gives wireless network topology and the protocol communication. Section VI shows and analyses the impact of some natural and technical parameters on the estimation of sea turtle trajectory. The section VII presents existing localisation technologies and their limits.Finally the section VIII conclude the paper.

II. ACRONYMS AND NOTATIONS

• BT: Beacon Turtle The studied species (green sea turtle, Chelonia mydas) can reach 1.5 m (carapace length) and weigh up to 400 kg. They live in the tropical and subtropical oceans worldwide. Green sea turtles move across three habitat types, depending on their life stage. They lay eggs on beaches. Mature turtles spend most of their time in shallow, coastal waters with lush seagrass beds. Adults frequent inshore bays, lagoons and shoals with lush seagrass meadows. Entire generations often migrate between one pair of feeding and nesting areas. Within their geographical range, the green sea turtles generally stay near continental and island coastlines. Near the coastlines, the green sea turtles live within shallow bays and protected shores. In these protected shores and bays, the green sea turtle habitats include coral reefs, salt marshes, and nearshore seagrass beds. For these reasons, the size and weight of the beacon is not a strong constrains as it shouldn't be more than 5% of the animal weight.

Green sea turtles migrate long distances between feeding sites and nesting sites; some swim more than 2 600 km to reach their spawning grounds. Mature turtles often return to the exact beach from which they hatched. Females usually mate every two to four years. In the tropics, green turtles nest throughout the year, although some subpopulations prefer particular times of the year.

Turtles spend most of their first five years in convergence zones within the bare open ocean that surround them. These young turtles are rarely seen as they swim in deep, pelagic waters. Green sea turtles typically swim from 2.5 to 3 km/h. Sea turtles spend almost all their lives submerged, but must breathe air for the oxygen needed to meet the demands of vigorous activity. With a single explosive exhalation and rapid inhalation, sea turtles can quickly replace the air in their lungs from 100 to 200 ms. During routine activity, green turtles dive for about 4 to 5 minutes, and surface to breathe for one to three seconds. They can also stay at the surface for several minutes to catch sun and rest. The maximum depth of turtle dives is 200 m which implies that the beacons should resists to pressure of 20 bar.

Thus multiple constraints should be taken into account. Firstly, the two transmission's options are, during the turtle's surfacing or when the turtle is on the beaches. During the turtle's surfacing, the transmission's time can be short (100 ms and 200 ms) or long (2 min to 3 min) [START_REF] Southwood | Heart Rates and Diving Behavior of Leatherback Sea Turtles in the Eastern Pacific Ocean[END_REF]. Moreover in the water, several conditions may affect the transmission's quality such as sea spray, and swell (can be of several meters). On land, sea turtle can be covered by the vegetations and the localization's precision may be inaccuracy or in the worst case impossible. Another constraint called Doppler shift, due to the sea turtle's movements and its environment, should be considered. In fact, this phenomenon causes frequency shift and multipath presence during signal's transmission. All of these lead to a bad reception on GW.

IV. LOCALIZATION TECHNIQUES OVERVIEW

Various beacon emitter localization techniques are possible, each of them has specific advantages and disadvantages. Generally, emitter localization techniques are based upon one or more measure of one or more of the following properties :

• The received signal power (Received Signal Strength, Power of Arrival) [START_REF] Zhu | RSSI-Based Algorithm for Indoor Localization[END_REF] [8] • The signal's propagation time (Time Of Arrival, Time Difference Of Arrival) [START_REF] Evennou | Techniques et Technologies de Localisation Avancées Pour Terminaux Mobiles Dans Les Environnements Indoor[END_REF] [9] [10] • The direction of arrival (Angle Of Arrival) [START_REF] Evennou | Techniques et Technologies de Localisation Avancées Pour Terminaux Mobiles Dans Les Environnements Indoor[END_REF] • Relative shifts in the signal frequency observed at pairs of spatially separated sensors, at least one of which is moving (Frequency Difference Of Arrival) [START_REF] Shao | TDOA/FDOA Geolocation with Adaptive Extended Kalman Filter[END_REF] The main emitter localization technique applied here uses measurement of the received signal strength (RSS) obtained from the individual GW, the GW position and a path loss model that relates the path loss to the propagation distance. A particular simple case occurs for free space propagation.

Here the path loss of an electromagnetic wave is proportional to 1/d 2 i . Therefore, by knowing the BT transmitter power p t , the distance between the BT and GW can be determined from a properly calibrated measure of the GW received signal power p r . This distance directly defines the equation of a line corresponding to the radius of a circle centered on the GW position. Each point of this circle defines a possible position of the BT. If two GW are used, the result will be a pair of circles that normally intersect at two points, one of which corresponds to the BT location. Consequently, using n g GW (with n g > 2), the BT position will correspond to a cluster of n g × (n g -1)/2 intersections. Of course, this approach implies an ideal over sea radio channel. Furthermore, in a marine environment, the received signal power p r will depend on various factors, such as the heights of the transmission and reception antennas and the nature of the sea. The sea effects are particularly important. In practice the path loss will not be a monotonic function of the distance and the underlying dependence on distance can vary between 1/r 2 and 1/r 4 . To be able to approximate the distance between the BT and the GW using POA technique, the RSSI of a receive signal transmitted by BT need to be measured on GW. This metric is measured with a small inaccuracy according to the Radio Frequency (RF) module on GW. Next with the strong hypothesis the use of a path loss channel, it's possible to approximate the distance between BT and GW. Friis equation in decibel, known as telecommunication equation is used as the path loss model (see equation 1).

p r (d i ) = 20.log 10 p t .G t .G r .λ 4.π.d i + 30 (1)
With : d i : distance between the BT to the i th GW (m) p r : GW received power or RSSI (dB m ) p t : BT transmitter power (W ) G t : transmitter antenna linear gain G r : receiver antenna linear gain λ : wavelength (meters)

The distance d i can easily be deducted from equation 1 as,

d i = λ 4π × 1 1 PtGtGr × 10
Pr -30 10

(2)

So classical technique to locate a beacon's signal origin using the POA technique, is to use multilateration. Multilateration enable to approximate the position of a beacon by knowing the distance that separating this beacon from other knowing positions called anchors. Then with the different distances d i from Beacon Turtle (BT) and each GW i, three circles can be drawn if three GW are used (see figure 1). With the intersections formed by the circles, we can compute line equations and found their intersection to finally approximate the turtle position. In some cases, two circle intersections can coincide and is considered as one point. Therefore no intersection lines can be drawn because there is an infinite number of line equation that passing thought one point.

Let's consider now three GW. The coordinate of the i th GW is the couple (x i , y i ). If the emitter BT is located at (x, y), the distance from the emitter to the i th GW is given by

d i = (x -x i ) 2 + (y -y i ) 2 (3)
Finally, we can estimate the position (x, y) of the BT.

V. WIRELESS NETWORK TOPOLOGY AND COMMUNICATION PROTOCOL

In order to determined a good network topology and his feasibility, the Europa Island field and the communication protocol need to be described and analyzed. Therefore Europa Island visible in the figure 2 is about 6 km from west to east and 7 km from north to south. So a coverage area of S = 15 km 2 will be under observation and oversight. When the turtle take a breath, a pressure sensor detects if the turtle is under or above the water. Then, the BT broadcasts a beacon message (figure 3). The beacon message contains four fields. First, the preamble field of size n p = 6 bits is useful to estimate the radio channel's profile (p r , T pi ). It consists of a particular bit sequence with some mathematical properties like equiprobability of zero and one, periodicity, cyclicity and stationarity. The preamble sequence is known from the BT and the GW. The second field contains the turtle identity with a size of n id = 1 byte. So a maximum of 256 turtles could be identified with the beacon. The third field called stamp of size n s = 1 byte allow all GW to maintain the order of the received frames. And the last field is the data that contain physiological parameters and the transmission time for TOA with a size of n d = 8 bytes. Finally, beacon message size is express in the following way n f = n p + n id + n s + n d = 86 bits.

Furthermore the electronic beacon don't encode the data and stays simple in order to save energy and to send the message efficiently. At a given GW receiver, all fields of the message are demodulated except the preamble field (see figure 4). This last is correlated with the original sequence preamble known by the BT and a given GW. The correlator function estimates the power and the delay profile of the sea radio channel instantaneously. Then we could estimate the received power p r and the propagation's delay T p of the main path shown in figure 5. In order to highlight the main path we represent the radio channel's profile with its normalized power [START_REF] Guegan | Integrating Over Sea Radio Channel for Sea turtles Localization in the Indian Ocean[END_REF]. To finish, the couple (p r , T pi ) is sent to the POA localization algorithm. This last estimates and saves the position of the BT on a data base. VI. RESULTS AND ANALYSIS Simulation parameters are given in table I. All parameters computed in this table suppose that we are using the SX1276 Lora RF module [START_REF] Semtech | SEMTECH SX1276 Datasheet[END_REF]. In order to compare all results, we use the same known trajectory (see figure 6) of the turtle for each condition factor like the radio channel's conditions, the modulation, the number of GW, the position of GW and the GW distribution.

A. Radio Channel's Impact

The radio channel has a direct impact on the turtle trajectory estimation. In fact, depending on the sea radio conditions, the GW may be unable to receive the signal from the turtle beacon and data loss can occurs (see figure 7). We define two realist path loss channels based on actual measurement. This two channels are visible on table II. To build this two channels, we place a turtle beacon on the ground and a GW transmitter at a distance of 20 m. Channel 1 was obtained by placing the GW at 1 meter of the ground and channel 2 was obtained by placing it directly on the ground. It must be noted that, the GW height need to be taken into account in the parameters of the reception's quality. The analysis of the table III compares the two realistic channels to an ideal channel and its shows that the radio channel's conditions have lot of impact on the sea turtle's localization accuracy. Tiny variations of the radio channel's conditions may cause bad reception of the signal by the GW.

B. Modulations Impact

The modulation reliability to the radio channel conditions is shown in figure 8. This figure shows three modulations that are part of the Lora SX1276 module [START_REF] Semtech | SEMTECH SX1276 Datasheet[END_REF]. According to the modulation's plots, frequency-shift keying (FSK) is more robust compared to phase modulation like minimum-shift keying (MSK) and gaussian minimum-shift keying (GMSK). In fact these phase modulations are more subject to multi path which delay the signal's phase. For example, with SN R = 0 dB the BER ≈ 2% with the FSK modulation against BER ≈ 15% for GMSK and BER ≈ 25% for MSK.

C. Gateway number impact

The figure 9 shows the effect of the number of gateway on turtle trajectory errors. The more n g increases the less error of trajectory occurs. So with 10 GW, we have an error of trajectory around 4%. However in order to maintain a suitable balance between environment and localization accuracy, we decide to use 8 GW that corresponding to a trajectory error around 10%. The real trajectory consists of 173 known points scattered over a distance of 10 km traveled by the turtle. With 8 GW, 156 points are found against 17 points lost. So a compromise between the respect of the environment [START_REF]Les îles éparses[END_REF], the GW power supply limited by batteries and a reasonable error rate was found.

D. Gateway disposition impact

The GW are disposed at equal distances D max , to obtain the best radio signal coverage. The different way to distribute the GW can significantly decrease the number of position errors and improve the localization accuracy. The influence of the GW geometrical distribution are shown in table IV. Disposed the GW linearly, led to a position error of 100%. In fact, all lines built from circle intersections will be vertical, and no line intersections will be possible. So, no conclusion can be made about the turtle's position. According to the table IV, the best gateway distribution from the available patterns is the hexagonal pattern.

VII. RELATED WORK

We introduce here some work based on existing techniques that can be used to find sea turtles' position [START_REF] Coyne | Satellite Tracking and Analysis Tool (STAT): an integrated system for archiving, analyzing and mapping animal tracking data[END_REF] living in different part of the world like in South Pacific Ocean [START_REF] Boyle | Evidence for transoceanic migrations by loggerhead sea turtles in the southern Pacific Ocean[END_REF] or in Indian Ocean [START_REF]Distribution spatiale des localisations de la Tortue Verte (Chelonia mydas) suivis par balise Argos depuis Tromelin (TAAF)[END_REF]. This section deals with the state of play of the beacons used on animals to locate or collect some physiological data. Argos is a beacon [17] which transmits at a carrier frequency of 401.650 MHz, with a power of 250 mW and a variable transmission rate between 40s and 200s with a step of 10s. The transmission duration varying from 360 to 920 ms according to the beacon message length (from 32 bits to 256 bits). Three NOAA satellites in polar orbits ensures the Argos beacons localization. On circular orbits at 850 km the satellite can receive waves transmitted by all beacons in a circle of 5 000 km of diameter on the Earth's surface. According to the beacon latitude, the satellite passing 7 times a day on the equator and 28 times on the poles [18]. The beacon localization are made in the following manner. When the satellite is passing over the beacon, it receives a signal on a specific frequency, code and repetition. In other words, all beacons transmit at the same frequency, but with different code and at different times. The measure of Doppler Shift, and the use of particular algorithms gives the beacon position. The given position by this technique has an accuracy in a range of 150 to 300 m [START_REF] Peberay | Présentation des balises Argos[END_REF].

These Argos beacons are limited by their prices around 5 000 e, their lifetimes (∼ 1 year), they need to reach a maximum of 5% of the animal's weight but also a limited amount of recorded data around 356 bits. Moreover, the Argos beacon's communication is very expensive. Unlike the Argos technology, the Lora beacon is able to transmit with a power of 20 mW at carrier frequency of 868 MHz. This particularity of the Lora module allows to increase its operating time. Moreover, a sea turtle Lora transmitter is much less expensive (around 300 e) than an Argos beacon and the communication band is free of charge.

The LOng RAnge Navigation system (LORAN) [START_REF] Ridenour | LORAN[END_REF] is a radio navigation system that use the fixed terrestrial emitter waves to establish a position. The LORAN is a hyperbolic type system. Hyperbolic systems determine the position by measuring the difference in propagation time between a minimum of two transmitters and the points' positions with equal difference is an hyperbola on the map. Three transmitters are required for hyperbolas' intersection point. The first hyperbolic system, LORAN-A, operated at 1800 kHz, the LORAN-C operated at 100 kHz. The maintenance of LORAN, less accurate and with a limited coverage, is periodically challenged to be replaced by new generation localization beacons like Global Positioning

System (GPS).

There is various localization beacons like the American GPS, the Russian GLONASS, the European Galileo or the Chinese Beidou. The GPS works with Precise Positioning System (PPS) [START_REF]Global Positioning System Standard Positioning Service Performance Standard[END_REF] in no degraded mode or Standard Positioning System (SPS) [START_REF]Global Positioning System Precise Positioning Service Performance Standard[END_REF] in degraded mode. The SPS signal offers to the public an accuracy in a range of 10 m to 100 m horizontally. The GPS receiver sensibility range from -165 dBm in tracking mode to -148 dBm in acquisition mode [START_REF] Skylab | Ultra High Sensibility and Low Power GPS Receiver Module[END_REF]. GPS provide some limitations. The signal's transmission quality can be easily altered and the communication is impossible when the sea turtle is below the surface (interrupted localization). Some devices use the « Fastloc » technology to quickly locate the animal's surfacing. These devices record and transfer raw data from GPS satellites. Once the data gathered, the animal position can be estimated with calendars and ephemerids of satellites by using algorithms. This technique provides a precision up to 70 m [START_REF] Dujon | The Accuracy of Fastloc-GPS Locations and Implications for Animal Tracking[END_REF]. GPS beacons are more accurate than our localization technique. In fact the Lora's localization technique provide a precision around 50 m. But GPS is a passive beacon and no physiological's data can be transmitted. Moreover GPS and Fastloc positions need to be collected and they are not real time systems.

VIII. CONCLUSION

Lot of parameters can alter the localization techniques' accuracy and need to be considered. Firstly the modulation and FSK was selected because we proved that its more robust to the effects of the radio channel conditions. Secondly the number of GW is another interesting parameter, and a number of 8 GW will be enough. Finally the geometrical distribution of the GW has an impact on the localization's accuracy. So, octagon geometrical distribution of the GW is a correct solution. The next step of our work consist in the development of a beacon and doing field experiments to compare the field measurements to the simulated measurements.

Fig. 1 .

 1 Fig. 1. Multilateration using three gateways.

Fig. 2 .

 2 Fig. 2. Europa Island.

Fig. 3 .

 3 Fig. 3. Frame structure of the beacon message.

Fig. 4 .

 4 Fig. 4. Link transmission between turtle beacon and a gateway.

Fig. 5 .

 5 Fig. 5. Normalized power and delay estimation sea radio channel profile.Another question to deal with, is the sending frequency of the beacon message. As the bit rate D b = 37.5 kbps, the frame duration is equal to T f = 231.424 ms. So during the short breaths of the turtle the BT transmitter could transmit 1 frame and during the long breath it could transmit 648 frames. The fact that the beacon message is sent frequently could improve the position estimation.

Fig. 8 .

 8 Fig. 8. Impact of the modulation choice.

Fig. 9 .

 9 Fig. 9. Impact of gateway number.

  Received signal strength indication • SPS: Standard positioning system • d i : distance between the beacon turtle to the i th gateway • n g : number of gateway • p t : beacon transmitter power • p r : gateway receiver power • n p : size of the preamble field • n d : size of the data payload field • n id : size of the turtle identification field • n s : size of the stamp field • n f : size of the beacon message • T b : bit time • T f : frame time • T pi : propagation time for the i th path • η : gateway receiver radio sensibility • D max : maximum distance for a given (p t , η)

	III. SEA TURTLE BIOLOGY AND CONSTRAINS ON THE
	BEACON DESIGN

• DGPS: Differential GPS • GPS: Global Positioning System • GW: Gateway • PPS: Precise Positioning System • RSSI:

TABLE I SIMULATION

 I PARAMETERS.

	Parameters	Value
	ng	variable (3 by default)
	Pt	13 dBm (20 mW)
	np	6 bits
	n id	8 bits
	n f	86 bits
	T b	2.69 ms
	η	-148 dBm
	T f	231.4ms

Fig. 6. A arbitrary turtle linear trajectory.

TABLE III ANALYSIS

 III OF THE RADIO CHANNEL IMPACT

		Total	Found	Lost	Error Rate
	Ideal	173	173	0	0%
	Channel 1	173	68	105	60%
	Channel 2	173	39	134	77%

TABLE IV IMPACT

 IV OF THE GATEWAYS GEOMETRICAL DISTRIBUTION.

	Disposition	ng	% Position error
	Linear (aligned)	3	100
	Equilateral triangle	3	84.12
	Arbitrary triangle	3	88.81
	Square	4	63.41
	Hexagonal pattern	6	28.34