Mireille Fouquet

Pierrick Gaudry

Robert Harley

An extension of Satoh's algorithm and its implementation

We describe a fast algorithm for counting points on elliptic curves de ned over nite elds of small characteristic, following Satoh. Our main contribution is an extension to characteristics two and three. We give a detailed description with the optimisations necessary for an e cient implementation. Finally we give the number of points we have computed on a \random" curve de ned over the eld F q with q = 2 8009 .

Introduction 1.A short history of point counting

The rst polynomial-time algorithm for counting points on elliptic curves over nite elds was described by Schoof in Sch85]. The basic idea was to nd the cardinality, modulo su ciently many small primes `using the `{torsion points and then to recover the exact result using the Chinese Remainder Theorem. To compute with `{torsion points, Schoof suggested doing polynomial arithmetic modulo the `{division polynomials.

The time required for point-counting over F q with Schoof's algorithm is O(log 5+" q) with asymptotically fast algorithms for arithmetic (or O(log 8 q) with na ve arithmetic).

To reduce the run-time, in large characteristic, Elkies Elk98] and Atkin Atk92] proposed replacing the `{division polynomials with lower degree ones found using the factorization of modular polynomials. In this way they reduced the degree from O(`2) to O(`) yielding the so-called SEA algorithm (see Sch95]). The improved run-time, under reasonable hypotheses, is O(log 4+" q) (or O(log 6 q)).

Further work by Morain Mor95a], M uller M ul95], Dewaghe Dew98] and others led to more e cient implementations of SEA. Morain carried out actual computations for q as large as 10 499 + 153 Mor95b]. Couveignes extended SEA to work in small characteristic Cou94], Cou96] and Lercier gave some improvements speci c to characteristic two Ler97], JL]. Vercauteren reached q = 2 1999 with an optimized implementation of these ideas Ver99].

Satoh's algorithm

Recently in Sat00], Satoh outlined a new algorithm with run-time O(log 3+" q) (or O(log 5 q)) for small xed characteristic p 5 and suggested that it could be extended to characteristics 2 and 3.

The basic idea of this new algorithm is completely di erent from SEA.

Satoh's algorithm (and our improvements of it) go out of their way to avoid computing completely and as a result the reader can skip this subsection on a rst reading.

First we de ne a particular lift of scalars from F q to Z q which respects the multiplicative structure.

De nition 2.4 The Teichm uller lift is the map ! : F q ! Z q de ned by: !(0) = 0 and for x non-zero, !(x) is the unique (q 1)-th root of unity in Z q such that (!(x)) = x.

The choice of name here is motivated by similarity with the Teichm uller character from p{adic analysis. Note that the Teichm uller lift can be computed using a Newton iteration based on the function f(x) = x q1 1.

Next we de ne a decomposition of elements of Z q which is close to the usual representation of Witt vectors 1 . See Chapter II of Ser68] for details on Witt vectors.

De nition 2.5 The semi-Witt decomposition of x 2 Z q is the unique sequence (x i ) i 0 of x i 2 F q such that x = P i 0 !(x i )p i . The coordinates x i can be computed one after another in the obvious way by x 0 = (x), then x 1 = ( x !(x 0 ) p ) and so on. Now we can de ne , the little Frobenius lifted from F q to Z q . Naturally it satis es ( ) = where is the little Frobenius on F q ; however is not a simple powering like .

De nition 2.6 The Frobenius : Z q ! Z q is as follows. For any x 2 Z q , let (x i ) i 0 be its semi-Witt decomposition. Then (x) is the element of Z q with decomposition (x p i ) i 0 . In other words it is P i 0 !(x p i )p i or equivalently P i 0 !(x i ) p p i .

Computations in Z p and Z q

For the purpose of computation one considers p{adic integers to some working precision, say n.

That is to say one represents a 2 Z p by an approximation a n 2 Z=p n Z and the ring operations are carried out modulo p n .

The inverse of an invertible a 2 Z p can be computed by the simple Newton iteration x

x x(ax 1), initialized with the inverse 1= (a) taken in F p .

Similarly, to represent a = a d 1 t d 1 + +a 0 2 Z q to some working precision n, one can store the sequence ( n (a d 1 ); : : : ; n (a 0 )). The space required is s = O(nd log p) and the time for addition or subtraction of two elements is O(s). The polynomial f(t) can be chosen to be sparse and with simple coe cients, so that the reduction modulo f(t) costs only a few additions and subtractions. Multiplication using na ve arithmetic would take O(s 2 ) whereas using Karatsuba's algorithm, in both the p{adic dimension and in the polynomial dimension, reduces it to O(s log 3= log 2 ).

One may also use fast multiplication algorithms. An asymptotically good method is to pack the coe cients into a single large integer and then use a fast algorithm for integer multiplication.

Each coe cient should be padded with zero bits to ll a eld of d2n log 2 p+log 2 de bits, so that the coe cients of the product polynomial can be recovered from elds in the integer product. Arithmetic with precision less than O(log d) takes negligible time so we can assume that the size `of the resulting integers is (nd log p). The fastest algorithm for multiplying large integers is Sch onhage's using Fast Fourier Transforms modulo Fermat numbers SS71] in time O(`log `log log `) for `bits.

In the following n = O(d) and hence multiplication can be done in time O(nd log d log log d), for xed p. Note that when n = (d) the same complexity can be attained, with better constant factors, by doing the FFT's directly on the polynomial representation. We found this approach to be the fastest in practice.

As before, the inverse of an invertible a can be obtained by a simple Newton iteration initialized with 1= (a). By varying the precision as described in the next section, division takes time proportional to multiplication.

Newton iteration

Several algorithms that are described in the present paper are based on Newton iteration. Therefore, we present it here.

Let R be an arbitrary p{adic ring. The following Newton iteration allows us to improve an approximate root of a polynomial. Given a good approximation to a root we can e ciently compute a better approximation, with approximately twice the precision.

It will be necessary to be quite careful about what we mean by \precision" throughout. We write p k j x when x 0 mod p k . In such a case p k x is in R. We write p k k x when p k j x but p k+1 -x. In such a case p k x is invertible.

Let x 2 R and f 2 R t]. Let k be such that p k k f 0 (x) and assume p n+k j f(x) for some n > k.

Under such conditions we will say that x is an approximate root of f known to precision n, in the sense that there exists an exact root y in R with x y mod p n . We rst prove a lemma showing how a Newton iteration improves a root known to precision n into one known to precision 2n k.

Lemma 2.1 (Quadratic convergence of Newton iteration) Let x 2 R and f 2 R t]. Let k be such that p k k f 0 (x) and assume p n+k j f(x) for some n > k. Let: = p k f(x) p k f 0 (x) and y = x : Then y x mod p n , p 2n j f(y) and p k k f 0 (y). Proof : It is clear that p n j so that y x mod p n . By Taylor expansion,

f(y) = f(x) f 0 (x) + 2 (x);
where (x) is a polynomial with coe cients in R. Since p 2n j 2 , we get f(y) f(x) f 0 (x) 0 mod p 2n .

Finally since y x mod p n , it follows that f 0 (y) f 0 (x) mod p n . Since p k k f 0 (x) and n > k we have p k k f 0 (y). Repeated application of this lemma gives rise to an algorithm to compute a root of a polynomial to any desired precision, from a su ciently precise initial root.

Procedure NewtonIterations Inputs:

A desired precision n.

A polynomial f 2 R t],

A starting solution x 0 2 R and an integer k with p k k f 0 (x 0 ) and p 2k+1 j f(x 0 ). Output: An approximate root x 2 R with x x 0 mod p k+1 and p n+k j f(x).

1. IF n k + 1 THEN y x 0 ; GO TO 5; 2. n 0 d n+k 2 e; 3. x NewtonIterations(n 0 ; f; x 0 ; k); 4. y x p k f(x) p k f 0 (x) ; 5. RETURN y.

For an e cient implementation, it is important to work with the lowest precision possible at each stage of the algorithm. In particular, one should reduce the precision of the Newton iterations in each recursive call. The depth of the recursion necessary to reach a desired precision n is log(n), so if all operations were done at precision n then the total time taken would be O(M(n) log(n)) where M(n) is the time for multiplication. By doing the top level iteration at full precision, the rst recursive call at roughly half precision, the second recursive call at one quarter precision and so on, the time taken is reduced to O(M(n)) total.

Furthermore, when calculating the improved root y = x f(x)=f 0 (x) in a Newton iteration, one can reduce the precision of some of the calculations by roughly half. The lowest required precisions are indicated next. We will write x + O(p n ) to denote any y x mod p n . For instance xy + O(p n ) can be understood to be the product xy computed with precision n.

When an element a 2 R is known to precision n then the product p k a is known to precision n + k, in the sense that p k (a + O(p n )) = p k a + O(p n+k ). Conversely when a is known to precision n and satis es p k j a, where k n, then p k a is known to precision n k. 3 Frobenius morphisms and the canonical lift

Frobenius morphisms on curves

Let E be a curve over the nite eld F q , where q = p d . As is well known, we can compute the order of E by computing the trace c of the q-th power Frobenius endomorphism on this curve. The number of points is then given by q +1 c. According to the Hasse-Weil bound, we have jcj 2 p q.

The p-th power Frobenius on F q can clearly be extended to map points (x; y) on E to points ( (x); (y)) on the conjugate curve E obtained by applying to the coe cients of E and in fact this map is a (purely inseparable) isogeny, also called the little Frobenius. Furthermore, the construction can be repeated giving an isogeny from E to E 2 and so on. Repeating it d times gives a cycle of isogenies which returns to the initial curve E. Writing E 0 for E, E d 1 for E , d 1 for the isogeny between them and so on we can draw the graph:

E 0 d 1 / / E d 1 d 2 / /
De nition 3.1 The q-th power Frobenius on E is the curve endomorphism F = 0 1 : : : d 1 .

Of course the action of F is trivial over F q but it is non-trivial in extension elds.

In the same manner, if we have a curve E over Z q , the little Frobenius on Z q can be extended to a map between E and the conjugate curve E . Repeating this operation d times, brings back to the initial curve, thus yielding another cycle of isogenies.

Canonical lifting of curves

