Pierrick Gaudry
email: gaudry@lix.polytechnique.fr

A comparison and a combination of SST and AGM algorithms for counting points of elliptic curves in characteristic 2

Since the first use of a p-adic method for counting points of elliptic curves, by Satoh in 1999, several variants of his algorithm have been proposed. In the current state, the AGM algorithm, proposed by Mestre is thought to be the fastest in practice, and the algorithm by Satoh-Skjernaa-Taguchi has the best asymptotic complexity but requires precomputations. We present an amelioration of the SST algorithm, borrowing ideas from the AGM. We make a precise comparison between this modified SST algorithm and the AGM, thus demonstrating that the former is faster by a significant factor, even for small cryptographic sizes.

Introduction

In the design of an elliptic public key cryptosystem, parameter initialization is a difficult task; it is required to count points of curves until one is found with almost prime group order. In the early ages of elliptic curve cryptography, the only way to achieve this was to use curves with special properties like having complex multiplication by a small discriminant or being supersingular, though taking random curves might be seen as the most secure. The first polynomial time algorithm for point-counting was designed in 1985 by Schoof [START_REF] Schoof | Elliptic curves over finite fields and the computation of square roots mod p[END_REF], but was not fast enough to deal with cryptographical sizes. A decade of theoretical and practical improvements by Atkin, Couveignes, Elkies, Lercier, Morain, Müller lead to a situation where point-counting was efficiently feasible for cryptographical sizes (see the survey [START_REF] Blake | Elliptic curves in cryptography[END_REF] and the references therein). However, the cost of parameter initialization remained high (in runtime and in complexity of programming) compared to other systems like RSA or XTR. Situation changed in 1999 when Satoh [START_REF] Satoh | The canonical lift of an ordinary elliptic curve over a finite field and its point counting[END_REF] proposed a new algorithm for counting points of elliptic curves over finite field of small characteristic. His method is based on the computation of the canonical lift of the curve in a p-adic local ring. The theoretical complexity is asymptotic better than all the variants of Schoof's algorithm. Further work by Fouquet-Gaudry-Harley [START_REF] Fouquet | An extension of Satoh's algorithm and its implementation[END_REF][START_REF] Fouquet | Finding secure curves with the Satoh-FGH algorithm and an early-abort strategy[END_REF], Skjernaa [START_REF] Skjernaa | Satoh's algorithm in characteristic 2[END_REF], Vercauteren et al. [START_REF] Vercauteren | A memory efficient version of Satoh's algorithm[END_REF], Satoh-Skjernaa-Taguchi [START_REF] Satoh | On p-adic counting algorithms for elliptic curves over finite fields[END_REF][START_REF] Satoh | Fast computation of canonical lifts of elliptic curves and its application to point counting[END_REF], Hae Young Kim et al. [START_REF] Kim | Fast elliptic curve point counting using Gaussian normal basis[END_REF] made this algorithm practical, in particular in characteristic 2, which is the most important in practice. Another closely related method, based on the algebraic-geometric mean (AGM) was found by Mestre, and an implementation by Harley [5] proved it to be very efficient. For a curve over F 2 n , the complexity of all these method is in O(n 3+ε ), except for the Satoh-Skjernaa-Taguchi (SST) method which achieves a complexity in O(n 2.5+ε ) but requires precomputations.

In characteristic 2, with the current state of the art, AGM is thought to be the fastest for cryptographical sizes, due to a very small constant, and is also the best algorithm for computing records. The first drawback of the SST algorithm is the precomputation stage which is not feasible for records, but this is not at all a problem for cryptographical sizes, where this is easily doable and the storage of the precomputed data is manageable. Another problem in the SST method is that the defining polynomial for the local ring is dense, thus increasing the cost of a multiplication by a factor of 3 compared to the sparse structure used in AGM.

Our contribution is two-sided: firstly we mix ideas of SST and AGM to get what we call the modified SST algorithm (MSST) which is faster by a constant factor compared to the original SST algorithm. Our improvement modifies only the lifting phase; the norm computation which is common to both algorithm is not modified. Then we make a precise comparison between MSST and AGM algorithms, based on an evaluation of the number of operations required at each precision. This turns out to be in favor of MSST, even for small cryptographical sizes, as confirmed by some experiments we did on a Pentium III: for curves over F 2 163 we get a speed-up by a factor of 4.15 and for curves over F 2 239 the factor is 4.90.

The paper is organized as follows: in Section 2 we recall some basics and fix notations. In Section 3 and 4, we give a brief description of the original SST and AGM algorithms. Section 5 is devoted to the mix of SST and AGM algorithms. Section 6 contains a theoretical comparison between MSST and AGM methods, and Section 7 contains the numerical experiments.

General Setting and Notations

Let F q be a finite field of characteristic 2, and let n be such that q = 2 n . Let E be a non-supersingular elliptic curve over F q . For the purpose of point-counting, without lost of generality, and perhaps considering the quadratic twist of E, we can assume that E has an equation of the form y 2 + xy = x 3 + a 6 . Then its jinvariant is given by j = a -1 6 . Denote by N the group order of E. The trace of E is defined by Tr(E) = q + 1 -N and Hasse's theorem states that |Tr(E)| ≤ 2 √ q.

All the p-adic point-counting methods proceed in the same way: lift some data from F q to a p-adic local ring with enough precision, and deduce a p-adic approximation of the Tr(E) which might be enough to conclude due to Hasse's bound.

In our case, the 2-adic local ring we shall consider is the ring of integers of the degree n unramified extension of Q 2 . In the following we denote this ring by Z q (noted W (F q ) in some papers, or simply R in [START_REF] Satoh | Fast computation of canonical lifts of elliptic curves and its application to point counting[END_REF]). Note that Z q has nothing to do with Z/qZ, just like the ring of 2-adic integers Z 2 is not Z/2Z. The ring Z q is equipped with a cyclic Z 2 -automorphism of order n which reduces to the 2-nd power Frobenius automorphism of F q .

We give a constructive way to see the ring Z q . Let f (t) be the irreducible polynomial of degree n over F 2 chosen to define F q = F 2 [t]/(f (t)). Consider any monic polynomial f (t) with coefficients in Z 2 which reduces to f (t) modulo 2. Then f (t) is irreducible and Z q can be defined by Z q = Z 2 [t]/(f (t)). Different choices for the polynomial f (t) lead to isomorphic rings. From an algorithmic point of view two strategies can be used: choosing a sparse f (t) with small coefficients speeds up the basic arithmetic, because the reduction modulo f (t) is almost for free; this is the representation used in the AGM algorithm. On the other hand, lifting f (t) in a careful way can give a representation in which the Frobenius substitution is efficiently computable, the price to pay is a dense polynomial f (t), hence a non-negligible reduction modulo f (t); this is the representation used in the SST algorithm.

Notations in Z q

The ring Z q comes with the natural "reduction modulo 2" homomorphism onto F q . For x ∈ Z q , the notation x mod 2 means the element of F q image of x by this homomorphism. The ring Z q also comes with a valuation. Let x and y be elements of Z q ; the valuation of (x -y) is high when x and y are close to each other. More precisely, the valuation of (x -y) is k if (x -y) is in 2 k Z q ; then we write x ≡ y mod 2 k Z q , or simply x ≡ y mod 2 k .

In an algorithm, when we say "compute x := . . . mod 2 k ", this means that the expression for computing x involves quantities which are known to precisions such that the result is known to precision at least k. The variable x is then assigned an element which is congruent to the result modulo 2 k .

We use the same notation σ for all kind of 2-nd power Frobenius action: ring/field automorphisms of F q and Z q , and also their coordinate-wise extensions to isogenies from an elliptic curve to its conjugate. There should be no confusion, because all the domain of these maps are distinct and all the reduction-diagrams involving two of these σ commute.

Canonical Lift of an Elliptic Curve

It is easy to find many curves over Z q whose equations reduce to the equation of E modulo 2. However, there is a canonical way to do it and keep information on the group order.

Theorem 1 (Lubin-Serre-Tate). Let E be a non supersingular elliptic curve over F q . Then, up to isomorphism, there exists a unique curve E defined over Z q , such that:

1. The equation of E reduces to the equation of E modulo 2; 2. End(E) ∼ = End(E).

A consequence of this theorem is the following commutative diagram

E σ ----→ E σ     E σ ----→ E σ
where σ on the top arrow is the 2-nd power Frobenius isogeny from E to E σ . This isogeny being of degree 2, the modular equation of degree 2 relates the j-invariants of the canonically lifted curves:

Φ 2 (j(E), j(E σ )) = 0,
where Φ 2 (X, Y ) is the symmetric bivariate polynomial

X 3 + Y 3 -X 2 Y 2 + 1488(XY 2 + X 2 Y ) -162000(X 2 + Y 2 ) + 40773375XY + 8748000000(X + Y ) -157464000000000.
Notation: Let c be an element of Z q and let c be its reduction modulo 2. If c is not the j-invariant of a supersingular curve, then we denote by c ↑ the j-invariant of the canonical lift of an elliptic curve whose invariant is c.

Satoh-Skjernaa-Taguchi Algorithm

We do not describe all the details of the SST algorithm: we concentrate on the main two steps: firstly the j-invariant of the canonical lift of E is computed to some precision, then the norm of a quantity is computed, yielding the trace. We refer to the original paper [START_REF] Satoh | Fast computation of canonical lifts of elliptic curves and its application to point counting[END_REF] for a description of the missing steps.

Canonical Lifting of the j-Invariant

We are given j(E) in F q \ F 4 , and we want to compute j(E). The value of j(E) is determined one bit after the other: assume that we know J such that J ≡ j(E) mod 2 k , then writing j(E) = J + 2 k e, and plugging it formally into the equation Φ 2 (j(E), j(E σ )) = 0, one gets an equation yielding e modulo 2. Hence we have gained one bit on the approximation of j(E).

For a more precise setting, we take a Taylor expansion:

0 = Φ 2 (j(E), j(E) σ ) = Φ 2 (J + 2 k e, J σ + 2 k e σ ) = Φ 2 (J, J σ ) + 2 k e∂ X Φ 2 (J, J σ ) + 2 k e σ ∂ Y Φ 2 (J, J σ ) + 2 2k-1 (element of Z q ).
In this equation, Φ 2 (J, J σ ) is zero modulo 2 k , we can therefore divide everything by 2 k . Furthermore the Kronecker relation implies that

∂ X Φ 2 (J, J σ ) is zero modulo 2 and that ∂ Y Φ 2 (J, J σ ) is different from zero modulo 2.
Finally we have e σ ≡ e 2 mod 2 and we get

e 2 ≡ Φ 2 (J, J σ ) 2 k ∂ Y Φ 2 (J, J σ ) mod 2.
To turn this into an algorithm, we need to apply σ to elements of Z q . For this, the polynomial defining Z q over Z 2 is chosen such that its roots are (q -1)-th roots of unity. This polynomial is precomputed once for all, for each base field. Hence Frobenius substitution is just reordering the coefficients and reducing modulo the defining polynomial (see [START_REF] Satoh | On p-adic counting algorithms for elliptic curves over finite fields[END_REF] for details).

Then we get the following first lifting algorithm: (inverse of Frobenius is used, thus saving the computation of the square root of e in the previous formula) Algorithm 1. Input: j and a desired precision k. Output: j ↑ to precision k.

1. d := ∂ Y Φ 2 (σ -1 (j), j); 2. y := j; 3. For i from 1 to k -1 do 4.
x := σ -1 (y) mod 2 i+i ; 5.

y := y -d Φ 2 (x, y) mod 2 i+1 ; 6. Return y;

In a point counting context, we need k ≈ n 2 . Running the i-th loop requires 1 Frobenius substitution and O(1) multiplications of elements of Z q at precision 2 i+1 . Therefore the cost of Algorithm 1 is in O(n 1+2µ ) bit-operations, which is the cost of other lifting methods. Here µ is a real such that multiplication of k bit objects can be done in time O(k µ ).

When looking at what is going on in

Step 5, we see that Φ 2 (x, y) is very close to zero and only the small non-zero piece of information is used to update y. It looks sub-optimal to recompute all the time Φ 2 (x, y) from scratch: the values of x and y at step i + 1 are close to the ones at step i, therefore Φ 2 (x, y) at step i + 1 can be deduced from its value at step i and some adjustment involving partial derivatives. By precomputing the partial derivatives modulo 2 W , one can update Φ 2 (x, y) during W iterations, then one needs to recompute one time Φ 2 (x, y) from scratch before doing again W iterations with only cheap updates. These ideas yield the SST lifting algorithm, a sketch of which is reproduced in Algorithm 2.

In [START_REF] Satoh | Fast computation of canonical lifts of elliptic curves and its application to point counting[END_REF] it is shown that Algorithm 2 runs in time O(n 2µ+1/(µ+1) ), when one chooses W = n µ/(µ+1) . Therefore, it is always better than Algorithm 1, because µ > 1. If an FFT-based multiplication algorithm is used, µ = 1 + ε, and we get a complexity of O(n 2.5+ε ).

From the lifted j, a quantity can be derived which is a rational fraction in j, such that the norm of this quantity gives the trace of E.

Algorithm 2. SST canonical lifting

Input: j and a desired precision k; a parameter W . Output: j ↑ to precision k.

1. y := j ↑ mod 2 W , computed via Algorithm 1; 2. D X := ∂ X Φ 2 (σ -1 (y), y) mod 2 W ; D Y := ∂ Y Φ 2 (σ -1 (y), y) mod 2 W ; 3. For m from 1 to ⌊ k-1 W ⌋ do 4.
Lift arbitrarily y modulo 2 (m+1)W ; 5.

V := Φ 2 (σ -1 (y), y) mod 2 (m+1)W ; 6.

For i from 0 to W -1 do 7.

Compute y := j ↑ mod 2 mW +i+1 ; 8.

Update V := Φ 2 (σ -1 (y), y) mod 2 mW +i+1 ; // Steps ( 7) and ( 8) use only operations modulo 2 W ; 9. Return y;

Fast Norm Computation

In [START_REF] Satoh | Fast computation of canonical lifts of elliptic curves and its application to point counting[END_REF] a fast norm computation is described, that is well-suited to the case of point-counting in characteristic 2. It is based on the following equation:

Norm(x) = exp(Tr(log(x))),
which holds whenever log and exp converge. Computing a trace is far easier than computing a norm, and the subsequent exponential is very cheap. Therefore the main cost is a log evaluation, which is performed by fast evaluation of power series. We refer to the original paper for details, and will not discuss this part anymore, since the norm computation is a step which has to be done for any variant of the algorithm, and it is not the place where one is better than the other.

AGM Algorithm

We recall here the principles of the AGM algorithm. We give no proof of the results, they can be derived in the same manner as for the other point-counting algorithms and are out of the scope of this paper.

The Arithmetic-Geometric Mean (AGM) Sequence

Let a 6 be an element of F * q and let E be the curve of equation y 2 + xy = x 3 + a 6 with j-invariant j(E) = a 6 -1 . We denote also by a 6 an arbitrary element of Z q that reduces to a 6 modulo 2. We then have recursive formulae which give a well-defined sequence (A i , B i ) of elements of Z q :

A 0 = 1 + 8a 6 , B 0 = 1, A i+1 = A i + B i 2 , B i+1 = A i B i ,
where the square root is chosen to be congruent to 1 modulo 4. Indeed, by induction, we show that if A i ≡ B i ≡ 1 mod 4 and Ai Bi = 1 + 8α for an invertible α, then the squareroot is possible to be taken and if the one which is chosen is congruent to 1 modulo 4, the same properties hold at step i + 1.

This sequence (A i , B i ) is called the AGM sequence and we can associate to it the sequence of elliptic curves E i of equations

y 2 = x(x -A 2 i )(x -B 2 i
). We denote by j i the j-invariant of the curve E i .

Link with Canonical Lifting

It is well known that AGM is linked to isogenies of degree 2 between elliptic curves. This in turn gives a link with the canonical lifting as follows: Theorem 2. Let j i be the j-invariant of the curve E i attached to the AGM sequence. Then the sequence j i verifies:

j 0 ≡ a -2 6 mod 2, j i+1 ≡ j 2 i mod 2, j i ≡ j ↑ i mod 2 i+2 .
The first assertion shows that E 0 is isomorphic to the conjugate of a lift of the initial curve E modulo 2. The second relation states that all the curves E i also reduce modulo 2 to conjugates of the curve E (up to isomorphism). The third one is the heart of the AGM algorithm: it means that when progressing along the AGM sequences, we get closer and closer to the canonical lift.

This yields immediately a straightforward algorithm for computing the canonical lift. Starting with the initial values of (A 0 , B 0 ), we apply the recursive formula to compute successive values of (A i , B i ). After k steps, we can compute the j-invariant of the associated curve which is close to the canonical lifting of a conjugate of E up to precision about 2 k .

The link with the trace is given by the following result:

Theorem 3. Let i > 0 and let c i be Norm Zq/Zp Ai+1 Ai
. Then

c i + q c i ≡ Tr(E) mod 2 i+4 .
A point-counting algorithm follows easily: one computes the AGM sequence with enough steps, then a norm computation gives the trace of the initial curve up to some precision which is equal to the number of steps plus a constant. A practical complication arises: on a computer one cannot really deal with elements of Z q , but with truncated ones. At first sight, it seems that we need a high starting precision for A 0 and B 0 , because we get less and less significant digits on A i and B i when at the same time the j i gets closer to the canonical lift. This problem can be overturned by arbitrary noise to A i and B i just before doing an operation which "looses" precision like a square root or a division by 2.

After having cleaned the details we get the following algorithm: k

:= k + 1; 6. a ′ := a+b 2 ; 7. Return Norm( a ′ a ) mod 2 ⌈ n 2 ⌉+2
as a signed integer in

[-2 √ 2 n , 2 √ 2 n ].

Runtime Analysis

The AGM algorithm requires O(n) operations between elements of Z q with maximal precision in O(n), and then a norm computation. As said before, the norm computation will not be discussed here, because it is the same in every algorithm. The cost of the lifting process is in O(n 1+2µ ), which is the same as Algorithm 1.

Hence Algorithm 2 by Satoh-Skjernaa-Taguchi is asymptotically faster than the AGM for the lifting phase (but requires precomputation). However the AGM algorithm has a very low constant, due to the small number of operations at each step and the fact that a sparse defining polynomial for Z q can be used. The figures given in [START_REF] Satoh | Fast computation of canonical lifts of elliptic curves and its application to point counting[END_REF] suggest that for cryptographical sizes, AGM remains faster.

AGM-Aided SST Algorithm

The AGM algorithm as stated before does not appear to be mixable with the SST idea. Therefore, before doing so we need to rewrite it in a univariate way to reveal the hidden modular equation which can then be used instead of Φ 2 in the SST algorithm. This is also this version of the AGM algorithm that we shall use for the comparison and the implementation in the next sections. We do not expect any speed difference between the univariate and the bivariate AGM.

Univariate AGM Algorithm

Taking again the AGM sequence as a starting point, we define a new sequence

λ i = A i B i .
The corresponding curves have equation

y 2 = x(x -1)(x -λ 2 i
). An easy computation shows that λ i+1 can be computed directly from λ i by

λ i+1 = 1 + λ i 2 √ λ i .
Another important fact is that λ i+1 ≡ λ σ i mod 2 i+4 , which corresponds to the fact that we are jumping from a curve to an approximation of its conjugate.

The corresponding univariate AGM algorithm is as follows: k

Algorithm 4.
:= k + 1; 6. Return Norm( 2λ 1+λ ) mod 2 ⌈ n 2 ⌉+2 as a signed integer in [-2 √ 2 n , 2 √ 2 n ].
Implementation of the Square Root. The main step of this algorithm is

Step (4) in which we have to compute the inverse of the square root of λ and to multiply the result by 1+λ 2 . The inverse of the square root is computed via a Newton iteration that can be done without inversion. First we note that λ is always of the form λ ≡ 1 + 8α mod 16. Then 1 √ λ ≡ 1 -4α mod 8, and this will be the initialization of the lift. Then the iteration is