First, we will recall some basic facts about modular equations. The modular equation p (X; Y ) is a symmetric polynomial of degree p+1 in each variable, with integer coe cients with the following property. Two elliptic curves E and E 0 de ned over F q , are related via a cyclic isogeny of degree ònly if `(j(E); j(E 0 )) = 0.

It satis es the so-called Kronecker relation:

p (X; Y ) (X p Y )(X Y p ) mod p:
The coe cients become rather large as p increases, so we just recall the modular equations 2 and 3 :

2 (X; Y ) = X 3 + Y 3 X 2 Y 2 + c 1 (XY 2 + X 2 Y ) c 2 (X 2 + Y 2 ) + c 3 XY + c 4 (X + Y ) c 5
where: c 1 = 1488; c 2 = 162000; c 3 = 40773375; c 4 = 8748000000; c 5 = 157464000000000 The following theorem, due to Lubin, Serre and Tate LST64], allows one to lift a curve E over F q to a curve E over Z q canonically, by lifting its j{invariant. The curve E is the unique lift of E having the same endomorphism ring.

3 (X; Y ) = X 4 + Y 4 X 3 Y 3 + d 1 (X 3 Y 2 + X 2 Y 3 ) d 2 (X 3 Y + XY 3 ) + d 3 (X 3 + Y 3 ) +d 4 X 2 Y 2 + d 5 (X 2 Y + XY 2 ) + d 6 (X 2 + Y 2 ) d 7 XY + d 8 (X + Y )
Theorem 3.1 (Lubin-Serre-Tate) Let E be a curve over F q with j{invariant j 2 F q n F p 2 , then there is a unique J in Z q such that p (J; (J)) = 0 and J j mod p;

and J is the j{invariant of the canonical lift E of E (de ned up to isomorphism).

It is possible to implement this theorem directly by lifting J with its conjugate (J). This is done by computing the Witt coe cients x n for n > 0. When the x i are known for 0 i < n, the equation p (J; (J))=p n 0 mod p yields a p{linear polynomial in the variable x n which can easily be solved. Unfortunately, computing the polynomial itself requires computations of and this is slow in practice. Furthermore, (d) such steps are required.

A much faster method is developed in the next sections using the whole cycle of J i 's. Indeed writing out all the equations p (J i ; J i+1 ) for 0 i < d produces an algebraic system over Z q without , which can be solved quickly by a O(log d) steps of a multi-variate Newton iteration. The cycle of lifted curves is:

E 0 d 1 / / E d 1 d 2 / / 1 / / E 1 0 / / E 0 E 0 d 1 / / E d 1 d 2 / / 1 / / E 1 0 / / E 0
Considering it as a whole yields the curve endomorphism F which is the lift of F: E

F / / E E F / / E
Now the dual of a little Frobenius isogeny is a (separable) isogeny ^ called the Verschiebung. Following Satoh we will work with the dual since, being separable, it can be manipulated easily via its kernel. By considering the duals, we go around the same cycles in the opposite direction:

E 0 ^ 0 / / E 1 ^ 1 / / ^ d 2 / / E d 1 ^ d 1 / / E 0 E 0 ^ 0 / / E 1 ^ 1 / / ^ d 2 / / E d 1 ^ d 1 / / E 0
We also get the dual curve endomorphism F = ^ d 1 ^ d 2 ^ 0 and its lift F.

E F / / E E F / / E

The main algorithm

The algorithm consists of two phases: lifting all the information we need to Z q with enough precision, and then recovering the trace with the help of these data.

Following Satoh we construct a cycle of j{invariants, using the Frobenius in F q , and then lift all of them simultaneously using a multivariate Newton iteration. In this manner we obtain all the conjugate J's in Z q without having to compute the Frobenius in Z q at all. Once that is done, we lift the curves one at a time by lifting their coe cients using (univariate) Newton iterations.

The isogenies ^ i and ^ i are separable of degree p, so they are determined by their kernels which have order p. Therefore lifting ^ i to ^ i will be done by lifting its kernel, which is a p{torsion subgroup.

We can lift the kernel either by lifting a single point using a Newton iteration, when p = 2 and p = 3, or by lifting a factor of the p{division polynomial with a more general Hensel lift, when p 5.

Procedure MainAlgorithm

Input: An elliptic curve E de ned over F q , with j(E) 6 2 F p 2 . Output: The trace of the curve E.

Lift each curve by lifting its coe cients;

4. Lift each curve's p{torsion subgroup.

5. Compute the trace from the lifted data.

Computing the trace

The aim here is to compute the trace of the Frobenius endomorphism F : E ! E. We assume that we have computed (a good approximation of) the canonical lift E of E. Since canonical lifting preserves the endomorphism ring, the trace of Frobenius is unchanged. Moreover the trace of an endomorphism is the same as the trace of its dual. We have Tr F = Tr F = Tr F: where F is the Frobenius on E and F is its dual. As explained above, the Frobenius F can be decomposed into the product of little Frobenius isogenies which cycle the curve E through its d conjugates, and similarly for the duals. Thus

Tr F = Tr ^ d 1 ^ d 2 ^ 0 :
The next step is to go to the formal groups of the curve E and its conjugates. Let us denote the local parameter X=Y of E by , and the local parameters of E i by i . Expressing the action of F on this parameter, we get the form

F( ) = X k 1 c k k ;
and Satoh's proposition 4.1 shows that the equation x 2 Tr ( F)x + q = 0 satis ed by F implies Tr ( F) = c 1 + q c 1 :

Thus, computing the rst coe cient c 1 is enough to solve the problem. The key point is that, since F is the composition of morphisms, it is possible to compute c 1 as the product of the rst coe cients in the expansions of the factors in the formal groups. More precisely, we can write ^ i : E i ! E i+1 on the formal groups as

^ i ( i ) = g i i + O( 2 i ): Then we have c 1 = Y 0 i<d g i ; and
Tr F Y 0 i<d g i mod q:

Note that this product of g i is an expression for the norm from Z q down to Z p of g 0 and thus it is certainly in Z p . In addition it gives the trace of F to within O(p d ), since if higher precision was desired it would be necessary to take the term q=c 1 into account.

The nal step is to compute each g i from the curves E i and E i+1 and the kernel of ^ i . This is done with the help of V elu's formulae V el71]. Each g i can be expressed as a rational fraction in terms of the data we lifted, and multiplying them together gives the trace with su cient precision.

Complexity

For the eld F q , one works with an algebraic extension of degree d to p{adic precision O(p O(d) ) so that each element of Z q takes O(d 2 log p) space. For each curve one needs to store a bounded number of such elements, and there are d conjugate curves; thus the total memory space required is O(d 3 log p). Remarkably the run-time is just O(d 3 log d log log d) with fast arithmetic (or O(d 5 ) with na ve arithmetic), for xed p. The algorithm is also signi cantly easier to implement than an optimized SEA algorithm, and even with simple Karatsuba arithmetic, the run-time exponent is a respectable 1 + 2 log 3 log 2 ' 4:17.

Satoh proved the following theorem for p 5, and we extend it to the cases p = 2 and p = 3. Theorem 3.2 (Satoh) Let E be an elliptic curve over the nite eld with q = p d elements. Assume that j(E) 6 2 F p 2 . Then there exists a deterministic algorithm for computing the order of E which, for xed p, requires O(d 3 ) memory and O(d 3+" ) bit-operations.

Note that the restriction j(E) 6 2 F p 2 is not essential as the cases j(E) 2 F p 2 can be handled by counting points over a tiny sub eld.

Algorithms for lifting 4.1 Lifting the cycle of elliptic curves

The theorem of Lubin, Serre and Tate ensures that the cycle of J i we want to construct is characterized by p (J i ; J i+1 ) = 0 for all 0 i < d (for notational convenience, the indices are understood to be taken modulo d). The algorithm for computing this cycle from the cycle of j i is a Newton iteration based on the following function acting on a vector of size d: (x 0 ; : : : ; x d 1 ) = ( p (x 0 ; x 1 ); p (x 1 ; x 2 ); : : : ; p (x d 1 ; x 0 )) :

The Newton algorithm presented in section 2 can be adapted to this multivariate case rather easily. Instead of considering the derivative of the function, it is now necessary to deal with the Jacobian matrix D (x 0 ; : : : ; x d 1 ) = 0 B B B B B @ 0 p (x 0 ; x 1 ) 0 p (x 1 ; x 0 ) 0 : : : 0 0 0 p (x 1 ; x 2 ) 0 p (x 2 ; x 1 ) 0 . . . . . . . . . . . . . . . 0 0 0 : : : 0 p (x d 1 ; x d 2 ) 0 p (x 0 ; x d 1 ) 0 0 : : :

0 p (x d 1 ; x 0 ) 1 C C C C C A
where 0 p (X; Y ) denotes the partial derivative of p (X; Y ) with respect to X, and the iteration is essentially (x 0 ; : : : ; x d 1 ) (x 0 ; : : : ; x d 1 ) (D ) 1 (x 0 ; : : : ; x d 1 ):

We describe here a detailed \ready to implement" algorithm which takes care of two important issues: the choice of working precision at each stage, and the inversion of the Jacobian matrix.

If the computations are organized in a suitable way, the inversion can be done with a linear (in d) number of arithmetic operations. The diagonal elements are all invertible so we can do elimination without having to look for a \pivot". Furthermore the o -diagonal elements are all divisible by p.

By doing row operations on the derivative matrix (and simultaneously on ) we move the bottom left element 0 p (x 0 ; x d 1 ) towards the right. At the n-th step it is divisible by p n so that it rapidly becomes zero to within working precision. Then the matrix has a simple form that can be solved directly, from bottom to top.

Procedure LiftJInvariants Inputs: A desired precision n and a cycle j i 2 F q n F p 2 s.t. p (j i ; j i+1 ) 0 mod p for all 0 i < d.

Output: A cycle J i 2 Z q s.t. (J i ) = j i and p (J i ; J i+1 ) 0 mod p n for all 0 i < d.

1. IF n = 1 THEN pick arbitrary J i s.t. (J i ) = j i ; GO TO 5;

2. n 0 d n 2 e;

3. (J 0 ; J 1 ; : : : ; J d 1 ) LiftJInvariants(n 0 ; (j 0 ; j 1 ; : : : ; j d 1 )); 4. (J 0 ; J 1 ; : : : ; J d 1 ) UpdateJs(n; (J 0 ; J 1 ; : : : ; J d 1 )); 5. RETURN (J 0 ; J 1 ; : : : ; J d 1 ).

Procedure UpdateJs

Inputs: A desired precision n and a cycle J i 2 Z q s.t. p (J i ; J i+1 ) 0 mod p dn=2e for all 0 i < d.

Output: A cycle J i 2 Z q s.t. p (J i ; J i+1 ) 0 mod p n and J i J i mod p dn=2e for all 0 i < d.

1. Allocate arrays D 0::d 2], P 0::d 1] and J 0::d 1] of elements of Z q ; 2. FOR i = 0 TO d 2 DO t 1= 0 (J i ; J i+1 ); D i t 0 (J i+1 ; J i ); P i t (J i ; J i+1 ); 3. m 0 (J 0 ; J d 1 ); f (J d 1 ; J 0 ); 4. FOR i = 0 TO d 2 DO f f m P i ; m m D i ; IF m 0 mod p n THEN BREAK; 5. m m + 0 (J d 1 ; J 0 ); 6. P d 1 f=m; 7. FOR i = d 2 DOWN TO 0 DO P i P i D i P i+1 ; 8. FOR i = 0 TO d 1 DO 9. Free arrays D and P; 10. RETURN (J 0 ; J 1 ; : : : ; J d 1 ).

In the procedure UpdateJs, it is possible to reduce the memory usage signi cantly. Indeed, the D and the P arrays can be avoided altogether by computing their entries on the y, although some of the calculations need to be repeated. To do this, loop 2 of the algorithm should be removed and the values D i and P i should be computed on the y in loop 4. Loops 7 and 8 need to be merged and the values D i and P i computed on the y. Some of them were already computed in loop 4 but note that the m 0 test breaks out of that loop after roughly n iterations. In fact, by working to half precision, as described at the end of section 2:5, roughly n=2 iterations are su cient. Since n d=2 at most, not much recomputation is necessary.

4.2 Characteristic p 5 (Satoh)

Lifting the curve's equation

When the characteristic p is at least 5 (p = 2 is treated in section 4.3 and p = 3 in appendix 7), we consider that the elliptic curve E over F q has an equation of the form E : y 2 = x 3 + ax + b. In this case, we want to lift E to a curve E : y 2 = x 3 + Ax+B over Z q whose j{invariant we already know.

To do so, we lift one of the coe cients arbitrarily and lift the other with a Newton iteration based on the equation J = 1728(4A) 3 = where = 16(4A 3 + 27B 2 ). Note that the hypotheses p 5 and J 6 2 F p 2 ensure that the denominator in the iteration is non zero, thus the precision exactly doubles at each iteration.

Procedure LiftAAndB Inputs: The precision n, a j{invariant J 2 Z q and coe cients a and b of a curve E over F q with j{invariant (J).

Output: Coe cients A and B in Z q of a curve E with j{invariant J, lifted to precision n. Procedure LiftBGivenA Inputs: The precision n, a j{invariant J and coe cients A 2 Z q and b 2 F q . Output: A coe cient B in Z q , lifted to precision n.

Lifting the p{torsion

Lifting the p{torsion subgroup is the more delicate step in Satoh's algorithm. The idea is to lift a factor of the p{division polynomial p (x) of E i by a type of quadratic Hensel lift (which resembles a Newton iteration). Two problems arise:

Lifting a factor is not as simple as lifting a root of a polynomial,

The derivative of p (x) is zero modulo p, so it is necessary to be careful with precision. It is especially important to check the initial required precision. The algorithm for dealing with this factor lifting is given in Lemma 2.1 of Satoh's paper. It is very technical and we shall not reproduce the proof here. We only reformulate the result with our notation.

Theorem 4.1 (Satoh) Let (x) be a polynomial over a p{adic eld such that p k 0 (x). Let h(x) be a monic polynomial known to precision n such that (h(x)) is square-free and prime to (p 1 0 (x)), h(x) divides (x) to precision n + 1.

De ne a new polynomial h(x) = h(x) + (x)

0 (x) h 0 (x) mod h(x) :

Then h(x) has the following properties h(x) h(x) modulo p n , h(x) divides (x) to precision 2n + 1. Note moreover that if n 1, then (h(x)) = (h(x)), and the process can be repeated.

To turn this theorem into an algorithm, it remains to initialize the iteration. For this, we need a way to construct the rst approximation for the factor H(x) of p (x). Satoh proposes taking the p-th root of the p{division polynomial of the curve E i , which is free since all the necessary information is in the p{division polynomial of the curve E i+1 .

The algorithm is as follows:

Procedure LiftH Inputs: The precision n, an elliptic curve E i+1 over F q and an elliptic curve E i over Z q . Output: A monic factor H(x) of the p-th division polynomial of E i , representing the kernel of ^ i .

(x) the p-th division polynomial of E

i ; (Note deg = p 2 1 2 ).
2. (x) the p-th division polynomial of E i+1 ; (Note = h p for some h(x) with degree p 1 2 ).

3. h(x) 0; 4. FOR k = 0 TO p 1 2 DO 13 h(x) h(x) + u k u (p 1)=2 x k , with u k the coe cient of x pk in (x); 5. H(x) LiftHbis(n; (x); h(x)); 6. RETURN H(x).

Procedure LiftHbis Inputs: The precision n, a polynomial (x) and an approximation h(x). Output: A monic factor H(x) of (x) to precision n.

Characteristic two

In this subsection, we propose lifting algorithms for the curve and the torsion subgroup in characteristic two. In remark 3.9 of Sat00], Satoh pinpointed the main obstacle to extending his method to p = 2 and sketched a possible workaround using a probabilistic factoring algorithm. Here we

propose an e cient and completely deterministic solution.

In characteristic two any elliptic curve E, or its twist, has the form y 2 + xy = x 3 + a: provided j(E) 6 = 0. Thus we can con ne ourselves to this case.

Lifting the curve's equation

Our algorithm for lifting the equation of the curve is to lift its a coe cient using a Newton iteration, to obtain the coe cient A in the equation y 2 + xy = x 3 + A of the lifted curve E. Since J = 1 , where = A 432A 2 is the discriminant of the curve, the polynomial whose root we will calculate is f(x) = 1 + J(x + 432x 2 ).

In this case f 0 (x) = J(1 + 864x) and since (J) 6 = 0, we could use procedure NewtonIterations (see section 2.5 above) with k = 0. Thus we could go from precision n to 2n at each step, but in fact we can do slightly better than the generic method and instead go to 2n + 4. Let x be an approximate root at precision n, with error term f(x) = O(2 n ). Let y = x f(x)=f 0 (x) be the improved root after one step. Then the new error term can be written explicitly as

f(y) = 1 + J(y + 432y 2 ) = 432 J f(x) 2 f 0 (x) 2
We have 2 -f 0 (x) and 2 4 k 432, therefore f(y) = O(2 2n+4 ). It follows that an initial approximate root is not actually needed to start the iteration, although for e ciency we might as well use 1=J modulo 16.

Procedure LiftA Inputs: An integer n and the j{invariant J of a curve E in Z q , with precision n. Output: The coe cient A of the lifted curve E in Z q with precision n.

IF n 4 THEN A

1=J; GO TO 5;

2. n 0 d n 4 2 e;

3. A LiftA(n 0 ; J); 4. A A 1+J(A+432A 2 ) J(1+864A) ; 5. RETURN A.

(A possible alternative algorithm would be to lift the conjugates of the coe cient a directly using a modular polynomial for a instead of the usual one for j).

Lifting the 2{torsion

Our algorithm for lifting the 2{torsion is also based on Newton iteration. In this case, the function f(x) comes from the equation satis ed by the abscissae of the non-trivial 2{torsion points on the lifted curve E, namely the 2{division polynomial 4X 3 +X 2 +4A. A root X 2 Z q of this polynomial is necessarily 0 modulo 2. By setting X = 2Z, we get the modi ed division polynomial 8Z 3 +Z 2 +A. In this case we nd Z using an iteration based on the function f(x) = 8x 3 + x 2 + A.

A di culty arises in that there are two candidate roots in Z q and we must compute the one which corresponds to the non-trivial point in the kernel of ^ i . It will be su cient to initialise the Newton iteration with the correct square root of A modulo 8.

We next describe how to do this in a deterministic way. We thus solve the problem Satoh encounters in his paper while avoiding the probabilistic polynomial factorization modulo 8 that he suggests. Some theory is needed to justify the choice of root but the result is simple and e cient. The reader can skip the next part if desired.

Choosing the correct root. In section 5.3 below, we use V elu's formulae to construct a curve E 0 i whose j{invariant must equal J i+1 . Computing it explicitly, in terms of A and the as-yet-unknown Z, from the equation of E 0 i yields J i+1 = J(E 0 i ) 1

Z 2 Z + A mod 4: Since Z is a root of f, we have Z 2 + A 0 mod 4 (even modulo 8) and thus Z 1 J i+1 mod 4 which determines Z uniquely and provides a su ciently precise initial root Z 0 for the procedure NewtonIterations. Indeed f 0 (x) = 2(12x 2 + x) and 12Z 2 0 + Z 0 1=J i+1 mod 4 and this is non-zero modulo 2. Hence we have k = 1 and we need f(Z 0 ) 0 mod 2 2k+1 i.e., modulo 8 to start the iterations. Now f(Z 0 ) Z 2 0 + A mod 8;

(1=J 2 i+1 ) + A;

(the value of Z 0 mod 4 determines Z2 0 mod 8) (1=J 2 i+1 ) (1=J i ): (from lifting of A in section 4.3.1 above) It remains to show J 2 i+1 J i mod 8. Now J i = (J i+1 ) so the desired result certainly holds modulo 2. Next, note that the Kronecker relation 2 (X; Y ) (X 2 Y )(X Y 2 ) actually holds modulo 16 and not just modulo 2. Thus 2 (!(j i ); !(j i+1 )) 0 mod 16 and the terms x 1 , x 2 and x 3 in the semi-Witt decomposition of J i+1 are zero (see section 2.3). Thus J i J 2 i+1 mod 16 and hence certainly modulo 8 as required 2 .

Lifting the root. To calculate the correct root Z, we use procedure NewtonIterations with k = 1 and with initial root 1=J i+1 mod 4.

Here, the precision increases at each step from n to 2n 1. Let x be the approximate value at precision n, with error term f(x) = O(2 n+1 ). Let y = x f(x)=f 0 (x) be the improved root after one step. Then the new error term is f(y) = 8y 3 + y 2 + A = f(x) 2 f 0 (x) 2 (24x + 1) 8 f(x) 3 f 0 (x) 3 :

We have 2 k f 0 (x) and therefore f(y) = O(2 min(2n;3n+3) ) = O(2 2n ) as expected. Procedure LiftZ Inputs: An integer n, the j{invariant J i+1 to precision 2 and the coe cient A to precision n + 1. Output: The Z of the lifted curve E with precision n.

1. IF n 2 THEN Z 1=J i+1 ; GO TO 5; 2. n 0 d n+1 2 e; 3. Z LiftZ(n 0 ; J i+1 ; A); 4. Z Z 8Z 3 +Z 2 +A 2(12Z 2 +Z) ; 5. RETURN Z.

5 Computing the trace V elu's formulae lead to simple expressions for the rst coe cient of the isogeny ^ between E i and E i+1 . Computing the trace just requires taking the product of all these expressions. In this section we recall the formula given by Satoh for p 5 and derive a similar one for characteristic two. The case p = 3 is given in the appendix.

V elu's formulae

Let E be an elliptic curve, and let F be a nite subgroup of E. Then E=F is isomorphic to an elliptic curve. The formulae given by V elu V el71] give the explicit equation of an elliptic curve E 0 isomorphic to E=F, together with an explicit formula for the isogeny between E and E 0 . Moreover the isogeny is such that when we write it in the formal group, its rst coe cient is 1.

Let us apply this to our problem. We have two curves E i and E i+1 and a subgroup of E i . We want to know the rst coe cient in the formal group expression of the isogeny between E i and E i+1 corresponding to this kernel. The rst step is to compute the curve E 0 i given by V elu's formulae.

Then, we know that E 0 i and E i+1 are isomorphic so we can compute this isomorphism explicitly and its rst coe cient in the formal group expansion.

We have the following diagram:

E i > > > > > > > ^ i / / E i+1 E 0 i > > | | | | | | | |
Thus g i , the rst coe cient of the isogeny ^ i is equal to the product of the rst coe cient of V elu's isogeny (which is 1) and that of the isomorphism . For the latter, it is easy to nd its square in terms of the equations of the curves. 5.2 Characteristic p 5 (Satoh) In the case of characteristic p 5, we refer to Satoh's original paper for the derivation of the formulae. (For characteristic two, see 5.3 and for characteristic three, see 7.3 in the appendix).

The equation of E i is of the form y 2 = x 3 + A i x + B i ; and that of E i+1 is y 2 = x 3 + A i+1 x + B i+1 :

The kernel of ^ i consists of the point at in nity on E i and p 1 nite points whose p 1 2 distinct abscissae are given by the roots of the polynomial H i (x).

The curve E 0 i given by V elu's formulae has equation y 2 = x 3 + i x + i with i = (6 5p)A i 30(s 2 1 2s 2 ) and i = (15 14p)B i 70( s 3 1 + 3s 1 s 2 3s 3 ) + 42A i s 1 ; where s k denotes the coe cient of x (p 1)=2 k in H i (x).

Having the equation for E 0 i , it is rather easy to compute the isomorphism with E i+1 . We refer to Silverman Sil86] for the general form of an isomorphism between elliptic curves. In this case it has the form (x; y) 7 ! (g 2 i x; g 3 i y) where g i is the term we are looking for. Hence

g 2 i = i i A i+1 B i+1 :
Thus the algorithm for computing the square of the trace is now clear, and we decide between the two square roots by checking the sign using the Hasse invariant h E de ned to be the norm of the coe cient of x p 1 in the polynomial (x 3 + ax + b) (p 1)=2 .

Procedure ComputeTraceOddChar

Input: An elliptic curve E over F p d , with j(E) 6 2 F p 2 , given by its equation y 2 = x 3 + ax + b. Output: The trace of the curve.

1. n log p 4 + d 2 ;

2. (j i ) 0 i<d ; (a i ) 0 i<d ; (b i ) 0 i<d Conjugates of j(E), of a, of b;

3. (J i ) 0 i<d LiftJInvariants(n; (j i )); 4. N 1; D 1; 5. FOR i = 0 TO d 1 DO A; B LiftAAndB(n; J i ; a; b); H LiftH(n; a i+1 ; b i+1 ; A; B); s 1 ; s 2 ; s 3 coe cients of x (p 1)=2 1 , x (p 1)=2 2 and x (p 1)=2 3 in H(x);

(6 5p)A 30(s 2 1 2s 2 );

(15 14p)B 70( s 3 1 + 3s 1 s 2 3s 3 ) + 42As 1 ; N N A; D D B; Note that in step 6, the numerator and denominator are in Z p and c is too. The p{adic square root can be found using a Newton iteration for the inverse square root, and then multiplying by c.

There are two possible roots, either of which will do, since step 8 corrects the sign if necessary.

Characteristic two

The equation of E i is of the form y 2 + xy = x 3 + A i ; and that of E i+1 is y 2 + xy = x 3 + A i+1 :

In the case of characteristic two, the kernel of ^ i is a subgroup of order 2 of the 2{torsion. Let (X i ; Y i ) be the non-trivial point of this subgroup. Note that the ordinate satis es Y i = X i =2.

The curve E 0 i given by V elu's formulae V el71] has equation y 2 + xy = x 3 + A 4 x + A 6 where A 4 = 5t and A 6 = A i t 7w; with t = 3X 2 i Y i and w = X i t:

Here again, having the equation for E 0 i and E i+1 allows us to compute the isomorphism and then the coe cient g 2 i . After translations of the axes (which do not a ect the rst coe cient in the formal group expansion of the isomorphism), the equations are the following: (48A 4 1)(1 + 864A i+1 ) :

Thereafter we can replace A 4 and A 6 with their expressions in terms of A i and X i .

We obtain

g 2 i = 18144X 3 i 4536X 2 i 252X i + 1 + 864A i (1 + 120X i + 720X 2 i )(1 + 864A i+1 ) :
We can simplify this formula further by reducing modulo the minimal polynomial of X i , which is

4X 3 i + X 2 i + 4A i . We get g 2 i = 1 252X i + 19008A i 1 + 120(X i + 6X 2 i ) (1 + 864A i+1 )
:

Remembering that we lifted Z i = X i =2 instead of X i and considering that we need one extra bit of precision for a 2{adic square root, we get the following algorithm.

Procedure ComputeTraceChar2

Input: An elliptic curve E over F 2 d , with j(E) 6 2 F 4 , given by its its equation y 2 + xy = x 3 + a.

Output: The trace of the curve.

1. j 0 j(E); FOR i = d 1 DOWN TO 1 DO j i j 9. RETURN c. Note that in step 6, the numerator and denominator are in Z 2 and c is too. The 2{adic square root can be found via a Newton iteration for the inverse square root. There are four possible square roots modulo 2 n+2 but just two modulo 2 n+1 and step 7 corrects the sign if necessary.

It is possible to reduce the amount of memory required by combining the lift of the J i 's with the computations in loop 5. Indeed as soon as one of the J i 's has been computed to full precision n in procedure UpdateJs, it can be used to lift the corresponding A and Z and to update N and D. Then J i is no longer needed. In this way, the cycle of J i 's only needs to be stored to half precision. When this trick is combined with the one described at the end of section 4.1, the total space requirement is d 3 4 + O(d 2 ) bits.

6 Numerical examples 6.1 A small example In this section we give some intermediate data which are computed when our algorithm for characteristic two is run on the elliptic curve over F 2 11 = F 2 t]=(t 11 + t 2 + 1) de ned by y 2 + xy = x 3 + a with a = t 4 + t 2 + t: This example is taken from LM00] where it is used to compare di erent algorithms for computing isogenies.

The rst steps are to lift the cycle of j{invariants and the curves to precision O(2 7 ). We give here the resulting sequence of A i 's.

A 0 = 30t 10 + 12t 9 + 30t 8 26t 7 18t 6 12t 5 39t 4 2t 3 + 41t 2 + 7t 20 A 1 = 31t 10 55t 9 3t 8 + 43t 7 + 33t 6 + 10t 5 50t 4 46t 3 + 17t 2 + 20t 5 A 2 = 46t 10 53t 9 6t 8 + 6t 7 18t 6 33t 5 + 17t 4 + 31t 3 + 16t 2 39t 15 A 3 = 8t 10 19t 9 + 47t 8 50t 7 41t 6 14t 5 + 30t 4 + 46t 3 + 9t 2 48t 57 A 4 = 23t 10 58t 9 42t 8 26t 7 + 18t 6 + 40t 5 + 29t 4 + 29t 3 30t 2 38t 54 A 5 = 39t 10 43t 9 + 33t 8 + 43t 7 + 30t 6 39t 5 56t 4 + 34t 3 t 2 27t + 63 A 6 = 42t 10 + 31t 9 38t 8 + 49t 7 49t 6 55t 5 21t 4 42t 3 42t 2 + 63t 51 A 7 = 62t 10 53t 9 + 46t 8 5t 7 37t 6 26t 5 + 53t 3 + 35t 2 + 52t 15 A 8 = 15t 10 + 54t 9 + 35t 8 31t 7 58t 6 10t 5 + 60t 4 + 49t 3 + 16t 2 + 40t + 26 A 9 = 58t 10 + 12t 9 45t 8 15t 7 38t 6 63t 5 + 11t 4 + 18t 3 8t 2 + 30t 20 A 10 = 56t 10 + 44t 9 57t 8 + 12t 7 + 50t 6 54t 5 + 19t 4 42t 3 53t 2 60t 52

The J i 's can be recovered easily if desired, by the formula

J i = 1 A i + 432A 2 i :
Then the half-abscissae of the 2{torsion points can be lifted. To precision O(2 6 ), the resulting sequence is:

Z 0 = 25t 10 + 7t 9 21t 8 3t 7 25t 6 + 6t 5 2t 4 + 22t 3 5t 2 + 32t 11 Z 1 = 26t 10 + t 9 30t 8 + 30t 7 2t 6 7t 5 + 23t 4 + 25t 3 + 28t 2 + 23t + 19 Z 2 = 32t 10 9t 9 + 9t 8 + 26t 7 + 17t 6 30t 5 18t 4 26t 3 9t 2 4t + 5 Z 3 = 23t 10 + 22t 9 2t 8 + 2t 7 30t 6 16t 5 + 11t 4 + 11t 3 + 10t 2 + 6t 22 Z 4 = 13t 10 + 19t 9 + 7t 8 3t 7 + 26t 6 25t 5 12t 4 + 26t 3 + 25t 2 13t 7 Z 5 = 10t 10 + 29t 9 + 18t 8 + 19t 7 7t 6 + 3t 5 + 21t 4 30t 3 2t 2 + 29t + 7 Z 6 = 22t 10 + 9t 9 22t 8 + 17t 7 7t 6 26t 5 28t 4 13t 3 + 5t 2 21 Z 7 = 23t 10 + 14t 9 + 5t 8 + 3t 7 2t 6 14t 5 28t 4 21t 3 12t 2 + 8t + 18 Z 8 = 14t 10 + 28t 9 + 17t 8 5t 7 18t 6 25t 5 + 5t 4 6t 3 24t 2 + 2t + 12 Z 9 = 16t 10 28t 9 3t 8 + 6t 6 30t 5 15t 4 + 2t 3 + 21t 2 28t 28 Z 10 = 30t 10 28t 9 + 22t 8 22t 7 22t 6 28t 5 21t 4 + 10t 3 + 27t 2 + 9t 28

The square of the trace can now be computed modulo 2 9 by the formula

c 2 = Q i (1 504Z i + 19008A i ) Q i (1 + 240(Z i + 12Z 2 i ))(1 + 864A i ) 65
129 449: The two square roots modulo 2 8 are c 31:

And we choose the one congruent to 1 modulo 4. Thus c = 31:

New record

Here we present a record result obtained with the third author's implementation of the algorithm described above (dubbed ECPC for Elliptic Curve Point Counting). We computed the number of points on curves over several large binary elds, the largest being F q with q = 2 8009 . Some details of the calculation are given below.

Processor

CPU Time Memory Location Alpha EV6, 750 MHz 313 h 16.9 GB Cornell Computer Systems Laboratory Several multiplication algorithms are implemented in ECPC. For small precisions it uses the na ve method and Karatsuba's algorithm. For medium precisions it switches to a 3-way or 4-way Toom-type algorithm with evaluation and interpolation at 5 or 7 rational points. Last but not least, the high precision calculations are performed using Fast Fourier Transforms modulo Fermat numbers in the style of Sch onhage's algorithm. Thus it reaches in practice the best speed predicted by the asymptotic analysis.

The usefulness of these advanced algorithms can be observed in the following times for multiplication over Z q at the maximal precision of 4008 bits:

Algorithm Time Na ve 866 s Karatsuba 26.8 s Toom3 12.7 s Toom4 9.80 s Sch onhage 2.56 s 7 Appendix: Characteristic three Curves in characteristic three, like curves in characteristic two, have a particular form which induces some particularities in Satoh's algorithm. Here we give the required formulae and brie y describe the method for lifting the coe cients of the curve and the 3{torsion subgroup. Finally we derive the equation for the trace using V elu's formulae.

Lifting the curve's equation

In characteristic three, the equation of an elliptic curve has the form y 2 = x 3 +a 2 x 2 +a 6 whenever its j{invariant is non-zero, and then j = a 3 2 =a 6 . The lifted curve E is of the form y 2 = x 3 +A 2 x 2 +A 6 and its j{invariant is J = 256A 6 2 =(4A 3 2 A 6 + 27A 2 6 ). Therefore, to lift the coe cients of the curve, one uses almost the same algorithms as for characteristic p 5. That is, one rst lifts the coe cient A 2 arbitrarily and then one lifts A 6 using a Newton iteration based on f(x) = J(A 3 2 x + 27 4 x 2 ) + 64A 6 2 and with initial approximate root x 0 = a 6 .

Lifting the 3{torsion

The 3{division polynomial of E is 3 (x) = 3x 4 + 4A 2 x 3 + 12A 6 x + 4A 2 A 6 whereas the one of E is 3 (x) = a 2 (x 3 +a 6 ). We lift the 3{torsion subgroup using a Newton iteration based on the function 3 (x). The initial approximate root is x 0 = 3 p a 6 . This iteration is valid since we have: 3 (x 0 ) = 3A 6 x 0 4A 2 A 6 + 12A 6 x 0 + 4A 2 A 6 = 9A 6 x 0 0 3 (x 0 ) = 12A 6 + 12A 2 x 2 0 + 12A 6 = 12A 2 x 2 0 Thus 3 (x 0 ) 0 modulo 9 and 0 3 (x 0 ) 0 modulo 3 but not modulo 9 (note A 2 6 = 0 and A 6 6 = 0).

Isogenies and traces in characteristic three

For the computation of the trace the method is the same as for characteristic two, except that we have to take into account the form of the curve equations and also adapt V elu's formulae.

The curve E i has an equation of the form E i : y 2 = x 3 + A i x 2 + B i :

We write X i for the abscissa of the lifted 3{torsion point. Then V elu's formulae give the following equation for the curve E 0 i : y 2 = x 3 + a 2 x 2 + a 4 x + a 6 where a 2 = A i ; a 4 = 5t; a 6 = B i 4A i t 7w; with t = 6X 2 i + 4A i X i ; and w = 10X 3 i + 8A i X 2 i + 4B i :

Now we transform the equations of E 0 i and E i+1 by translation of the axes to obtain E i+1 : y = x 3 1 3 A 2 i+1 x + B i + 2 27 A 3 i+1 E 0 i : y = x 3 + (a 4 1 3 a 2 2 )x + a 6 + 2 27 a 3 2 1 3 a 2 a 4 23

The expression for g 2 i follows easily:

g 2 i = A 0 i 2 ( 1890X 3 i 1890A i X 2 i 252A 2 i X i + 2A 3 i 729B i ) (2A 0 i 3 + 27B 0 i ) 90X 2 i + 60A i X i + A 2 i :

Finally the trace is given by Tr F Y 0 i<d g i mod q:

  In practice the division and multiplication by p k are fast operations e.g., right and left shifts when p = 2. Now the Newton iteration can be computed as y = x + O(p 2n k ) where : = (f(x) + O(p 2n )) p n k + O(p n k ) (f 0 (x) + O(p n )) p k + O(p n k ) + O(p n k ) p n + O(p 2n k )

  where d 1 = 2232, d 2 = 1069956, d 3 = 36864000, d 4 = 2587918086, d 5 = 8900222976000, d 6 = 452984832000000, d 7 = 770845966336000000 and d 8 = 1855425871872000000000.

1.

  Pick arbitrary A such that (A) = a; 2. B LiftBGivenA(n; J; A; b); 3. RETURN A; B.

  1. IF n = 1 THEN pick any B such that (B) = b; GO TO 5

  6. c p N=D;7. h E Hasse invariant of E.8. IF c 6 h E mod p THEN c c; 9. Reduce c to an integer in 0 : : : p n . IF c > 2 p q THEN c c p n ; 10. RETURN c.

  Reduce c to an integer in 0 : : : 2 n+1 . IF c > 2 p q THEN c c 2 n+1 ;

	8.
		2 i+1 ;
	2. n d d 2 e + 1;
	3. (J i ) 0 i<d LiftJInvariants(n; (j i ));
	4. N 1; D 1;
	5. FOR i = 0 TO d 1 DO
	A LiftA(n; J i );
	Z LiftZ(n 1; J i+1 ; A);
	A 864A;
	N N(1 504Z + 22A);	(N has precision n + 2)
	D D(1 + 240(Z + 12Z 2 ))(1 + A); 6. c p N=D;	(D has precision n + 2)
	7. IF c 6 1 mod 4 THEN c c;

The di erence is simply that for Witt vectors, the coordinates xi are replaced by x p i i .

/ / E 1 0 / / E 0 Composing all these gives:

Compute the cycle of d curves E i and their j{invariants j i ;

Lift all the j i simultaneously, yielding J i ;

J i J i P i ;

Note that this allows the rst two steps of lifting the Ji's to be optimised away and replaced by d + 2 squarings.

Acknowledgements

We would like to thank Fran cois Morain for his continuous support and many invaluable suggestions during this work.

We are also grateful to Paul Bourke from Swinburne University Astrophysics and Supercomputing, to Tom Morris from Alpha Processor, Inc. and to Rajit Manohar from Cornell Computer Systems Laboratory. They provided the computer resources needed for many of our calculations.

We represent the eld F q as F 2 t]=(f(t)) where f(t) is the irreducible polynomial t 8009 +t 3159 +1. Let E be the curve y 2 + xy = x 3 + a where a is: 0x3F636F6420707520732774616857 This hexadecimal representation is obtained by reducing a modulo f and setting t. The value was chosen to be the ASCII encoding of the phrase \What's up doc?". The result we obtained is q + 1 c with the trace c as follows:

- We checked that this result is indeed a multiple of the orders of several randomly chosen points on each curve. A rigorous check of the number of points would require q + 1 c to be factored completely, but this does not seem to be feasible.

For reference, the run-times for ECPC on some smaller eld sizes are as follows.

Degree


F Pedraza
email: fpedraza@univ-lr.fr

J L Grosseau-Poussard

J F Dinhut

NITRIDATION EFFECTS ON THE OXIDATION MECHANISMS OF AN ODS FeAl INTERMETALLIC ALLOY

An ODS FeAl intermetallic alloy has been nitrided at low-energy high flux implantation diffusion leading to the formation of hexagonal AlN and α-Fe segregation. Its high temperature behaviour is subsequently evaluated under isothermal oxidation at 800º C.

Microscopy techniques (SEM, TEM) will show that nitridation hinders aluminium outward diffusion and enhances iron outward diffusion giving rise to a layered structure.

1.-Introduction

Upon the high temperature oxidation of titanium aluminides, TiN and/or Ti 2 AlN subscales have been observed to develop at the substrate/oxide interface [1,2], which sometimes have been referred to provide an effective barrier for outward Al diffusion [3] or to prevent oxygen dissolution in the alloy [4] thus improving their oxidation resistance. When these alloys are nitrided, the same nitrogen containing phases appear [5] but only detrimental effects have been reported to occur compared to non nitrided specimens owing to a lower amount of Al 2 O 3 developed at the top surface [6][7][8].

In the case of iron aluminides without oxygen-active elements, their oxidation behaviour is worse in air than in pure oxygen due to internal nitridation below a defective alumina scale [9]. Pint et al. [10] indicated that on Fe 3 Al this could result by either simultaneous nitridation and oxidation or, once the scale had been formed, by a reduced oxygen partial pressure in contrast to a high nitrogen pressure. The latter mechanism seems to better agree with the findings of Xu et al. on FeAl [11]. However, the effects of nitridation have only been scarcely studied. Choe [12] employed ion implantation at 150 keV to nitride different Fe 3 Al (with and without Cr, Mo and B) resulting in the formation of AlN, Fe 4 N, CrN and even α-Fe, which enhanced the corrosion resistance to acid media. More recently, the effects of an ion nitriding treatment on the oxidation behaviour of an ODS FeAl alloy have been discussed [13],

indicating the formation of AlN and again of α-Fe after the nitridation treatment, the latter element diffusing outwardly upon oxidation to form iron oxides. As a result, the nitridation treatment is concluded not to be beneficial. It is therefore intended in this work to provide additional insight on the nitridation of an yttria dispersed FeAl and its subsequent oxidation behaviour at 800º C. This temperature has been chosen since previous studies on iron aluminides have only focused on temperatures higher than 900º C [10,11]

2.-Experimental

Low energy -high flux nitrogen implantation of 1 μm polished FeAl Grade 3 [15 ppm B, 0.1 wt% Zr, 1 wt%Y 2 O 3 , CEA/CEREM (Grenoble, France)] was carried out at 1.2 keV and 1 mA.cm -2 up to a dose of 3.5 x 10 19 at.cm -2 while controlling the temperature not to exceed 400°C. Prior to nitridation, Ar + sputtering was carried out on each main coupon face to remove the rigid oxide layer that precludes nitridation [14]. The backing pressure in the chamber upon the nitriding process was better than 10 -2 Pa. Implantation was carried out on both principal coupon faces for the subsequent oxidation experiments, representing about 85% of the overall surface.

Oxidation of the nitrided specimens was conducted in a Setaram TG DSC92 thermobalance of 10 -6 g of accuracy at 800º C for 24 h under synthetic air. Heating and cooling rates were fixed at 50º C/ min Characterisation was undertaken by conventional XRD in a Bruker AXS D-5005, AFM in the contact mode with an Autoprobe CPR (Veeco Instruments),SEM/EDS in a JEOL JSM-5410 LV and TEM/EDS in a JEOL-JEM 2010 at 200 kV. For the preparation of the cross sections of the implanted and the oxidised specimens careful mechanical polishing in SiC# 4000 emery paper was performed down to a thickness of about 50 μm. Then, Ar bombardment at 3 keV was carried out in a GATAN PIPS™ (precision ion polishing system) model 691 at different angles.

3.-Results

3.1.-Nitridation

The surface of the nitrided specimens appeared to be homogeneous with protrusions at the top surface and remains of porosity. The former seemed to be pinned by yttria particles [START_REF] Pedraza | Thin Solid Films, Nitridation treatment of an ODS FeAl intermetallic alloy[END_REF]. The EDS average surface composition was of 55% Fe-25% Al and 20% N (at%). However, by inspecting the cross sections a non planar nitridation front is observed to occur [Figure 1(a)] with an outer compound layer and an inner diffusion layer. After chemical etching, the structure of the nitrided layer is better revealed, with outward growing protuberances as well as grains of submicron size constituting the nitrided layer. The alloy itself shows the alignment of the grains composing this alloy fabricated by powder metallurgy and extruded in the <110> direction [13,[START_REF] Montealegre | [END_REF].

TEM analysis again showed equiaxed grains of submicron scale throughout the nitrided layer and a diffusion layer more compact than the compound layer. Figure 2 (a) shows the EDS (TEM) analyses across the full nitrided layer. The amount of nitrogen decreases gently from the top surface although a jump is observed at about 0.75 μm from the surface, which seems to differentiate the compound layer (top) from the diffusion layer (bottom). Some oxygen impurities are present all across the nitrided layer. The aluminium concentration is almost constant across the nitrided layer but the iron amount increases from the top surface towards the substrate exceeding its original content in the alloy. Closer TEM inspection at this region shows iron segregating at the nitrided layer/substrate interface [Figure 2 (b)]. Selected area diffraction patterns (SADPs) across the different regions reveal the exclusive formation of hexagonal AlN and α-Fe together with fragmentation (diffused rings) of the outer FeAl grains of the alloy [START_REF] Pedraza | Thin Solid Films, Nitridation treatment of an ODS FeAl intermetallic alloy[END_REF] The conventional XRD confirmed the presence of such three species [13].

3.2.-Oxidation

After the 24 h exposure at 800º C, the weight gains of the nitrided specimens was fourfold that of the un-nitrided, with parabolic rate constants of about 4.7•10 -8 mg 2 •cm -4 •s -1 for the latest stage [13], i.e. even 10 times faster than those of nitrided α-iron [17].

After cooling, the oxide scales are shown to extensively spall off (Figure 3), depicting at least two subscales, a very convoluted top layer and an inner layer with white needles.

Although the surface EDS microanalysis and XRD only indicated the presence of iron oxide (hematite), TEM inspection reveal a more complex oxide scale as shown in phase, with contribution of hexagonal AlN at the oxide/substrate interface, whose reflections are summarised in Table 1. Upon the nitridation of aluminium-containing alloys, supersaturation of nitrogen in aluminium or the formation of AlN may occur [18]. However, the thermodynamic stability of the growing phase also plays an important role. In the FeAl alloy, the chemical affinity of N to Al is much greater than that to Fe [19] and as such, only AlN formation is observed under the present experimental conditions. According to Sonnleitner et al. [20] the polycrystalline hexagonal AlN only develops if the nitrogen content is between 15-25 wt%, which is possibly non stoichiometric owing to the reconstruction of surface atoms upon implantation [19]. In the present study, only the outer compact layer would have enough nitrogen to form AlN but as its content decreases towards the substrate, the nitride is found diluted in a FeAl / α-Fe matrix, which agrees well with the previous investigation reported in [13]. α-Fe seems to result as a by-product from the reaction of nitrogen with aluminium during the implantation process. It is believed that AlN formation starts at the surface of the FeAl grains and further penetrates into them thus inducing their fragmentation [START_REF] Pedraza | Thin Solid Films, Nitridation treatment of an ODS FeAl intermetallic alloy[END_REF]. This brings about the creation of more grain boundaries through which nitridation is promoted (also incorporating some oxygen) and aluminium is transported towards the surface, as revealed by the constant profile shown in Figure 2 (a). Iron outward diffusion is in turn hindered since the diffusion coefficient of indium (isoelectronic to aluminium) has been

shown to be about twice than that of iron in Fe 66 Al 34 and Fe 50 Al 50 [21].

After nitridation, the porosity of this sintered material still remains but the protrusions are likely to result from the gas bubble formation [22] which may surpass the yield stress of the parent material thus inducing deformation [23]. Since the intermetallic alloy is strengthened by a dispersion of Y 2 O 3 particles, those areas lacking of such particles are more prone to deform and thus the material flows in an elongated shape.

4.2.-Oxidation

The isothermal oxidation at 800º C of the nitrided ODS FeAl has shown to bring about extensive spallation of the oxide scale. This is thought to occur upon cooling of the specimens since no humps in the oxidation curve were recorded during the test [13]. As mentioned above, the surface after nitridation is plastically deformed (protrusions), which may bring about high stress gradients within the oxide scale upon cooling bringing about the observed detachment. Convolution of the oxide scale had already been observed by Xu et al. [11] oxidised at 1100º C on the same substrate, in which only alumina scales formed together with AlN at the inner oxide interface.

In this study, the oxidation rate is about ten times faster than that of nitrided iron [17].

Indeed, it has been shown that layered oxide scale is formed after oxidation composed of an outer hematite layer, central alumina and inner Fe-Al spinel scale. The latter besides contains AlN at the interface with the substrate. Such complex structure seems to derive from the following oxidation mechanism. Although outward diffusion of indium (aluminium) is two times faster than that of iron in Fe 66 Al 34 and Fe 50 Al 50 [21],

there is not enough aluminium available at the top surface to form the oxide since this is trapped as AlN throughout the compact layer. At the diffusion layer, α-Fe was found to segregate at the fragmented FeAl matrix together with some AlN. Such iron is readily available for outward diffusion through the important number of short circuit paths that represent the grain boundaries and defaults created upon nitridation. However, once the outer iron scale is developed, the oxygen partial pressure decreases and only aluminium oxide is able to form owing to its higher thermodynamic stability. Although at reduced pressure only the α-Al 2 O 3 phase develops, the appearance in Figure 3 dissolution of AlN also takes place [11] and indeed, no nitrogen is found in any of the oxide layers except at the spinel / substrate interface. This implies that after dissolution of the nitride, nitrogen seems to diffuse inwardly towards the substrate whereas the resulting aluminium tends to be transported outwardly, stabilising the spinel oxide phase. The presence of such spinel phase has also been observed at the same location on non nitrided specimens at temperatures of 850 and 950º C [28] and seemed to form prior to the development of the outer alumina scale. In such study it was already claimed that the spinel layer would only be partially effective in hindering outward aluminium diffusion when the grains coarsened with increasing temperature . Therefore, a change in the oxidation mechanism of FeAl Grade 3 results from the presence of implanted nitrogen. Overall, its role is that of retarding the establishment of an external alumina scale, but does not seem to impede it. Longer oxidation tests should be carried out to confirm this possibility. It also has to be remarked that no contribution of the yttria dispersed phase has been found and its role does not seem to affect the oxidation behaviour of FeAl at 800º C.

5.-Summary and conclusions

The

Figure 4 (

 4 Figure 4 (a). Owing to the spallation phenomenon, preparation of the electron transparent cross section was a hard task but this figure clearly depicts stratification, which in turn indicates different oxidation mechanisms, as confirmed by the EDS (3 nm spot) microanalyses across the entire scale [Figure 4 (b)]. Indeed, the outermost oxide layer is only constituted of iron and oxygen and of about 0.25 μm thick. According to the XRD patterns [13] this phase has been identified as α-Fe 2 O 3 .Underneath, a 0.2 μm thick layer exists, which is mostly enriched in aluminium, which may correspond to α-Al2O 3 . The inner oxide layer is the largest (about 0.5 μm thick) with more of Al than Fe as plotted Figure 4 (b), indicating the possibility of a FeAl 2 O 4 spinel phase. It is right at the spinel substrate interface that nitrogen is found to concentrate, accompanied with a drop in the oxygen content. As shown in Figure 4 (c), the selected area diffraction patterns (SADPs) at the top and bottom inner scale confirm the existence of the FeAl 2 O 4

  of the typical needle or plate-like morphology indicates the presence of the θ-Al 2 O 3 phase [24]. Both the Fe 2 O 3 and the θ-Al 2 O 3 phases are known to contain an important amount of defects through which oxygen can be transported inwardly [25] resulting in the formation of the spinel phase underneath the alumina scale. The Fe-Al spinel phase has been reported to originate from either the Fe 2 O 3 and Al 2 O 3 reaction [26] or from the FeO and Al 2 O 3 one [27]. This is confirmed from the EDS microanalysis of Figure 4(b) in which the oxygen amount is constant across the entire oxide scale. At reduced oxygen partial pressures

Figure 1 .Figure 2 .Figure 3 .Figure 4 .

 1234 Figure 1.-SEM cross sections of the nitrided specimens (a) unetched showing irregular nitrided front and (b) etched condition revealing the surface protrusions.

Table 1 .-Experimental d-spacings obtained from SADPs at the inner oxide layer / substrate interface after oxidation at 800º C of the nitrided ODS FeAl and their correspondence to the planes of the identified compounds. d-spacing, Å FeAl 2 O 4 (JCPDS 34-192) AlN JCPDS 25-1133

 1

	4.65	111	-
	2.70	-	100
	2.46	311	002
	2.04	400	-
	1.86	331	102
	1.39	-	103


F Pedraza
email: fpedraza@univ-lr.fr

C Savall

G Abrasonis

J P Rivière

J F Dinhut

J L Grosseau- Poussard

LOW ENERGY, HIGH-FLUX NITRIDATION OF FACE CENTRED CUBIC METALLIC MATRICES

Keywords: nitrogen implantation, fcc metal matrix, expanded austenite, hardening

In this work, a comparative study on the effects of a low energy, high-flux nitrogen implantation at moderate temperature on different fcc metallic matrices (Ni, NiCr 20 and FeCr 20 Ni 10 ) is presented. The nitrided layer main features (thickness, composition and surface roughness) will be shown to be markedly dependant on the original substrate composition. As calculated by thermodynamic analyses, the low chemical affinity of pure nickel towards nitrogen accounts for ineffective nitridation, whereas the presence of chromium clearly promotes nitrogen diffusion into the matrix. Comparatively, N uptake is enhanced in the Fe-rich matrix thus suggesting a beneficial role of iron. As a result, a expanded austenite layer is formed in both Cr-containing substrates which brings about a significant increase in microhardness. Roughening of the nickel surfaces mainly occurs by sputtering whereas nitrogen-induced deformation seems to be the main responsible in the NiCr 20 and FeCr 20 Ni 10 substrates.

1.-Introduction

Nitridation treatments by low energy, high-flux implantation at moderate temperatures (~ 400°C) have been reported to produce relatively thick nitrided layers enhancing all together tribological [1-5] and corrosion resistance [6] in face-centred-cubic (fcc) stainless steels as a result of the formation of a fcc γ N phase (expanded austenite) so long as precipitation of CrN is avoided [7]. Few studies are however devoted to the implantation-diffusion of nitrogen into other metallic matrices. Williamson et al. [8] focused on the study of 16 fcc Fe and Ni-based alloys and already claimed that higher nitrogen solubilities were obtained in the iron-rich materials compared to the nickel-rich alloys and that higher contents of alloying elements were also responsible of enhanced nitrogen incorporation, especially chromium. In addition, the comparative study of the tribological behaviour of a low energy, high-flux nitrided stainless steel and a nickel base alloy (Inconel 600) also showed better resistance of the Fe-rich substrate than the Ni-based alloy because of a thinner nitrided layer developed in the latter [9]. Therefore, in this work it is intended to compare the effects of a low energy high flux nitridation process on three face centred cubic (fcc) metallic structures, namely pure nickel (Ni), a nichrome (NiCr 20 ) and an AISI 304L stainless steel (FeCr 20 Ni 10 ).

2.-Experimental procedure

All the samples were mechanically polished to 1 μm diamond paste (average roughness, R a = 0.01 μm) , then ultrasonically degreased in acetone and subsequently rinsed in 96% ethanol. The major composition and implantation temperature of the fcc materials under investigation are given in Table 1. Prior to nitridation, all the samples were subjected to Ar sputtering (1.2 keV, 0.5 mA.cm -2 for 10 minutes) to remove the naturally forming oxide film that may prevent nitridation [10].

Nitrogen implantation was performed with a Kaufman-type ion source 7.5 cm diameter delivering 55% N 2 + and 45% N + [5], which were accelerated at low energy (1.2 keV), high-flux (1 mA.cm -2 ) for 1 hour to obtain similar doses of 2.25x10 19 cm -2 . The initial vacuum in the chamber is 10 -4 Pa and raises to 10 -2 Pa during implantation. The temperature of the samples was carefully controlled with a thermocouple attached to the back of the samples. Because of the different nitrogen-alloy interactions for similar nitridation conditions, the maximum substrate temperatures values also differed (see Table 1) but never surpassed 500ºC.

Thermodynamic calculations have been performed using the HSC Chemistry software

3.-Results

3.1.-Characterisation of nitrided specimens

The XRD comparative diffractograms are shown in Figure 1. It can be readily observed that in nitrided Ni no additional peaks appear compared to the pattern of the untreated metal. Calculation of the lattice parameters of both untreated and nitrided substrates leads to similar results (a 0 ≈ 0.351 nm), which confirms that no expansion of the fcc lattice has occurred by nitrogen solid solution in nickel.

Conversely, after nitridation, the Cr-bearing alloys develop satellite peaks at lower diffraction angles than the initial γ phase indicating the formation of the expanded austenite γ N but no metal nitrides [Figures 1(b) and 1(c)]. X-ray absorption by Ni atoms is known to be weaker than for Fe atoms thus further penetration of the X-rays may occur in the NiCr 20 matrix than in FeCr 20 Ni 10 . Therefore, in order to better compare the differences between both implanted chromium-containing substrates a rough estimation of the retained nitrogen has been carried out as reported by Williamson et al. [8] in which a linear correlation between lattice parameter and atomic concentration was employed using Vegard's law for substitutional solid solution as follows:

a γN =a γ +α•C N ,
where a γN and a γ are the lattice parameters for the N-containing and N-free γ phases, respectively, and α is the Vegard's law constant (0.00072 for Fe alloys, also assumed for Ni alloys in this study [8]). C N is the concentration of nitrogen in atomic %. The results of these calculations are presented in Table 2.

From the results of Table 2, it can be observed that the retained amount of nitrogen in NiCr 20 is significantly lower than in FeCr 20 Ni 10 regardless of the crystallographic plane.

In both substrates however, it would seem that the highest amount of nitrogen concentrates in the (200) planes and the lowest in the (220). The different partitioning of nitrogen in the various planes also brings about different expansion of the lattice, which in turn may induce strains and stresses as will be discussed later.

Figure 2 shows the negative images of the SEM surface morphologies of the different metallic substrates after implantation, hence the lightest areas are deeper and the darkest are higher in real conditions. In pure Ni some grains are dark and the orientation of the dislocation slipping bands composing each grain is underpinned; while other grains are lighter in colour and of smoother appearance. In addition, a significant number of protrusions appear throughout the entire surface, especially at the grain boundaries. In According to EDS microanalyses no nitrogen has been retained in pure Ni either within the grains or at the grain boundaries where more protrusions are observed. However, this can also be due to the poor detection limit of light elements by the EDS technique.

Conversely, different nitrogen contents are found in both chromium-bearing alloys. For instance, in NiCr 20 about 10 at% N is present at the surface regardless of the location whereas in FeCr 20 Ni 10 some of the grains only incorporate about 12 at% N whereas some others contain up to 17 at% N, which is close to the chromium content in the substrate. In order to provide further insight on this issue, AFM investigations have therefore been carried out.

Figure 3 compiles some characteristic 3D AFM images of the three substrates after nitridation and their associated height profiles. The nitrided pure Ni shows a very uneven and grainy surface with roughness values (from 10x10 μm 2 images) that range between 175 and 275 Å. Some of the grains exhibit the aligned bands also observed by SEM (see Fig. 2) and can be ascribed to the slipping bands due to the presence of stress, as also reported in fcc AISI 316 L stainless steel [12]. From the height profile of Ni, it can be observed that the average height is of about 0.3 μm except for the white grain in the centre of the AFM image. In nitrided NiCr 20 however, the surfaces are rather smooth within the grains (average roughness from 10x10 μm 2 images, R a = 50-80 Å) but more significant height differences among grains compared to nitrided Ni. In addition, some of the grains contain relatively large pores as those shown in

Microhardness measurements

The Vickers microhardness values shown in Figure 6 Comparatively, the major hardness increase after nitridation is observed for the FeCr 20 Ni 10 matrix. Indeed, for the shallowest indentation depths (about 1.5 μm) the implanted near surface region is about 4 times harder than the unimplanted one.

Thereafter, hardness progressively decreases towards the values of the untreated steel matrix, which hardness is relatively higher than that of Ni and NiCr 20 .

3.3.-Thermodynamic analyses

Thermodynamic calculations have been carried out with the HSC software [11] taking into account the major compositions of the substrates, i.e. Fe, Ni and Cr, the atmospheric pressure and 10 -2 Pa (implantation conditions) and by implanting the major charged N 2 + (g) species and alternatively, the uncharged N 2 (g). Regardless of the approximation, all the calculations indicate that no nickel nitride forms at least from a thermodynamic point of view. On the contrary, chromium and iron nitrides may form as shown in Figure 7 for the evolution of the free energy of formation with temperature.

The Cr-N reactions are exothermic (ΔH < 0) and spontaneous (ΔG < 0), especially when the uncharged N 2 (g) is reacting with Cr. [Figure 7 As implantation was carried out under similar experimental conditions and the three metallic substrates possess face-centred cubic structures and relative similar grain size, it can be suggested that a chemical effect might be responsible to some extent for the observed differences. Therefore, nitridation in each substrate will be discussed separately. Only the effect of the major elements will be considered as some minor role of carbon atoms has been previously highlighted [e.g. 13,16].

4.1.-Nitridation in pure nickel

It has been shown by conventional θ-2θ X-ray diffraction (Figure 1a) that no extra peak appears as a result of the formation of a new phase compared to the untreated Ni matrix.

This observation is supported by the HSC thermodynamic analyses and with the fact that no binary phase diagram exists in the literature [START_REF]Smithells Metals Reference Book[END_REF] but is in contrast to previous results in which the appearance of the (102) peak of hexagonal Ni 3 N and retention of about 0.4 at% N in the γ phase were reported using 700 eV and a higher flux (2 mA•cm - 2 ) at 400º C for 15 min [8]. Such nitrogen content obviously falls within the detection limit of the EDS technique employed in this present study, but can be considered as negligible. Therefore, the roles of energy and ion flux are of ground importance as thoroughly discussed by Wei [START_REF] Wei | [END_REF] and more recently by Abrasonis [13,16,17].

Sputtering of the surface is also accompanied by an increase in surface roughness (Figure 3), which value varies from grain to grain (150-275 Å) and probably induces twinning (Figure 5). Moreover, a high number of pores appear on the surface of the nitrided specimens (Figure 2). Indeed, incorporation of nitrogen in nickel has been reported to occur by ion implantation as far as the temperature of 375ºC is not surpassed [18] because otherwise nitrogen will be released due to its low solubility in Ni [START_REF] Hansen | Constitution of Binary Alloys 2 nd Ed[END_REF].

According to the work of Pranevicius et al. [START_REF] Pranevicius | [END_REF] on a fcc AISI 304L stainless steel, the surface roughness can be derived from the competition between surface kinetics and bulk diffusion. Nucleation of roughness would first occur by relocation of adatoms, formation of surface vacancies and removal of atoms, which in turn lead to the appearance of clusters of atoms in other regions of the surface. The development of surface roughness subsequently occurs by further relocation and sputtering of atoms displaced by the ion beam. Thereafter, diffusion of nitrogen seems to occur mainly along grain and sub-grain boundaries creating compressive stresses [21]. In nickel, the metastable incorporation of nitrogen can in fact occur by two paths: through the grains and along the grain boundaries. In the former, nitrogen atoms are forced to diffuse inwardly because of the low energy -high flux implantation process. Within the metallic substrate, atomic nitrogen can then recombine as molecular nitrogen, thus raising locally the pressure and inducing plastic deformation of nickel. As a result, a blistered surface appears (Figure 2). Due to the recession of the metal surface upon implantation, the blisters are peeled off and the pores are then visible. Since the solubility of nitrogen in nickel is very low the observed porosity is rather shallow. The larger number of pores and blisters are however found at the grain and twin boundaries rather than within the grains as also inferred in a previous study [22]. This seems to support the idea that diffusion of nitrogen might be more prone to occur along these short circuit paths, which also become readily saturated in nitrogen thus inducing significant plastic deformation all around.

A likely explanation to the highly anisotropic surface roughness in nickel may be related to the sputtering and nitrogen penetration. Indeed, it is widely accepted that sputtering may randomly occur depending on the incoming ion flow but also on the response of the substrate. As the binding energy is different for each grain, a different sputtering rate can then be expected. Likewise, the ions will lose more energy in collisions if striking against close packed planes compared to less compact planes.

Therefore, electron backscattered diffraction measurements should be carried out to correlate grain orientation to roughness.

4.2.-Nitridation in NiCr 20

In contrast to pure nickel, NiCr 20 is able to retain up to about 10 at% N on average as revealed by EDS microanalyses. The XRD patterns (Figure 1b) clearly depict the formation of the so-called expanded austenite, i.e. an fcc phase with nitrogen in solid solution [START_REF] Wei | [END_REF]. From these XRD patterns no chromium nitride formation has been observed even though decomposition of the γ N phase at 450º C has been quoted to produce Ni and metal nitrides in NiCr 20 [23] and in Inconel 690 (NiCr 30 Fe 10 ) [24]. As inferred in Table 2, the expansion of the (200) planes is twice that of the remaining planes. Previous studies on plasma nitriding of Inconel 690 [24,25] also showed a larger width of the (200) peaks compared to the other reflections but disagreed with the idea of different N contents for (200) and (111) suggested by Ozturk and Williamson [26].

Conversely, the explanation of such feature has been put forward in terms of the likely anisotropy of stress on strain, plastic deformation of the nitrided layer and the possible incidence of oxygen in each crystallographic plane. The latter factor could in principle be rejected in our study because of the Ar + cleaning treatment carried out prior to nitridation [16].More recently, it has been suggested that the faster nitriding rate in the grains that contribute to the (200) reflection could adequately be explained by the formation of stacking faults together with the stress generated thus bring about the anomalous expansion of the (200) planes [12].

As discussed above for Ni, roughness can result from ion induced atomic processes on the surface and plastic deformation. However, roughness in NiCr 20 is the lowest among the three implanted materials (see Figure 3). In fact, only from thermodynamic considerations (Figures 7 and8) when implanting either N 2 (g) or N 2 + (g) chromium shows a strong tendency to form either the fcc CrN (ΔHº =-40 kJ.mol -1 ) or the hcp Cr 2 N (ΔHº =-38 kJ.mol -1 ) phases, which have not been observed experimentally. However, this may indicate that Cr can significantly increase N solubility in Ni. On the other hand, Rivière and co-workers [27] already indicated that although preferential bonding occurred between N and Cr, no defined nitride formed in a FeCr 20 Ni 10 substrate and concluded that Cr played a specific role in the atomic transport of nitrogen [28], rather in agreement with the trapping-detrapping mechanism proposed by Möller et al. [29].

This means that most of nitrogen arriving at the surface can remain in the matrix due to enhanced solubility, diffuse inwardly and be trapped at chromium atoms. However, at the implantation temperature (450ºC) chromium may also diffuse outwardly [2,15] and preferentially interact with nitrogen thus developing less porosity than in pure Ni, where the excess nitrogen tends to form bubbles [30]. Incorporation of nitrogen would then lead to swelling of the grains due to a faster nitriding rate in the (200) oriented grains [12] and plastic deformation of the fcc lattice [31].

4.3.-Nitridation in FeCr 20 Ni 10

Using similar experimental conditions as for pure Ni and NiCr 20 , the Fe-base alloy mainly develops the expanded austenite (γ N ) phase on its surface (Figure 1c). The approach of Vegard's law for substitutional solid solutions indicates that more nitrogen has been retained compared to NiCr 20 (Table 2) but its distribution is also highly anisotropic and follows the same trend as for NiCr 20 , i.e. more lattice expansion seems to occur for the grains reflecting the (200) planes. Therefore, assuming homogeneous distribution of chromium in both matrices, it can be deduced that anisotropy only arises from mechanical effects. Indeed, by comparing single crystal and polycrystalline steel substrates it has been recently suggested [12,16] that as nitrogen is incorporated to the fcc matrix, compressive stresses are generated that lead to distortions, plastic deformation and even lattice rotations in an anisotropic fashion because the {001} planes have less slip systems than other planes [31]. As a result of the anisotropic deformation, heterogeneous diffusion will occur thus modifying the nitrogen ingress rate [12].

Furthermore, the FeCr 20 Ni 10 develops the roughest surface among the three studied substrates (Figures 2 and3), but a small number of relatively deep pores. As previously mentioned, surface roughness can originate from ion induced atomic processes on the surface and plastic deformation by misfit dislocation glide as nitrogen is incorporated into the matrix [21]. However, the differences in surface roughness between both chromium containing substrates are rather significant. Indeed, Rivière et al. [27] found by X-ray photoelectron experiments that nitrogen was always detected in a nitride type state and that it was preferentially bound to chromium, without specific nitride formation. Similarly, a small amount of iron atoms showed the same nitride type bonding but only at the outermost surface. Therefore, iron interaction together with a lower nickel content (which rejects nitrogen) results in higher nitrogen supersaturation in the superficial layers of FeCr 20 Ni 10 than in NiCr 20 . Thereafter, because of the difference in chemical potentials between the external layer and the bulk, diffusion will be enhanced. As a result, the Fe-based alloy, which incorporates more nitrogen will exhibit a higher degree of deformation. This induces significant swelling of the grains, thus developing rougher surfaces. Due to the nitrogen contents retained in the Fe-based alloy (up to 17 at%), a mixed γ N + γ region probably develops at the outermost surface and the resulting hardness (12 GPa, cf. Figure 6) is lower than the 20-22 GPa reported in the literature for a high nitrogen containing γ N phases [8].

5.-Conclusion

Similar low energy, high flux nitridation processing conditions on different fcc metallic substrates lead to very different results depending on the chemical composition of the matrix. It has been shown that pure nickel does not develop an expanded austenite phase due to rejection of nitrogen. The tiny retained amount of nitrogen creates blisters and pores as nitrogen tries to be triggered off the substrate. The major surface roughness is then developed by sputtering. On the contrary, once chromium is added, a expanded austenite phase develops but nitrogen uptake is still limited by nickel rejection. In turn, iron atoms can thermodynamically favour nitrogen uptake at least at the outermost surface. The higher the nitrogen intake, the higher the degree of deformation including and grain swelling, which leads to rougher and harder surfaces.

List of tables

  [11] to assess the thermodynamically stable compounds expected to form within the different matrices. The calculations have been carried out at equilibrium conditions at 10 -2 Pa (implantation conditions) and at atmospheric pressure (after implantation) disregarding collision cascades and sputtering of the surfaces. Only the gas species N 2 + (g) or N 2 (g) have been considered to react with the substrates, thus taking into account the splitting of the molecules into 2 nitrogen atoms and the corresponding energy release.After nitridation, the samples were characterised using contact mode atomic force microscopy (AFM) with an Autoprobe CPR (Veeco Instruments), X-ray diffraction (XRD) in the Bragg-Brentano configuration of a Bruker AXS D-5005 equipment using a copper anode (Cu K α1 = 0.15406 nm) and scanning electron microscopy (SEM) coupled to energy-dispersive spectrometry (EDS) in a JEOL JSM-5410LV. Acquisition of the microhardness values at different depths of the nitrided and non nitrided specimens has been carried in a Shimadzu Type M microhardness tester by increasing the applied load. 10 indentations have been carried out for each load to better average the actual microhardness values.

NiCr 20 the

 20 surface is rather uniform and smooth with no protrusions but with relatively coarse pores. The FeCr 20 Ni 10 surface is the most heterogeneous of all three fcc nitrided substrates. As in pure Ni, some of the grains exhibit aligned dislocation slipping bands, whereas other are relatively smooth and remind those of NiCr 20 . As opposed to pure Ni and NiCr 20 neither protrusions nor porosity are observed though.

Figure 4 .Figure 4 )

 44 Figure 4) thus reminding of the NiCr 20 grains, whereas some other grains resemble more the nitrided pure Ni by underlining the slipping bands, hence being rougher (see height profile). A common feature observed on the three alloys is the occurrence of twinning within the grains, but again the morphology of twins differs from one matrix to the other as shown on Figure 5. In nitrided nickel [Figure 5 (a)] the twin seems to modify the sputtering behaviour thus giving rise to a different surface morphology on both sides of the twin. Conversely, in the iron-rich matrix [Figure 5 (b)], the twin has been fully peeled off giving rise to an even morphology of the grain.

  have been averaged from 10 indentations on each specimen surface. From one set of measurements to the other, the applied load was increased, which allows to plot the estimated indentation depth in the abscissa. In pure Ni [Figure6(a)], both the untreated and nitrided specimens follow the same hardness trend, in which the uppermost surface layers are harder than the innermost ones and it is typically associated to the plastic deformation induced upon mechanical polishing of the samples. However, careful inspection of the hardness values indicates that implantation has brought about a slight superficial hardening (around 12%), which might be related the deformation induced upon implantation, hence inducing plastic deformation of the near surface region. It is also interesting to remark that after the nitridation process, an overall softening of the whole matrix occurs compared to raw Ni as assessed by the displacement to the right of the indentation depth and which may arise from metallurgical recovery at the implantation temperature.After implantation of the NiCr 20 substrates [Figure6(b)], a significant difference of hardness of the extreme surface (about 20%) is readily observable up to about 2 μm, from which the same hardness values are found for both untreated and nitrided specimens. Again, in this sample hardening could have been produced by plastic deformation during mechanical polishing. However, since the procedure was the same for Ni and NiCr 20 , the hardness increase can be attributed to solid solution hardening (γ N phase formation).

  Figure8(a) that CrN will be more prone to occur than Cr 2 N at the implantation temperature of the stainless steel (410ºC). On the contrary, at 450ºC (nitridation temperature of NiCr 20 ) the thermodynamic amounts of both chromium nitrides do not significantly differ and thus, competition reactions may occur at the near surface of the NiCr 20 matrix.

  .M. Jones, S.J. Bull, Surf. Coatings Technol. 83 (1996) 269. 2. R. Wei, J.J. Vajo, P.J. Wilbur, J.A. Davis, D.L. Williamson, G.A. Collins, Surf. Coat. Technol. 83 (1996) 235.

FeCr 20 Ni 10 CFigure 1

 101 Figure 1.-X-ray diffraction patterns obtained in the Bragg-Brentano geometry of the raw materials (dashed lines) and nitrided (solid lines) by implantationdiffusion (NID) on (a) Ni (b) Ni20Cr and (c) Fe10Ni20Cr substrates.

  In pure Ni, roughness development is enhanced because the nickel atoms reject nitrogen, which is inconsistent with the fact that NiCr 20 (80 at% Ni) has in general a smoother surface than FeCr 20 Ni 10 (10 at% Ni). Therefore, chemical interactions between nitrogen and the metallic atoms can help in explaining such phenomenon. Indeed, FeCr 20 Ni 10 and NiCr 20 incorporate different amounts of nitrogen. Möller et al.[29] suggested a mechanism in which nitrogen atoms would diffuse inwardly to form new bonds with chromium atoms in progressively deeper atomic layers. Since the chromium content is the same in both matrices, nickel and iron may be responsible for the observed differences. On the one hand, because nickel rejects nitrogen, the nickel-

	rich substrate (NiCr 20 ) incorporates less nitrogen. On the other hand, from a
	thermodynamic point of view the free enthalpy (ΔG) is more negative (thus, more
	spontaneous reaction) upon the formation of chromium nitrides than that of iron nitrides
	(Figures 7). However, the iron effect cannot be neglected if the chemical potential of the

species is also taken into account; i.e. when one mole of nitrogen encounters the substrate surface 70% of the atoms are composed of iron and only 20% of chromium.

Table 1 .

 1 Substrates major composition (at%), and the corresponding maximum temperatures achieved upon nitridation.

	substrate	Fe	Cr	Ni	T (ºC)
	FeCr 20 Ni 10	70	20	10	410
	NiCr 20	-	20	80	450
	Ni	-	-	∼ 100	470

Table 2 .

 2 Lattice parameters of the N-containing γ N and N-free γ austenite phases, the relative expansion induced, an their corresponding average atomic nitrogen contents, C N , as a function of the diffraction plane (hkl) in NiCr 20 and FeCr 20 Ni 10 substrates.

		hkl	111	200	220	311
		a γN , nm	0.3580	0.3637	0.3589	0.3612
	NiCr 20	a γ , nm expansion, %	0.3538 1.2	0.3540 2.8	0.3545 1.2	0.3548 1.8
		C N , at%	∼ 6	13.5	6	∼ 9
		a γN , nm	0.3666	0.3716	0.3666	0.3683
		a γ , nm	0.3572	0.3583	0.3583	0.3583
		expansion, %	2.6	3.7	2.3	2.7

Profile across line