x n+1 := x n + x n 2 (1 -λx 2 n ).
If for some n, x n is congruent to 1 √ λ modulo 2 k , then one can show that x n+1 is equal to 1 √ λ modulo 2 2k-1 (see for instance Lemma 2.7 in [START_REF] Fouquet | An extension of Satoh's algorithm and its implementation[END_REF]).

Modified Modular Equation

In the previous algorithm, the λ i which is computed at the last step of the loop is (the conjugate of) a solution of the following equations:

Z ≡ 1 + 8a 6 mod 16, (Z σ ) 2 (1 + Z) 2 -4Z ≡ 0 mod 2 i .
But this is precisely this kind of system that SST algorithm is meant to solve. It remains to remove the leading non-significant bits in λ i and to prove the same result on partial derivatives that made Algorithm 1 work.

Let E(X, Y ) be AGM modular equation:

E(X, Y ) = Y 2 (1 + X) 2 -4X = 0.
We make a change of variables X ← 1 + 8X, Y ← 1 + 8Y, and the modular equation becomes:

Ẽ(X, Y ) = (X + 2Y + 8XY ) 2 + Y + 4XY = 0,
which has to be solved, subject to the conditions that X is known and non-zero modulo 2 and Y = X σ .

The partial derivative of Ẽ evaluated at (X, Y ) give

∂ X Ẽ(X, Y ) = 2(X + 2Y + 8XY )(1 + 8Y ) + 4Y ∂ Y Ẽ(X, Y ) = (1 + 4X)(1 + 4(X + 2Y + 8XY ))
This proves that ∂ X Ẽ(X, Y ) is congruent to 0 modulo 2, whereas ∂ Y Ẽ(X, Y ) is 1 modulo 2, thus yielding the required asymmetry for the SST algorithm to converge. Note also that the partial derivative with respect to Y is 1 modulo 2, so that it is no longer necessary to compute d in Step (1) of Algorithm 1.

Modified Satoh-Skjernaa-Taguchi (MSST) Algorithm

According to the previous section, it is possible to use SST algorithm to compute the lifted invariant of the curve (or more precisely some kind of Legendre's invariant of the canonical lift of the curve). It remains to compute the data whose norm will give the result. This is actually much simpler than in the original SST algorithm: transposing the results of the AGM method, we can see that if λ is a solution of Ẽ(X, X σ ) and λ ≡ a 6 mod 2 then the following holds:

Tr(E) ≡ Norm 1 1 + 4λ mod 2 n .
We obtain Algorithm 5.

The advantage of the MSST algorithm is 2-sided: firstly the modular equation is smaller thus reducing by a constant factor the number of operations, secondly the intermediate step between the lift and the norm does not exist any more, thus simplifying the code and giving a slight speed-up.

Theoretical Comparison

The MSST algorithm is always faster than the plain SST algorithm because it involves strictly less operations. It remains to compare it to the AGM algorithm.

Algorithm 5. MSST point-counting

Input: a 6 in F × 2 n . Output: Trace of the curve y 2 + xy = x 3 + a 6 .

1. y := a 6 ; // arbitrary lift to 2 W . 2. For i from 1 to W -1 do 3.

x := σ -1 (y) mod 2 i+i ; 4.

y := y -Ẽ(x, y) mod 2 i+1 ; 5.

x := σ -1 (y) mod 2 W ; 6. D X := ∂ X Ẽ(x, y) mod 2 W ; D Y := ∂ Y Ẽ(x, y) mod 2 W ; 7. For m from 1 to ⌈ n 2W ⌉ do 8.
Lift arbitrarily y modulo 2 (m+1)W ; 9.

x := σ -1 (y) mod 2 (m+1)W ; 10.

V := Ẽ(x, y) mod 2 (m+1)W ; 11.

For from 0 to W -

1 do // break if i + mW ≥ ⌈ n 2 ⌉ 12. ∆ Y := -2 -mW V mod 2 W ; 13. ∆ X := σ -1 (∆ Y ) mod 2 W ; 14. y := y + 2 mW ∆ Y mod 2 (m+1)W ; 15. V := V + 2 mW (D X ∆ X + D Y ∆ Y ) mod 2 (m+1)W ; 16. Return Norm( 1 1+4y ) mod 2 ⌈ n 2 ⌉+2 as a signed integer in [-2 √ 2 n , 2 √ 2 n ].

Constraint Environments

In a constraint environment it might be preferable to choose an algorithm for which no precomputation need to be stored and the RAM requirement stays low. In this context, the AGM algorithm (with the norm computation replaced by an extra loop) is by far the best choice. However, one should keep in mind that for a reasonable key-size, the amount of precomputed data to be stored for the SST algorithm is not so high: this is essentially two elements of Z q at maximal precision; for instance, for F 2 163 , it is only a few kilo-bytes. This might be too much for a smart card, but this is not a problem on a PDA. We consider as unlikely that someone really wants to count points in a highly constraint environment. Indeed, this kind of computation is required during the setup of the system parameters and the result does not need at all to be secret. Hence a card can ask to the server to do the computation if a new parameter setting is required.

In the following, we shall therefore concentrate on the case where we have no constraints and a machine word size of 32 bits (still the most common for PC's).

Assumptions

We recall that we are interested in cryptographically useful sizes. In that case, it has been shown in [START_REF] Satoh | Fast computation of canonical lifts of elliptic curves and its application to point counting[END_REF] that in the SST algorithm it is not worthwhile to use a W parameter different from machine word size. Therefore we shall always consider that W = 32 is the optimal parameter for the MSST algorithm.

Another assumption we make is that multiplying integers of size less than the machine word size is not significantly faster than multiplying integers of size exactly the machine word size. At first sight, this assumption looks reasonable since the assembly instructions for multiplying bytes or short integers usually do not require much less cycles than the instruction for long integers. In fact this is a bit misleading because in both AGM and MSST algorithms several of these operations are parallelizable, one could therefore pack several small integers in a word size integer and perform several multiplication at once, or one could also use specific multimedia instruction like the MMX or SSE2 instruction set in the case of the Pentium. Using those could speed-up both the algorithms and we shall consider that we do not penalize one or the other by always using machine-word-size arithmetic.

Cost Analysis

In this section we compare the lifting parts of the AGM and the MSST algorithm. In MSST, we use a dense defining polynomial for Z q in order to speed-up the Frobenius substitution computation. Therefore the reduction modulo the defining polynomial subsequent to a multiplication or a square is costly. On the other hand, in the AGM we have no Frobenius substitution to perform and it is possible to use a sparse defining polynomial, leading to an almost free reduction. Therefore, reductions will be counted in the MSST algorithm whereas we shall neglect them in the AGM. In MSST, with the dense polynomial, Frobenius substitution can be done at a cost of roughly one multiplication and one reduction, as explained in [START_REF] Satoh | On p-adic counting algorithms for elliptic curves over finite fields[END_REF]. We do not count additions and other simpler operations.

We use the following notations for the basic operations in Z q :

P : unreduced product S : unreduced square R : reduction modulo defining polynomial Furthermore, we can add an index i to each of these symbols to indicate the number of W-bit-digits of each operand.

MSST Algorithm

The cost to evaluate the modular equation Ẽ is P + S + 2R. Each of its partial derivatives can be evaluated at a cost of 2P + 2R, and if one wants both derivatives, one can share the result of one product and get a cost of 3P + 3R.

Steps ( 2)-( 4) cost (W -1)(2P 1 + S 1 + 3R 1 ).

Steps ( 5)-( 6) cost 4P 1 + 4R 1 .

Next we analyze the cost of Steps ( 8)-(15) for each value of m:

Steps ( 9)-( 10) cost 2P m+1 + S m+1 + 3R m+1 .

Steps ( 12)-(15) cost W (3P 1 + 2R 1 ). Indeed, the multiplications by powers of 2 are for free, and one reduction can be saved at step (15). Actually, as explained in [START_REF] Satoh | Fast computation of canonical lifts of elliptic curves and its application to point counting[END_REF], some operations could be done on one bit operands.

If we need to lift to precision k, the total cost of MSST is then

(3k-W +2)P 1 +(2k+W +1)R 1 +(W -1)S 1 + 1≤m≤⌈ k-W W ⌉ (2P m+1 +S m+1 +3R m+1 ).
We then apply this formula with W = 32, for two base fields. For F 2 163 , we need a precision k = 82, and we get

C M SST (163) = 216P 1 + 31S 1 + 197R 1 + 2P 2 + S 2 + 3R 2 + 2P 3 + S 3 + 3R 3 .
For F 2 239 , we need a precision k = 120, and we get

C M SST (239) = 330P 1 + 31S 1 + 273R 1 + 2P 2 + S 2 + 3R 2 + 2P 3 + S 3 + 3R 3 +2P 4 + S 4 + R 4 .
Hence we readily notice that for cryptographical sizes, only few operations require multiprecision arithmetic.

AGM Algorithm

As said above, we study the univariate AGM instead of the bivariate one. The key step is then clearly Step (4), and in this step the crucial part is the Newton iteration for computing the inverse of √ λ:

x n+1 := x n + x n 2 (1 -λx 2 n ).
As usual for a Newton iteration, we need to have operations with variable precision. If we want to compute x n+1 with precision k from x n known at precision roughly k/2, at first sight it requires one square and two products computed modulo 2 k . However this can be improved: (1 -λx 2 n ) is zero at precision k/2, because x n is already a good approximation of the result. Hence when we multiply this further by x n , this is actually a multiplication at precision k/2 that has to be performed. One step further is explained by Karp and Markstein in [START_REF] Karp | High precision division and square root[END_REF]: the "self-correctingness" of this iteration allows to compute λx 2 n with two multiplications of an operand at precision k and the other at precision k/2.

We note however that in our case a square ideally costs roughly one half of a product and that this "Full times Half" precision product saves one fourth of the operations. Thus the trick of Karp and Markstein does not help in our case.

Estimating the number of operations in a Newton iteration is not that easy, due to the variable precision. To simplify the formulae we shall consider that the precision is exactly doubled at each step (whereas in fact one bit is lost). On the other hand this is easy to write a short program that emulate the algorithm and count the number of operations and the precision required, because there is no branching depending on the input data. Hence for a given base field, it is much simpler to run this emulation to evaluate the cost. We shall compare the results given by both approaches.

Cost of one lift in precision.

The cost of the Newton iteration to get the inverse of the square root at a precision between 2 k-1 and 2 k < W is (k -1)(2P 1 + S 1 ). After the lift one has to multiply the result by 1+λ 2 , which cost another P 1 .

Cost of the first W iterations. We split the interval [0, W ] into pieces where the cost of the iterations are the same, and add them all. We get the following formula for the cost:

2≤k≤log 2 (W ) (k -1)2 k-1 (2P 1 + S 1 ) + W P 1 , which simplifies to (2 + W (log 2 (W ) -2)) (2P 1 + S 1 ) + W P 1 .
Cost of the W iterations between precision W and 2W . The last step in a Newton iteration is done at precision of two W -bit digits and all the others are at precision 1. Furthermore, for each lift, the number of iteration at precision 1 is always (log 2 (W ) -1)(2P 1 + S 1 ). Hence the cost of all the second W operations is

W (log 2 (W ) -1)(2P 1 + S 1 ) + P 1 + 2P 2 + S 2 .
In this formula, we took into account the fact that in the last iteration at precision 2, one operation has only to be done at precision 1.

Cost of the W iterations between precision 2W and 3W . The last step in a Newton lift is done at a precision of 3 digits, thus reducing to compute the result at a precision between W and 1.5W . The penultimate step is therefore at a precision of 2 digits, and the remaining steps are done at precision 1. The overall cost is then

W (log 2 (W ) -1)(2P 1 + S 1 ) + P 1 + 2P 2 + S 2 + 2P 3 + S 3 .
Cost of the W iterations between precision 3W and 4W . The last step in a Newton lift is done at a precision of 4 digits, and the penultimate is done at a precision of 2 digits. The others steps are done at precision 1. Hence the following overall cost:

W (log 2 (W ) -1)(2P 1 + S 1 ) + P 1 + 2P 2 + S 2 + 2P 4 + S 4 .
Cost of one iteration at a precision of k digits. The Newton iteration starts as always by (log 2 (W ) -1) operations at a precision of 1 digit. Then there are O(log 2 (k)) operations at a precision of at most k digits. Including the cost of the multiplication by 1+λ 2 , there is at least 2P k + S k . We apply now our analysis to the same cases than for the MSST algorithm, namely n = 163 and n = 239, with W = 32. We get

C AGM,th (163) = 696P 1 + 306S 1 + 104P 2 + 52S 2 + 40P 3 + 20S 3 , and
C AGM,th (239) = 1038P 1 + 458S 1 + 180P 2 + 90S 2 + 64P 3 + 32S 3 + 52P 4 + 26S 4 .
With the emulation program mentioned above we get:

C AGM,emu (163) = 694P 1 + 303S 1 + 109P 2 + 57S 2 + 45P 3 + 23S 3 , and
C AGM,emu (239) = 1033P 1 + 452S 1 + 188P 2 + 98S 2 + 64P 3 + 32S 3 + 57P 4 + 29S 4 .
These values are close enough to justify the simplifications we made in our analysis.

Comparison

We first compare the cost of the lifting up to precision W = 32, where all the operations that take place are single precision. We have to compare

62P 1 + 31S 1 + 93R 1 and 228P 1 + 98S 1 .
This clearly depends on the relative costs of R 1 and P 1 . It is always possible to do a reduction at the cost of two products, once a small precomputation is done (see [START_REF] Zur Gathen | Modern computer algebra[END_REF], page 247). Hence R 1 ≤ 2P 1 . Note that in our implementation (see below) we got a ratio close to 1.5. Also S 1 is usually about 1.5 faster than P 1 . With these ratios, the advantage is on MSST side.

Next, we compare the costs for gaining W bits of precision at a higher level. This corresponds to one iteration of Steps ( 8)-(15) in MSST or W loops of AGM. Let k be the number of digits corresponding to the precision. In MSST, the cost is

2P k + S k + 3R k + 96P 1 + 64R 1 ,
whereas in AGM we have

64P k + 32S k + • • • + 256P 1 + 128S 1 ,
where the dots contain operations at a precision strictly between 1 and k digits. Hence MSST is clearly faster than than AGM, and the difference increases with the size of the basefield, due to the higher number of operations at multiprecision in AGM.

Practical Experiments

We implemented MSST and the univariate AGM algorithm in the C programming language, using the GNU MP library [START_REF] Granlund | The GNU Multiple Precision arithmetic library -4[END_REF] for the low-level integer multiplications. Multiplications in Z q are done via Karatsuba algorithm. We wrote specific code for the machine word-size precision because in that case many things are simplified and this is critical in both algorithms. We give timings for two field sizes: n = 163 and n = 239. We see that at low precision, we were able to get a reduction step faster than two times a product. For the two given field sizes, the ratio between the two lifted methods is a factor of 6 to 7 in favor of the MSST algorithm. We implemented the norm computation to get significant runtimes for the complete point-counting computation. However this part is not as well optimized as the first step and the runtime we give might be improved. We only mention that in case of MSST algorithm, after the lift, we switch to the sparse representation before calling the same norm routine as the one used for AGM. This base conversion can be made very quick by precomputing the corresponding matrix. For cryptographical sizes, this matrix fits easily in a few mega-bytes, but for records, this strategy is not feasible. For the complete computation, the overall gain we have by choosing MSST instead of AGM is respectively by a factor of 4.15 and 4.90 for fields of 163 and 239 bits.

For comparison, we recall that the runtimes given in [START_REF] Satoh | Fast computation of canonical lifts of elliptic curves and its application to point counting[END_REF] for the original SST algorithm were 0.76s for a field of 163 bits and 2.54s for 239 bits on a 866 MHz Pentium III.

Conclusion

We presented a modification of the SST algorithm, using ideas taken from the AGM algorithm to speed-up the lifting phase and remove the second phase; the norm computation is unchanged. We did a precise theoretical and experimental comparison between our method and the AGM. We demonstrate that the number of operations is much smaller for the former. To illustrate this we implemented both methods with the same level of optimization -actually, they use the same time-critical functions. The gain is significant, even for small cryptographical field sizes.

For cryptographical applications, it is required to have an almost prime group order. Therefore it is usually necessary to count O(log(n)) curves before finding one suitable for cryptography. To speed-up this search, in [START_REF] Fouquet | Finding secure curves with the Satoh-FGH algorithm and an early-abort strategy[END_REF] the authors propose to mix the p-adic point-counting method with an early-abort strategy à la Schoof. Indeed for a small prime ℓ, it is possible to decide quickly whether the group order is divisible by ℓ, and if so to switch to another curve without running the p-adic algorithm. The size of the largest ℓ for which we do this depends on the relative costs of the point-counting algorithm and the early-abort. Since [START_REF] Fouquet | Finding secure curves with the Satoh-FGH algorithm and an early-abort strategy[END_REF], the cost of point-counting has been greatly reduced, and the number of ℓ to consider must have diminished accordingly. Therefore it would be nice to also have new ideas in the early-abort stage to obtain another speed-up in the curve construction.

Algorithm 3 .

 3 AGM point-counting Input: a 6 in F * 2 n . Output: Trace of the curve y 2 + xy = x 3 + a 6 . 1. a := 1 + 8a 6 mod 16; b := 1 mod 16; k := 4; 2. Repeat until k = ⌈ n 2 ⌉ + 3: 3. Lift arbitrarily a and b modulo 2 k+2 ; 4. (a, b) := a+b 2 mod 2 k+1 , √ ab mod 2 k+1 ; 5.

  Univariate AGM Input: a 6 in F * 2 n . Output: Trace of the curve y 2 + xy = x 3 + a 6 .

	1. λ := 1 + 8a 6 mod 16; k := 4; 2. Repeat until k is ⌈ n 3 ⌉ + 3: 3. Lift arbitrarily λ modulo 2 k+2 ;
	4. 5.	λ := 1+λ 2 √ λ mod 2 k+1 ;

  All the experiments are made on a Pentium III at 700 MHz running Linux. The compiler is gcc version 2.96. Field size Precision Product Square Reduction 163 1 word 0.11 ms 0.07 ms 0.14 ms 2 words 1.4 ms 0.92 ms 2.3 ms 3 words 1.8 ms 1.3 ms 3.6 ms 239 1 word 0.21 ms 0.13 ms 0.29 ms 2 words 2.5 ms 1.7 ms 4.9 ms 3 words 3.4 ms 2.3 ms 6.8 ms 4 words 5.4 ms 4.5 ms 10.8 ms

	Field size Lift MSST Lift AGM Norm computation Total MSST Total AGM
	163	0.08 s	0.49 s	0.05 s	0.13 s	0.54 s
	239	0.26 s	1.82 s	0.14 s	0.40 s	1.96 s

Acknowledgments

We thank Takakazu Satoh, Robert Harley and François Morain for valuable comments and remarks.


E Bonnet

B Borderie

N Le Neindre

Ad R Raduta

M F Rivet

R Bougault

A Chbihi

J D Frankland

E Galichet

F Gagnon-Moisan

D Guinet

P Lautesse

J Lukasik

P Marini

M Pârlog

E Rosato

R Roy

G Spadaccini

M Vigilante

J P Wieleczko

B Zwieglinski

New scalings in nuclear fragmentation

Keywords: numbers: 25, 70, -zLow and intermediate energy heavy-ion reactions ; 25, 70, Pq Multifragment emission and correlations

Fragment partitions of fragmenting hot nuclei produced in central and semiperipheral collisions have been compared in the excitation energy region 4-10 MeV per nucleon where radial collective expansion takes place. It is shown that, for a given total excitation energy per nucleon, the amount of radial collective energy fixes the mean fragment multiplicity. It is also shown that, at a given total excitation energy per nucleon, the different properties of fragment partitions are completely determined by the reduced fragment multiplicity (fragment multiplicity normalized to the source size). Freeze-out volumes seem to play a role in the scalings observed.

The process of the total disintegration of a nucleus accompanied by a copious production of nuclear fragments, termed multifragmentation, was discovered more than forty years ago [1]. However, tremendous progress in the understanding of multifragmentation came during the last fifteen years with the advent of powerful 4π detectors [2][3][4]. From the theoretical side, the equation of state describing nuclear matter, similar to the van der Waals equation for classical fluids, foresees the existence of a liquid-gas type phase transition and multifragmentation was long assimilated to this transition. In the last ten years the general theory of first order phase transition in finite systems was strongly progressing [START_REF] Gross | Microcanonical Thermodynamics -Phase Transitions in "small" systems[END_REF][START_REF] Gulminelli | [END_REF][7]. Today a rather coherent picture has been reached which is related to the experimental observation of different phase transition signatures for hot multifragmenting nuclei [4,[8][9][10][11][12][13][14][15]. The region of phase coexistence was identified in a semi-quantitative way (3 to 10 AMeV excitation energy and 0.7 to 0.2 times the normal density) and it is experimentally observed that fluctuations (configurational energy and charge of the heaviest fragment) are large and even maximum in the middle of this region for multifragmenting nuclei produced in semiperipheral collisions [START_REF] Neindre | INDRA and ALADIN collaborations)[END_REF]. Such large fluctuations seem to correlate points at a distance comparable to the linear size of the system and can therefore have an effect, in the coexistence region, similar to a diverging correlation length in an infinite system at the critical point [START_REF] Neindre | INDRA and ALADIN collaborations)[END_REF][17][START_REF] Yeomans | Statistical Mechanics of Phase Transitions[END_REF]. Consequently one can expect to reveal new specific scalings related to a first order phase transition for finite systems. To do that, in this Letter, we compare, with the help of the reduced fragment multiplicity, the fragment partition properties of fragmenting hot nuclei produced in central and semiperipheral collisions.

The experiments were performed with the 4π multidetector for charged reaction products INDRA [20]. For central collisions, beams of 129 Xe, accelerated by the GANIL accelerator in Caen, France, at five incident energies: 25, 32, 39, 45 and 50 MeV/nucleon, bombarded a thin target of natural tin (350 µg/cm 2 ) and hot quasifused (QF) nuclei/sources with Z around 70-100 could be selected [12]. Hot nuclei with lower Z around 60-70 (quasi-projectile, QP, sources) were obtained in semiperipheral Au+Au collisions at 80 and 100 MeV/nucleon incident energies at the SIS heavy ion synchrotron at the GSI facility in Darmstadt, Germany [21]. In this experiment the 197 Au beam was impinging on a 2 mg/cm 2 thick target. For both experiments, Z identification was obtained over the whole range of fragments produced and the energy calibration was achieved with an accuracy of 4%. Further details can be found in [22][23][24].

The procedures used to select the studied nuclei/sources are the following. First of all poorlymeasured events were rejected by requiring the detection For comparisons, QF and QP events are limited to those with excitation energies defined as

|E * -< E * > | ≤ 0.3 σE * .
of at least 80% of the charge of the initial system (projectile plus target for QF sources, projectile only for QP sources). Then compact sources were selected by using topology selectors in velocity space. For QF sources the constraint of large flow angle (≥ 60 • ) calculated with the kinetic energy tensor for fragments (Z≥5) in the center of mass of the reaction was imposed (for details see [12]). For QP sources it was done by imposing a maximum value (2/3 of the QP velocity) of the mean relative velocity between fragments emitted in the forward hemisphere of the center of mass (see Eqs.( 1),( 2) and [START_REF] Bonnet | [END_REF] for details). A constant QP size, within 10%, was additionally required. Note that for QP sources fission events were removed [25]. Further information concerning selections and light charged particles associated to sources can be found in [START_REF] Bonnet | [END_REF]. The following step consists in the evaluation of the total excitation energy of the different sources. The calorimetric method [START_REF]Dynamics and Thermodynamics with nuclear degrees of freedom[END_REF] was used event by event. Neutrons are not detected but their multiplicity is estimated from the difference between the mass of the source and the sum of the masses attributed to the detected charged products. The source is assumed to have the same N/Z ratio as the initial system. Hypotheses which have been made for QF sources are the following: a level density parameter equal to A/10, the average ki-netic energy of neutrons equal to their emitting source temperature and the Evaporation Attractor Line formula (A=Z(2.072+2.32×10 -3 Z)) [27] used to calculate fragment masses. EAL is especially well-adapted when heavy fragments (Z > 20) result from the deexcitation of neutron deficient sources. For QP sources the hypotheses are identical except for calculated fragment masses for which we use the formula (A=Z(2.045+3.57×10 -3 Z)) [27], better adapted for excited nuclei close to the beta-stability valley. Note that, compared to the EAL formula, differences appear only for masses associated to Z greater than 40.

In the following, we will use as main sorting parameter the total excitation energy per nucleon, E * , to compare fragment properties of both QF and QP sources. Excitation energy bins of compared samples have been fixed by values (mean and σ) calculated for QF sources at the five incident energies (see Table I). Only the mean values are reported in the panels of figures.

We suppose that fragment velocities, in their source frame, are the results of the composition of three components: a randomly-directed thermal contribution, a Coulomb contribution dependent on the fragment charges and source sizes, and a radial collective energy. To evaluate the radial collective energy involved in the de-excitation of the different sources the mean relative velocity between fragments

β rel = 2 M f rag (M f rag -1) i<j | β (ij) | (1)
β (ij) = β (i) -β (j) (2)
is used, which is independent of the reference frame. Only events or subevents (for QP sources) with fragment multiplicities M f rag greater than one are considered. It was shown in [START_REF] Bonnet | [END_REF] that this observable is a good measure of the amount of radial collective energy. The thermal component of fragment velocities has a negligible contribution to their mean relative velocity, while increasing the size of fluctuations. The effect of the Coulomb contribution is removed by using a simple normalization

β (N ) rel = β rel < Z > (Z s -< Z >) (3)
which takes into account, event by event, the Coulomb influence of the mean fragment charge (< Z >) on the complement of the source charge (Z s -< Z >).

We first look at the most global observable: the mean fragment multiplicity. Figure 1 shows that, for a given total excitation energy per nucleon, the mean fragment multiplicity normalized to the source charge/size < M (N ) f rag >= < M f rag /Z s > is strongly correlated with the amount of radial collective expansion, as measured by β N rel . Crosses correspond to mean values for each type of source. Depending on the source type the relative contributions of radial collective energy (thermal pressure and compression-expansion cycle) strongly differ [START_REF] Bonnet | [END_REF] but in all cases β N rel , representative of the total collective energy, fixes the normalized mean fragment multiplicity. Note that for the largest β N rel values (above 0.006) reached only at the higher excitation energies for QF sources, normalized fragment multiplicities increase more slowly. In that case the average size of fragments decreases and a larger fraction of them have a charge below our fragment limit Z=5.

One can now go a step further and study the properties of fragment partitions (total charge bound in fragments, heaviest fragment, asymmetry in charge of fragments) associated to the different values of the fragment multiplicity distributions. To do that, and to be able to compare QF and QP sources, we introduce a new variable the reduced fragment multiplicity M f rag /< Z s >. It is built from Fig. 2 (left side) which shows the evolutions of the mean source size with the different values, M f rag , of the fragment multiplicity distributions for the different excitation energies per nucleon. Figure 2 (right side) shows the evolution with the reduced fragment multiplicity of the total charge bound in fragments normalized to the source charge/size, Z (N ) f rag , for the different excitation energies per nucleon. We observe that the mean values of Z (N ) f rag are independent of the source type. On the left side of Fig. 3 average values of the heaviest fragment charge, Z 1 , are reported: values for QP and QF sources follow exactly the same evolution. The independence of Z 1 on the system size was already observed and is valid as long as the total system or projectile mass is above 190 [4,28]. Finally the division of the charge among the other fragments is investigated using the generalized charge asymmetry of the fragment partitions, with at least 3 fragments noted A Z \{Z 1 }. The results are displayed in Fig. 3 (right side). They follow a linear behavior and do not depend on the source type at a given total excitation energy per nucleon.

A Z = 1 M f rag -1 σ Z < Z > (4)
To summarize, we have shown in this Letter new results independent of the mechanism of production of hot fragmenting nuclei. First, at a given total excitation energy per nucleon, the amount of the radial collective energy fixes the mean fragment multiplicity normalized to the charge/size of the fragmenting hot nucleus; we recall that in the multifragmentation regime (3-10 AMeV) the radial collective energy is limited to at most 20% of the total excitation energies involved [START_REF] Bonnet | [END_REF]. And secondly, the properties of fragment partitions are completely determined by the reduced fragment multiplicity. What is the possible origin of the scalings observed? To, at least, give a direction to follow for future studies, we have checked to what extent fragment partition scalings are compatible with statistical multifragmentation models with cluster degrees of freedom. The standard version of the Microcanonical Multifragmentation Model (MMM) [29,30] was used. Inputs were the average A and Z of QF and QP sources at the different total excitation energies per nucleon. Contributions of radial collective energy to the total excitation energy were taken from [START_REF] Bonnet | [END_REF]. We do obtain fragment partition scalings if and only if the freeze-out volume of the QF sources increases monotonically with the total excitation energy from 2.7 to 5.7 V 0 and the freeze-out volume of the QP sources is kept fixed at the intermediate value of 3.5 V 0 ; V 0 would correspond to the volume of the source at normal density. However the agreement between MMM results and the present observed scalings is partial: a rather fair agree-ment for Z (N ) f rag and Z 1 and a systematic underestimation for the fragment asymmetry without Z 1 . We recall that in MMM the radial collective energy is decoupled from the break-up thermodynamics and fragment formation. Clearly dynamical approaches, which contain the coupling between thermal and collective expansion effects to produce fragments [31], must be compared to those data.

FIG. 1 :

 1 FIG. 1: (color online) Evolution of the average fragment multiplicity normalized to the source charge/size < M (N) f rag >= < M f rag /Zs > as a function of the relative velocity of fragments, β N rel , (see text) for different total excitation energy per nucleon of the sources. Full squares, open and full circles stand respectively for QF sources and QP sources produced at 80 and 100 MeV/nucleon incident energies. Crosses correspond to the mean values of the considered samples for QF (black) and QP (grey dashed-80 MeV/nucleon and full-100 MeV/nucleon) samples, see text.

FIG. 2 :

 2 FIG. 2: (color online) Left side refers to mean values of source charges as a function of fragment multiplicity for different total excitation energy per nucleon of the sources. Right side shows the evolution of the total charge bound in fragments normalized to the source charge/size, Z (N) f rag , as a function of the reduced fragment multiplicity M f rag /< Zs > for the same total excitation energies. Full squares, open and full circles stand respectively for QF sources and QP sources produced at 80 and 100 MeV/nucleon incident energies.

FIG. 3 :

 3 FIG.3:(color online) Left and right sides refer respectively to the mean charge of the heaviest fragment of partitions, < Z1 >, and to the generalized asymmetry in charge of the fragment partitions without the heaviest one, AZ\{Z1}, (see text) as a function of the reduced fragment mutiplicity, M f rag /< Zs >, for different total excitation energy per nucleon of the sources. Full squares, open and full circles stand respectively for QF sources and QP sources produced at 80 and 100 MeV/nucleon incident energies.

TABLE I :

 I

Selected excitation energy bins for the comparison between QF and QP sources. The five columns stand for the five bombarding energies for producing QF sources (fist line). Second and third lines indicate the mean value and root mean square of excitation energy (E * ) distributions for QF sources.


Sophie Docteur

Florence
email: florence@u707.jussieu.fr

Pierre Docteur

Chauvin
email: chauvin@u707.jussieu.fr

Migration, health and access to care in Mayotte Island in 2007: lessons

Keywords: Health, Migration, Social factors, Primary care

recours aux soins à Mayotte en 2007 : enseignements d'une enquête représentative en population générale.

RESUME

Position du problème. Mayotte est une collectivité départementale française de l'Océan Indien qui conjugue de nombreuses spécificités : développement sanitaire récent, pression migratoire importante, accès aux soins gratuit pour les résidents légaux et payant pour les étrangers en situation irrégulière, absence de plusieurs prestations sociales, systèmes d'information sanitaire inexistants. Pour la première fois, une enquête représentative en population générale a permis de décrire les liens entre migration et santé et d'étudier les recours aux soins en fonction de la nationalité.

Méthodes Enquête transversale représentative en population générale conduite auprès d'un échantillon aléatoire à 3 niveaux (zones géographiques, logements, personnes), comprenant 2105 personnes interrogées en français, shimaore ou kibushi (taux de réponse = 96%). Le questionnaire a été adapté au contexte de Mayotte par la réalisation d'une enquête qualitative préalable. Des analyses descriptives et des modèles de régression logistique ont été réalisés.

Résultats. Les étrangers représentent 40% de la population (dont 1/4 d'enfants nés à Mayotte) ; 80% sont en situation irrégulière alors que l'ancienneté médiane d'installation des immigrés étrangers est de 10 ans. Ils sont majoritaires chez les femmes, dans la population entre 20 et 35 ans et dans les zones les plus urbanisées. Les migrations sanitaires apparaissent très minoritaires : 11% des immigrés déclarent avoir migré ou s'être installés à Mayotte pour raisons de santé tandis que la majorité des motifs de migration est économique (50%) ou familiale (26%). La situation sociale des étrangers est plus précaire, leur état de santé ressenti moins bon que les Français et leur accès aux soins est également jugé plus difficile. La fréquence de consultation durant l'année précédente ne diffère pas selon la nationalité contrairement aux modalités de recours aux soins ; les étrangers consultent moins en médecine libérale et plus en médecine traditionnelle.

Conclusion.

Dans ce « territoire frontière » de la République, la population étrangère est nombreuse et installée depuis dix ans en moyenne. Les motifs de migration sont principalement économiques et familiaux. Les étrangers relatent des obstacles dans l'accès aux soins liés à la précarité de leurs conditions de vie et à l'absence de titre de séjour. Depuis 2006 et l'intensification des politiques françaises de contrôle de l'immigration, la moitié des reconduites à la frontière de personnes en situation irrégulière effectuée chaque année sur le territoire de la République française ont eu lieu à Mayotte [5].

Le système sanitaire repose sur un maillage associant 19 dispensaires publics (dont 3, intercommunaux, sont ouverts 24h/24), 25 centres de protection maternelle et infantile (PMI) et le Centre hospitalier de Mayotte (CHM) [6]. Le secteur libéral reste très restreint. Les soins médicaux concilient donc une approche privilégiant les soins de santé primaires, un équipement hospitalier performant et une qualité des soins médicaux qui se veut proche des standards métropolitains.

Pour autant, la densité médicale y reste très faible : en 2007 on dénombrait 110 médecins pour 100 000 habitants à Mayotte, contre 239/100 000 à la Réunion et 338/100 000 en métropole [START_REF]Conseil national de l'ordre des médecins[END_REF]8].

Jusqu'en 2004, l'accès aux soins était gratuit pour tous, sans condition. Depuis la convergence de la Caisse de Sécurité sociale de Mayotte (CSSM) vers le modèle métropolitain [START_REF] Quatresous | Épidémie de béribéri infantile à Mayotte : rapport d'investigation[END_REF], a été créée une distinction entre les affiliés pour lesquels les soins restent gratuits et les non affiliés qui doivent payer un forfait dont les tarifs ont été fixés localement par l'Agence Régionale d'Hospitalisation (ARH) Réunion Mayotte, la Direction des affaires sanitaires et sociales (DASS) et le CHM [10]. Il est, par exemple, de 10 € pour une consultation au dispensaire et de 350 € pour le forfait accouchement. Les affiliés sont, en droit, tous les résidents réguliers de Mayotte quelle que soit leur nationalité -mais ils doivent avoir leur état civil à jour et posséder un compte en banque (les Français métropolitains et réunionnais restant généralement affiliés à leurs caisses d'Assurance maladie de droit commun « hexagonal ») -et les non affiliés sont les personnes en situation irrégulière de séjour (il n'y a pas d'Aide Médicale d'Etat à Mayotte). En dehors d'enquêtes spécifiques conduites notamment à l'occasion de l'épidémie de Béribéri en 2004 [START_REF] Quatresous | Épidémie de béribéri infantile à Mayotte : rapport d'investigation[END_REF] et de Chikungunya en 2005 [11], peu de données socio-sanitaires systématiques ou représentatives sont disponibles sur l'île [12], en particulier sur la consommation de soins des étrangers à Mayotte.

Cette situation nourrit bien des préjugés sur la situation sanitaire de ces étrangers, leur « charge » pour le système de soins et le poids des migrations sanitaires des Comoriens vers Mayotte [5].

Les objectifs de notre enquête conduite en 2007 étaient les suivants : (A) décrire la part de la santé et du recours aux soins dans les motivations et les raisons de migration de la population immigrée;

(B) comparer la situation sanitaire et les recours aux soins des Français et des étrangers, notamment le suivi de la dernière grossesse ; (C) décrire les principaux obstacles à l'accès aux soins de la population et identifier ses principaux déterminants en fonction de la nationalité.

MATERIELS ET METHODES

Une enquête transversale par échantillonnage a été conduite en population générale d'octobre à novembre 2007 sur l'ensemble de l'île. La population de référence était constituée de toutes les personnes résidant à Mayotte depuis au moins 6 mois ou envisageant au jour de l'enquête d'y séjourner pour au moins cette durée. Un échantillonnage aléatoire, stratifié par zone géographique (urbaine/rurale), a été réalisé à trois degrés : 20 zones géographiques de 100 à 200 logements ont été tirées au sort, puis 30 logements par zone et 2 individus par logement (un de moins de 15 ans, un de plus de 15 ans). La base de sondage disponible était la base des îlots de recensement constituée par l'antenne locale de l'INSEE en septembre 2008. Le questionnaire a été établi à partir de versions abrégées d'enquêtes préalablement conduites par l'équipe porteuse du projet (en région parisienne [13,14] notamment, mais également à Madagascar [15]) et a été adapté au contexte de Mayotte grâce à la réalisation préalable d'une enquête qualitative exploratoire. Il

RESULTATS

DISCUSSION

Les deux sujets abordés dans cette étude -le lien entre migration et santé et les différences d'accès aux soins selon la nationalité -encore peu abordés dans la littérature [START_REF] Mladovsky | A framework for analysing migrant health policies in Europe[END_REF][START_REF] Uiters | Differences between immigrant and non-immigrant groups in the use of primary medical care; a systematic review[END_REF],

notamment en France où les études sur les migrants ou les étrangers sont rares [START_REF] Chenu | Le repérage de la situation sociale[END_REF][START_REF] Darmon | An overview of the health status of migrants in France, in relation to their dietary practices[END_REF]. Mayotte ne fait pas exception à cette rareté alors même que sa situation géographique, démographique et politique rend ces questions prégnantes. Les différentes études internationales sur la santé et l'accès aux soins des immigrés [START_REF] Ellen | Differences between immigrant and non-immigrant groups in the use of primary medical care; a systematic review[END_REF] ont des conclusions divergentes. En effet plusieurs facteurs entrent en jeu dans le processus de migration (pays d'origine, de destination, date de migration) et jouent un rôle sur la morbidité, la mortalité des immigrés [START_REF] Mckay | Migration and Health: a review of the international literature[END_REF].

Avec un taux de participation important et une procédure de sondage à 3 niveaux ayant permis d'interroger de façon aléatoire 2,7% des ménages de Mayotte interrogés, notre échantillon possède une bonne représentativité, notamment par comparaison avec les derniers RGP [17,18].

Cette étude montre la forte proportion d'étrangers dans la population résidente de Mayotte. Les étrangers représentent en effet 40% de la population, dont 1/4 d'enfants nés à Mayotte .Ils sont majoritaires chez les femmes, les adultes jeunes et en zone urbaine. Cette situation plaide, en ellemême, en faveur de la prise en compte, dans la conception des services de santé comme dans la formation des personnels soignants, de la santé de ces étrangers [17]. La grande majorité de ces étrangers (80%) est en situation irrégulière, alors que prés de la moitié des immigrés réside depuis plus de 10 ans sur l'île. Pour la période récente, l'accroissement du nombre d'étrangers semble être beaucoup plus le fait des naissances à Mayotte des enfants nés de parents étrangers (résidant pour la plupart depuis plusieurs années sur l'île) que d'une augmentation de l'installation de nouveaux immigrants. En effet, nos résultats montrent que le nombre d'immigrants diminue très fortement depuis 5 ans. En revanche, la part des personnes en situation irrégulière parmi les étrangers, elle, ne cesse d'augmenter depuis les restrictions au droit de séjour des étrangers introduites à la fin des années 1990.

Les principales limites de cette étude résident dans le caractère déclaratif des données collectées.

Les biais de classement selon la nationalité ou la situation administrative de séjour ont été minimisés par l'information préalable des populations au sujet de cette enquête. De même, pendant la formation des enquêteurs, une insistance particulière a été portée sur la présentation de l'étude soulignant l'importance de collecter des données représentatives de l'ensemble de la

2 ,

 2 Santé . Migration . Facteurs sociaux . Soins primaires INTRODUCTION Mayotte est une des quatre îles de l'archipel des Comores situées dans le canal de Mozambique, entre Madagascar et l'Afrique. D'une superficie de 374 km elle est située à 8000 Km de Paris. Territoire français depuis 1841, Mayotte a choisi en 1974 de demeurer au sein de la République à l'issue de la consultation des populations des Comores sur l'indépendance. Depuis, son statut a évolué de Territoire d'Outre Mer (TOM) en Collectivité d'Outre Mer, puis, en 2001, en statut exceptionnel de Collectivité Départementale d'Outre Mer [1]. Depuis le référendum de mars 2009, elle est appelée à devenir un Département d'Outre Mer (DOM). Actuellement, l'île compte 186 452 habitants [2] et sa situation démographique est marquée par une croissance forte et une population très jeune. Carrefour de civilisations, la société mahoraise est qualifiée par certains de «microcosme de l'Océan Indien occidental» [3]. L'islam est la religion majoritaire et les langues principales sont le shimaore, le kibushi et le français. Mayotte connaît un important mouvement d'immigration en provenance des Comores que l'accession à l'indépendance des trois îles de l'archipel n'a pas interrompu. Ces mouvements, dus à l'étroitesse des liens séculaires, géographiques, familiaux et culturels, ont sans doute été renforcés à mesure que la différence des niveaux de développement entre Mayotte et l'Union des Comores (anciennement République fédérale islamique des Comores) se creusait [4]. En 1995, la mise en place d'un visa d'entrée à Mayotte pour les Comoriens conduit au développement d'une immigration clandestine et contribue à fixer sur l'île les Comoriens en situation irrégulière de séjour.

  contenait 3 parties : un questionnaire ménage, un questionnaire pour les personnes âgées de 15 ans et plus et un questionnaire pour les moins de 15 ans. Les items recueillis concernaient l'ensemble des caractéristiques connues pour interagir avec l'accès aux soins : les caractéristiques sociodémographiques (âge, sexe, composition du ménage, situation familiale, nationalité, statut de résidence vis-à-vis du droit français, lieu de naissance et lieu de naissance des parents, ancienneté d'installation à Mayotte comptée à partir de la première installation en cas d'immigrations successives, langues parlées), socioéconomiques (niveau d'éducation, emploi, source et montant du revenu du ménage, situation financière ressentie, caractéristiques et équipement du ménage, couverture sociale) et sanitaires (état de santé ressenti, handicap, maladie chronique, fréquence de consultation de chaque types de prestataires de santé médicaux, paramédicaux et soignants traditionnels, suivi de la dernière grossesse, obstacles et renoncement aux soins). Les raisons de migration vers Mayotte ont été recherchées de 3 façons chez les immigrés adultes : les raisons d'immigrer (« pourquoi êtes vous venus ? »), les raisons de s'installer (« pourquoi êtes vous restés ? ») et, chez les patients déclarant être atteints de maladies chroniques, la part de ceux dont le traitement ou le suivi médical avait été, au moins partiellement, un motif d'installation (« aviez-vous -et le saviez vous-un de ces problèmes avant de venir à Mayotte ? » et si oui « vous êtes-vous installé à Mayotte pour traiter ce problème? »). Les questionnaires ont été administrés au domicile des personnes en français, en shimaore ou en kibushi. La durée de passation moyenne pour un logement était d'une heure environ. La base de données a été redressée a posteriori sur la taille des ménages puis calée sur la distribution par sexe et âge de la population mahoraise au dernier recensement général de la population (RGP) disponible [16]. Les résultats communiqués ici (notamment les effectifs et les proportions) prennent en compte les pondérations ainsi effectuées. Une analyse descriptive de la population d'étude a d'abord été conduite en fonction de la nationalité et du statut migratoire afin de comparer les caractéristiques des étrangers et des français, ainsi que des migrants (nés hors de Mayotte) et des non migrants (nés à Mayotte). Quatre groupes de population ont ainsi été définis : la population française non immigrée constituée des Mahorais et des enfants des métropolitains et Réunionnais ayant migré à Mayotte, la population étrangère immigrée, la population étrangère née à Mayotte, la population française immigrée constituée de la population métropolitaine et réunionnaise et de la population d'origine étrangère ayant acquis la nationalité française. Dans la suite de l'article, nous nommerons « étrangère » une personne n'ayant pas la nationalité française au jour de l'enquête (quelle soit née en dehors ou à Mayotte) et « immigrée » (au même sens que l'Insee) une personne née étrangère à l'étranger et résidant à Mayotte (quelque soit sa nationalité actuelle).. Les populations étrangères et immigrées ne se confondent pas totalement : un immigré n'est pas (plus) nécessairement étranger et certains étrangers sont nés Mayotte (essentiellement des mineurs). Les associations univariées entre les variables d'intérêt (recours aux soins, suivi de la dernière grossesse, difficultés pour consulter un médecin) et les variables indépendantes (âge, sexe, nationalité, légalité de séjour, affiliation à la sécurité sociale, niveau d'étude, activité, revenu par UC,…) ont été étudiées à l'aide du test du Chi2. Des analyses multivariées ont été réalisées pour le fait d'avoir accouché l'année précédant l'enquête et le fait de déclarer des difficultés pour consulter un médecin. Toutes les variabes associées aux variables d'intérêt avec un degré de signification p <= 0,20 ont été incluses dans des modèles de régression logistique puis sélectionnées avec une procédure descendante pas à pas. En analyse univariée, les risques relatifs ont été calculés avec leur intervalle de confiance à 95%. En analyse multivariée, les forces d'association sont estimées par le calcul d'un Odds Ratio (OR) et de son intervalle de confiance à 95% (IC95%). Toutes ces analyses ont pris en compte les pondérations mentionnées ci-dessus. Les analyses statistiques ont été réalisées à l'aide du logiciel SAS ® (SAS Institute, Cary, NC, USA).

  population vivant sur l'île. Dans cette optique, les enquêteurs étaient d'origines diverses, permettant au maximum d'acquérir la confiance des enquêtés. Source également de biais de classement, certaines personnesnotamment les femmes concernant le suivi de grossesse -ne sont pas forcément très au fait de la qualification précise du soignant qui les examine. Néanmoins, on peut supposer que, en cas de doute ou d'ignorance sur cette qualification, les personnes jugent plus volontiers qu'elles ont été reçues par un médecin et les écarts observés sont, de ce fait, plutôt minimaux. Pour des raisons pratiques (contraintes financières et matérielles des temps de passation du questionnaire), certaines données n'ont pu être recueillies. Par exemple, les questions sur la vie génitale des femmes ne permettent pas de comparer la prise en charge de l'ensemble des grossesses, ni celle de la dernière grossesse ajustée sur la parité et son ancienneté. Une autre limite, inhérente à la définition de la population de référence de notre enquête (les personnes résidentes pendant au moins 6 mois) est que cette étude ne permet pas d'estimer la fréquence des migrations pendulaires (pour une durée inférieure), ni les motifs, l'état de santé et les recours aux soins de ces migrants de courte durée. Notons néanmoins que l'extrapolation du nombre de grossesses dans notre population de référence aboutit à une estimation de 8000 naissances annuelles ; ce qui correspond au nombre de naissances rapporté par le système de soins de Mayotte. Ainsi, le nombre d'accouchements qui seraient le fait de la population non enquêtée, autrement dit le nombre de femmes étrangères venant accoucher à Mayotte et repartant ensuite rapidement (de leur fait ou non), apparaît très faible.Les principales raisons à l'immigration et à l'installation des étrangers à Mayotte sont d'ordre économique (50%) ou familiale (26%

Figure 1 :

 1 Figure 1 : Répartition de la population de Mayotte en fonction de la nationalité et du statut migratoire (source : enquête DRSM).

  partir de la distribution de la population résidente à Mayotte selon la nationalité et le statut migratoire, la Figure1montre 5 sous-groupes de population : les Mahorais (n=1143, 54,4%) dont 0,2% d'enfants nés à Mayotte de métropolitains ou de Réunionnais, les étrangers immigrés 0% en ce qui concerne la venue et 49,6% en ce qui concerne l'installation) ou familiales (26,8% et 28,3% respectivement). La migration pour raison de santé est citée en 3ème position par ordre de fréquence décroissant (8,9% ; IC95% : 6,3-11,6). L'installation pour raison de santé est moins une fois renoncé à des soins contre seulement 10,9% dans la population française (RR = 3,47 ; IC95% : 2,74-4,41). De la même façon, 18,8% de la population de nationalité étrangère avec des enfants avaient au moins une fois renoncé à des soins pour leurs enfants

	multivariée, seul le fait d'être en couple est lié statistiquement au fait d'avoir accouché l'année
	précédente.
	Suivi de la dernière grossesse
	(n=611, 29,1%), les étrangers nés à Mayotte (n=234, 11,1%), les français migrants (métropolitains citée en 4ème position par ordre de fréquence décroissant (4,0% ; IC95% : 2,4-5,6) parmi les contre 3,39% de la population de nationalité française (RR = 6,77 ; IC95% : 3,58-10,07).
	et Réunionnais, n=56, 2,6%) et les étrangers immigrés ayant acquis la nationalité française (n=57, motifs d'installation, derrière l'avenir des enfants (8,3% ; IC95% : 6,1-10,4) et juste devant les Sur l'ensemble des femmes ayant eu une grossesse à Mayotte (n=474), 10,7% n'ont bénéficié
	2,8%). Cette répartition est très similaire à celle du RGP [18] seuls les métropolitains et les études (4,0% ; IC95% : 1,5-6,5). Enfin, 4,6% (IC95% : 2,8-6,4) des immigrés se sont installés pour d'aucun suivi, 2,2% n'ont eu qu'une ou deux consultations prénatales par un médecin ou une sage-
	Réunionnais sont un peu moins représentés dans notre échantillon. traiter un problème de santé chronique. Au total, 11,3% (IC95% : 8,5-14,2) de la population femme et 86,1% déclaraient un suivi « régulier » (défini par au moins une consultation par
	Parmi les étrangers (n=845), 17,8% étaient en situation régulière de séjour et 82,2% en situation immigrée ont migré et/ou se sont installés pour raisons de santé et/ou pour traiter une maladie trimestre). Parmi ces dernières, 25,5% l'ont été par un médecin en dispensaire et 12,3% par un
	irrégulière. Ils étaient essentiellement de nationalité comorienne (96,8%). Parmi la population chronique connue. médecin libéral.
	population étrangère, p<0,0001), pour les consultations d'infirmiers (13,1% vs. 9,6%, p=0,004) et
	de kinésithérapeutes (2,6% vs. 1,2%, p=0,03). En ce qui concerne le recours à la médecine
	traditionnelle, on ne retrouve pas de différence pour les recours à 2 types de guérisseurs : fundi
	Obstacles aux soins
	(12,6%) et mwalimu (1,9%) ; mais on en retrouve pour les consultations des herboristes (8,0%
	dans la population française versus 19,4% dans la population étrangère, p<0,0001) et des Dans notre population d'enquête, 70,3% des personnes interrogées déclaraient rencontrer des
	masseuses (12,3% vs. 23,7%, p<0,0001), ainsi que pour la prise de traitements traditionnels obstacles pour se soigner : 86,1% (728/845) de la population étrangère étaient dans cette
	(14,8% vs. 21,8%, p<0,01). situation contre 59,7% (750/1256) de la population de nationalité française. Les principaux
	obstacles pour consulter différaient selon la nationalité. Chez les étrangers, les problèmes
	Parmi les femmes de l'échantillon de 15 à 49 ans (n=544), 17,7% déclarent avoir été hospitalisées
	Description de la population financiers (78,7%) et la peur d'être arrêté (41,3%) étaient cités en premier. Chez les Français, il
	durant l'année précédente. Les deux tiers (64,8%) de ces hospitalisations étaient motivées par un
	accouchement. En analyse univariée, parmi les facteurs sociodémographiques (âge, région, Au total, 1246 ménages ont été inclus et 2105 individus interrogés. Les logements vacants (19,3% De fait, les inactifs représentent un groupe important et hétérogène et comprend des personnes en s'agissait d'abord de l'attente en consultation (61,1%) puis des problèmes financiers (29,1%). De la
	nationalité, légalité de résidence, statut marital) et économiques (revenu du ménage par unité de de l'échantillon initial de logements) ont été remplacés à l'intérieur de chaque zone tirée au sort par recherche d'emploi. même façon, 57,8% de la population de nationalité étrangère trouvaient plutôt difficile de consulter
	de nouveaux logements eux-mêmes choisis aléatoirement. La proportion de réponse a été de consommation, situation financière ressentie) étudiés, le fait d'être en couple, l'irrégularité de Motifs d'immigration un médecin contre 33,2% dans la population française (p<0,001). En analyse multivariée, les
	résidence et l'inactivité sont associées au fait d'avoir accouché l'année précédente. En analyse

96,0%, soit 4,0% de personnes absentes à l'issue des 3 visites (dont une en soirée) ou ayant refusé de répondre.

A immigrée (n=667), la distribution de l'ancienneté de migration montre que la moitié s'est installée à Mayotte depuis 10 ans ou plus (médiane : 10 ans, interquartile : 7 -15 ans). On observe une nette diminution des installations au cours des 5 dernières années (16,7% de l'ensemble des immigrés), encore renforcée depuis 2005 (5,6%). Plus la migration est ancienne, plus la proportion d'immigrés en situation régulière est importante. Les immigrés installés depuis plus de 10 ans ont ainsi 7 fois plus de chance d'avoir obtenu un titre de séjour ou la nationalité française que ceux installés depuis moins longtemps (RR = 6,91 ; IC95% : 4,24 -11,33) tandis que ceux installés depuis moins de 5 ans ne sont que 7,2% à être en situation régulière. A contrario, parmi les immigrés depuis 10 ans ou plus, 57,9% sont toujours en situation irrégulière. Le tableau 1 montre que les caractéristiques sociodémographiques des Français et des étrangers sont différentes. La population étrangère est plus féminine, jeune, urbaine, non francophone, inactive, précaire et en moins bon état de santé. Les chômeurs ou demandeurs d'emploi sont extrêmement difficiles à dénombrer : le terme n'existe pas en langue locale et la reconnaissance de ces statuts ne concernent qu'un tout petit nombre de personnes

[8]

(les affiliés à la Caisse d'assurance chômage, opérationnelle depuis janvier 2006, ne représentent qu'une faible part des chômeurs). Interrogés sur les raisons principales de venue et d'installation sur l'île de Mayotte (Figure 2), les immigrés de plus de 15 ans (n=602) déclarent le plus souvent que celles-ci sont économiques (49,Recours aux soins Les recours aux soins de la population au cours de l'année précédant l'enquête ne diffèrent pas en fonction de la nationalité, que ce soit en termes d'hospitalisation (10,7%), de consultations médicales au dispensaire (56,2%), à l'hôpital (16,9%) ou aux Urgences (11,2%), de consultations chez le dentiste (8,0%) ou de consultation d'un pharmacien (6,5%). Ils diffèrent en revanche pour les consultations en médecine libérale (22,2% dans la population française versus 13,8% dans la Les femmes de nationalité étrangère avaient 1,20 (IC95% : 1,11-1,29) fois plus de chance d'avoir été suivies au moins une fois par un médecin ou une sage femme pendant leur grossesse (96,2% vs. 80,3%). En revanche, il n'y avait pas de différence significative concernant le suivi régulier par un médecin (en dispensaire ou en ville) : RR = 1,04 ; IC95% : [0,82-1,33]. Si l'on ne considère que le suivi régulier par un médecin libéral, les femmes de nationalité étrangère avaient 2,38 (IC95% : 1,39-4,17) fois moins de chance d'avoir bénéficié d'un tel suivi. Parallèlement, le suivi par un soignant traditionnel était plus élevé chez les femmes de nationalité étrangère (54,2% vs. 35,1% ; p<0,0001). personnes qui déclaraient avoir des difficultés pour consulter un médecin étaient les personnes avec un moins bon état de santé perçu, en situation irrégulière de séjour et avec un fort sentiment d'isolement (Tableau 3). Près d'un tiers (29,9%) de la population de nationalité étrangère déclarait avoir au

  ). En regard, les migrations pour raisons de santé apparaissent très minoritaires, ne représentant que 11%. Ce chiffre contredit l'idée généralement véhiculée d'une immigration sanitaire importante[5,[START_REF] Torre | Rapport d'information sur l'immigration clandestine à Mayotte[END_REF][START_REF] Hyest | Rapport d'information à la suite d'une mission d'information effectuée à Mayotte du 1er au 6 septembre 2008[END_REF][START_REF] Bourgeon | L'immigration clandestine de patients comoriens à Mayotte : quels enjeux éthiques pour quels enjeux politiques ?[END_REF]. Cette faible proportion de migrants venus pour se soigner est également retrouvée en Europe dans une enquête récente réalisée auprès d'immigrés en situation irrégulière par l'Observatoire européen sur l'accès aux soins de Médecins du Monde[START_REF] Chauvin | Access to healthcare for the undocumented migrants in 11 European countries[END_REF] qui retrouve 6% d'immigrés sans autorisation de séjour venus en Europe pour des raisons de santé. De son côté, le rapport d'information du Sénat sur l'immigration clandestine à Mayotte[START_REF] Hyest | Rapport d'information à la suite d'une mission d'information effectuée à Mayotte du 1er au 6 septembre 2008[END_REF], estime que l'immigration clandestine à Mayotte en 2007 a généré 16 millions d'euros de coûts de fonctionnement pour le CHM sur un budget total de 114 millions d'euros : soit 14% pour un tiers de la population. De même, les nombreux accouchements de femmes comoriennes -si souvent mis en avant par les décideurs sur l'île -ne sont que les conséquences logiques de la structure de la population étrangère irrégulière composée principalement de femmes en âge de procréer (en particulier dans les zones les plus urbanisés) dont la fécondité estsans doute aussi -plus élevée que celle des Mahoraises (d'après le RGP, l'indice synthétique de fécondité des femmes nées à l'étranger est de 6,4 contre 3,4 pour les mères nées en France, données Insee 2007, à paraître).A Mayotte, la situation sociale des étrangers est plus précaire et leur état de santé ressenti est moins bon que celui des Français. Bien que les modalités de recours aux soins étaient différentes selon la nationalité (les étrangers consultaient moins en médecine libérale et avaient aussi plus souvent recours aux soignants traditionnels), aucune différence significative en termes de La mise en place de la Sécurité sociale constitue sans doute une avancée dans la mise en place du droit commun à Mayotte mais elle participe également à la mise à distance du système de soins des personnes non affiliées, faute de dispositifs complémentaires.L'importance numérique de la population non affiliéeet non affiliable à ce jour -à la Sécurité sociale (une population pourtant souvent résidente depuis de très nombreuses années) comme les obstacles financiers (rapportés par les étrangers mais aussi dans la population française) plaident en faveur de la mise en place sur l'îlecomme c'est la cas en métropole ou dans les départements

	comparative et médicalisée nécessiterait d'être conduite auprès des patientèles des dispositifs de
	soins.
	Concernant 7 personnes sur 10 (notamment, mais pas seulement, les personnes cantonnées dans
	la clandestinité), les obstacles d'accès aux soins s'accompagnent de risques sanitaires individuels
	et collectifs. La difficulté d'accès aux soins et l'isolement risquent en effet d'aggraver des
	pathologies banales (maladies chroniques ou infectieuses) ou d'être à l'origine du développement
	fréquence de consultation au cours des 12 derniers mois n'a été mise en évidence malgré les différences rapportées en terme d'état de santé ressenti et d'accessibilité. Cela s'explique pour deux raisons. D'une part, parce que le recours de la population française et bénéficiaire de l'Assurance maladie reste assez faible en comparaison de celui observé en métropole. Ainsi, par exemple, la proportion de personnes ayant recours au moins une fois à un médecin en un an est d'épidémie [31-34]. De manière générale, l'enquête qualitative conduite préalablement à cette étude a montré que les
	de 83,6% en France métropolitaine (en 2006) [29] contre 73,1% à Mayotte. D'autre part, le recours personnes interrogées à Mayotte, qu'elles soient autochtones ou immigrées, apparaissent
	de la population étrangère n'est pas si mauvais : les étrangers en situation irrégulière payent leurs extrêmement mal informées quant à l'évolution du système de santé et d'Assurance maladie et
	consultations (les recettes en 2007 tirées de ces provisions sont évaluées à environ 2 millions particulièrement démunies devant la complexité et la nouveauté des nouvelles règles établies en la
	d'euros [30]) et ils consultent également plus souvent la nuit pour éviter les barrages de police, ou matière. De notre point de vue, et compte tenu des résultats de l'enquête en population,, tous les
	de façon préférentielle dans certains dispensaires où l'application de l'obligation de paiement est acteurs (soignants, gestionnaires et usagers) du système de soins auraient tout à gagner à ce que
	moins systématique. Les étrangères avaient souvent eu au moins un contact avec les structures ce défaut manifeste d'information -avec les fausses croyances, les rumeurs et la part d'arbitraire
	de soins pour le suivi de leur grossesse, mais ce suivi n'était pas forcément complet, ni réalisé par qu'il implique -soit comblé. En regard, même si certaines améliorations ont été réalisées ces
	un médecin. Pour étudier plus avant la question des délais et des retards aux soins éventuels des dernières années [35], il apparaît également important qu'un système d'informations socio-
	étrangers en situation irrégulière et leurs conséquences sanitaires, une étude représentative,

d'outre merde Permanences d'accès aux soins (dispositifs PASS hospitaliers), de l'AME, mais aussi de la Couverture Maladie Universelle (CMU) pour les personnes affiliées à la CSSM avec de faibles revenus. L'accès au statut département d'outre mer de l'île, prévu pour 2011, devrait accélérer ces mises en place. Enfin le 3 ème obstacle cité en termes de fréquence, le délai d'attente en consultation, doit inciter les services de santé à rentrer dans une dynamique d'amélioration de la qualité des services rendus pour diminuer ces délais.

sanitaires fiablereposant sur les structures socio-sanitaires de l'îlepuisse être développé à Mayotte, pour mieux évaluer et planifier les demandes de soins mais aussi pour alerter sur l'état de

Tableau 1 : Principales variables sociodémographiques selon la nationalité

  les chômeurs ont été pris en compte selon le secteur d'emploi de leur dernier emploi

	Figure 2 :
		Français	Etrangers	p
		(n =1260)	(n =845)
	Sexe :
	Masculin	54,5% (	43,6%	<0.0001
	Age :
	0-15 ans	50,7%	37,2%
	16-30 ans	21,4%	38,5%
	31-45 ans	14,5%	19,0%	<0.0001
	46-60 ans	8,7%	3,8%
	Plus de 60 ans	4,7%	1,4%
	Région :
	Urbain	32,8%	68,2%	<0.0001
	Maîtrise du français :
	Pas du tout, très peu	34,1%	65,9%	<0.0001
	Niveau d'études
	Jamais scolarisé	27,6%	41,7%
	Primaire	15,0%	27,0%	<0.0001
	Collège	20,9%	22,6%
	Lycée et supérieurs	36,6%	8,6%
	Statut d'emploi*
	Salarié de la fonction publique	30,4%	2,3%
	Secteur privé (indépendants ou salariés)	17,4%	14,2%	<0.0001
	Secteur informel	0,7%	16,3%
	Inactif	24,2%	57,6%
	Etudiant	24,6%	9,0%
	Retraité	2,7%	0,6%
	Activité :
	Travail ou font des études	64,0%	28,1%	<0.0001
	Ressources du mois dernier :
	< 142 euros	38,8%	60,7%	<0.0001
	Situation financière ressentie :
	« Pas assez d'argent pour vivre »	27,5%	59,7%
	« Se prive beaucoup »	57%	35,1%	<0.0001
	« Suffisamment d'argent pour vivre »	15,5%	5,1%
	Etat de santé ressenti :
	Bon ou très bon	89,0%	74,7%	<0.0001
	Déclaration de maladie chronique
	Oui	18,5%	24,2%	0,0019
	Handicap
	Fortement limité	3,4%	3,1%
	Limité	10,8%	10,0%	0,80
	Pas limité	85,8%	86,8%
	Isolement
	Oui	14,2%	30,1%	<0.0001
	Affiliation a la CSSM :
	Oui	89,9%	17,7%	<0.0001
	Source : Etude DSRM, Octobre 2007, Mayotte

*

Motivations de migration et d'installation des immigrés de plus de 15 ans (source : enquête DRSM).

	Tableau 2:
	60%
	50%	49,4%	49,7%
	40%				migration	installlation
	30%		26,4% 28,1%
	20%
	10%			8,0%	8,6%	8,8%
				2,2%	5,3%	3,9%	2,5%	3,8%	1,5%	0,3%
	0%
		Economiques Familiales	Avenir des	Autres	SANTE		Etudes	Politiques
				enfants	raisons

Facteurs associés avec le fait d'avoir des difficultés pour consulter un médecin (analyse multivariée).

		% dans la	% chez
		population	les cas	OR*	[IC 95% ]
		(n=1241)	(n=660)
	Bonne santé perçue
	Oui	78,4	61,5	ref.
	Non	21,6	38,5	+++
	Situation légale de résidence
	Régulière	64,1	51,2	ref.
	Irrégulière	35,9	48,8	2,11	[1,26 -3,53]
	Isolement
	Oui	21,4	27,9	ref.
	Non	78,6	72,1	2,05	[1,27-3,34]

*ajusté sur l'âge, le sexe, le niveau d'étude, le revenu par unité de consommation du ménage, l'activité et la situation financière ressentie