Jean-Yves Charbonnel
email: jean-yves.charbonnel@imj-prg.fr

ON THE COMMUTING VARIETY OF A REDUCTIVE LIE ALGEBRA

Keywords: Mathematics Subject Classification. 14A10, 14L17, 22E20, 22E46 polynomial algebra, complex, commuting variety, Cohen-Macaulay, homology, projective dimension, depth

On the Commuting variety of a reductive Lie algebra.

Introduction

In this note, the base field k is algebraically closed of characteristic 0, g is a reductive Lie algebra of finite dimension, ℓ is its rank, and G is its adjoint group.

1.1. The dual of g identifies to g by a non degenerate symmetric bilinear form on g extending the Killing form of the derived algebra of g. Denote by (v, w) → v, w this bilinear form and denote by I g the ideal of k[g × g] generated by the functions (x, y) → v, [x, y] 's with v in g. The commuting variety C(g) of g is the subvariety of elements (x, y) of g × g such that [x, y] = 0. It is the underlying variety to the subscheme S(g) of g × g defined by I g . It is a well known and long standing open question whether or not this scheme is reduced, that is C(g) = S(g). According to Richardson [START_REF] Richardson | Commuting varieties of semisimple Lie algebras and algebraic groups[END_REF], C(g) is irreducible and according to Popov [Po08, Theorem 1], the singular locus of S(g) has codimension at least 2 in C(g). Then, according to Serre's normality criterion, arises the question to know whether or not C(g) is normal. There are many results about the commuting variety. A result of Dixmier [START_REF] Dixmier | Champs de vecteurs adjoints sur les groupes et algèbres de Lie semi-simples[END_REF] proves that I g contains all the elements of the radical of I g which have degree 1 in the second variable. In [Ga-Gi06], Gan and Ginzburg prove that for g simple of type A, the invariant elements under G of I g is a radical ideal of the algebra k[g × g] G of invariant elements of k[g × g] under G. In [START_REF] Ginzburg | Isospectral commuting variety, the Harish-Chandra D-module, and principal nilpotent pairs[END_REF], Ginzburg proves that the normalisation of C(g) is Cohen-Macaulay.

1.2. Main results and sketch of proofs. According to the identfication of g and its dual, k[g × g] equals the symmetric algebra S(g × g) of g × g. The main result of this note is the following theorem:

Theorem 1.1. The subscheme of g × g defined by I g is Cohen-Macaulay and normal. Furthermore, I g is a prime ideal of S(g × g).

According to Richardson's result and Popov's result, it suffices to prove that the scheme S(g) is Cohen-Macaulay. The main idea of the proof in the theorem uses the main argument of the Dixmier's proof: for a finitely generated module M over S(g × g), M = 0 if the codimension of its support is at least l + 2 with l the projective dimension of M (see Appendix A).

Introduce the characteristic submodule of g, denoted by B g . By definition, B g is a submodule of S(g × g) ⊗ k g and an element ϕ of S(g × g) ⊗ k g is in B g if and only if for all (x, y) in g × g, ϕ(x, y) is in the sum of subspaces g ax+by with (a, b) in k 2 \ {0} and g ax+by the centralizer of ax + by in g. According to a Bolsinov's result, B g is a free S(g × g)-module of rank b g , the dimension of the Borel subalgebras of g. Moreover, the orthogonal complement of B g in S(g × g) ⊗ k g is a free S(g × g)-module of rank b gℓ. These two results are fundamental in the proof of the following proposition: Proposition 1.2. For i positive integer, the submodule i (g) ∧ b g (B g ) of S(g × g) ⊗ k i+b g (g) has projective dimension at most i.

Denoting by E the quotient of S(g × g) ⊗ k g by B g , let E i be the quotient of i (E) by its torsion module. The S(g × g)-modules i (g) ∧ b g (B g ) and E i are isomorphic. Furthermore, for i ≥ 2, E i is isomorphic to a direct factor of the quotient of E ⊗ S(g×g) E i-1 by its torsion module. Denoting by E i-1 this quotient, the projective dimension of E i-1 is at most

d i-1 + 1 if d i-1 is the projective dimension of E i-1
, whence a proof of the proposition by induction on i.

Let d be the S(g × g)-derivation of the algebra S(g × g) ⊗ k (g) such that for all v in g, dv is the function on g × g, (x, y) → v, [x, y] . Then the ideal of S(g × g) ⊗ k (g) generated by b g (B g ) is a graded subcomplex of the graded complex S(g × g) ⊗ k (g). The support of the homology of this complex is contained in C(g). Then we deduce from Proposition 1.2 that this complex has no homology in degree different from b g and k[C(g)] is Cohen-Macaulay by Auslander-Buchsbaum's theorem.

Notations.

• For V a module over a k-algebra, its symmetric and exterior algebras are denoted by S(V) and (V) respectively. If E is a subset of V, the submodule of V generated by E is denoted by span(E). When V is a vector space over k, the grassmannian of all d-dimensional subspaces of V is denoted by Gr d (V).

• All topological terms refer to the Zariski topology. If Y is a subset of a topological space X, denote by

Y the closure of Y in X. For Y an open subset of the algebraic variety X, Y is called a big open subset if the codimension of X \ Y in X is at least 2.
For Y a closed subset of an algebraic variety X, its dimension is the biggest dimension of its irreducible components and its codimension in X is the smallest codimension in X of its irreducible components. For X an algebraic variety, k[X] is the algebra of regular functions on X.

• All the complexes considered in this note are graded complexes over Z of vector spaces and their differentials are homogeneous of degree -1 and they are denoted by d. As usual, the gradation of the complex is denoted by C • .

• The dimension of the Borel subalgebras of g is denoted by b g . Set n := b gℓ so that dim g = 2b gℓ g = 2n + ℓ.

• The dual g * of g identifies with g by a given non degenerate, invariant, symmetric bilinear form ., . on g × g extending the Killing form of [g, g].

• For x ∈ g, denote by g x the centralizer of x in g. The set of regular elements of g is

g reg := {x ∈ g | dim g x = ℓ}.
The subset g reg of g is a G-invariant open subset of g. According to [V72], g \ g reg is equidimensional of codimension 3.

• Denote by S(g) g the algebra of g-invariant elements of S(g). Let p 1 , . . . , p ℓ be homogeneous generators of S(g) g of degree d 1 , . . . , d ℓ respectively. Choose the polynomials p 1 , . . . , p ℓ so that

d 1 ≤ • • • ≤ d ℓ .
For i = 1, . . . , ℓ and (x, y) ∈ g × g, consider a shift of p i in direction y: p i (x + ty) with t ∈ k. Expanding p i (x + ty) as a polynomial in t, one obtains

p i (x + ty) = d i m=0 p (m) i (x, y)t m ; ∀(t, x, y) ∈ k × g × g (1)
where y → (m!)p (m) i (x, y) is the derivative at x of p i at the order m in the direction y. The elements p (m) i defined by (1) are invariant elements of S(g) ⊗ k S(g) under the diagonal action of G in g × g. Remark that p (0) i (x, y) = p i (x) while p (d i ) i (x, y) = p i (y) for all (x, y) ∈ g × g.

Remark 1.3. The family P x := {p (m) i (x, .);

1 ≤ i ≤ ℓ, 1 ≤ m ≤ d i } for x ∈ g, is a
Poisson-commutative family of S(g) by Mishchenko-Fomenko [START_REF] Mishchenko | Euler equations on Lie groups[END_REF]. One says that the family P x is constructed by the argument shift method.

• Let i ∈ {1, . . . , ℓ}. For x in g, denote by ε i (x) the element of g given by

ε i (x), y = d dt p i (x + ty) | t=0
for all y in g. Thereby, ε i is an invariant element of S(g) ⊗ k g under the canonical action of G. According to [Ko63, Theorem 9], for x in g, x is in g reg if and only if ε 1 (x), . . . , ε ℓ (x) are linearly independent. In this case, ε 1 (x), . . . , ε ℓ (x) is a basis of g x . Denote by ε (m) i , for 0 ≤ m ≤ d i -1, the elements of S(g × g) ⊗ k g defined by the equality:

ε i (x + ty) = d i -1 m=0 ε (m) i (x, y)t m , ∀(t, x, y) ∈ k × g × g (2)
and set: V x,y := span({ε i (x, y) (0) , . . . , ε i (x, y) (d i -1) , i = 1, . . . , ℓ}) for (x, y) in g × g.

Characteristic module

For (x, y) in g × g, set:

V ′ x,y = (a,b)∈k 2 \{0}
g ax+by , and denote by P x,y the span of x and y. By definition, the characteristic module B g of g is the submodule of elements ϕ of S(g × g) ⊗ k g such that ϕ(x, y) is in V ′ x,y for all (x, y) in g × g. In this section, some properties of B g are given.

2.1. Denote by Ω g the subset of elements (x, y) of g × g such that P x,y has dimension 2 and such that P x,y \ {0} is contained in g reg . According to [CMo08, Corollary 10], Ω g is a big open subset of g × g.

Proposition 2.1. Let (x, y) be in g × g such that P x,y ∩ g reg is not empty.

(

[x, V x,y ] is the orthogonal complement of V x,y in g. (v) The space V x,y is contained in V ′ x,y . Moreover, V x,y = V ′ x,y if (x, y) is in Ω g . (vi) For i = 1, . . . , ℓ and for m = 0, . . . , d i -1, ε (m) i is a G-equivariant map. Proof. (i) For pairwise different elements t i,1 , . . . , t i,d i -1 , i = 1, . . . , ℓ of k \ {0}, the ε (m)
i (x, y)'s, m = 0, . . . , d i -1 are linear combinations of the ε i (x + t i, j y)'s, j = 1, . . . , d i -1 for i = 1, . . . , ℓ. Furthermore, for all z in g reg , ε 1 (z), . . . , ε ℓ (z) is a basis of g z by [Ko63, Theorem 9], whence the assertion since the maps ε 1 , . . . , ε ℓ are homogeneous.

(ii) Let O be an open subset of (k \ {0}) 2 such that ax + by is in g reg for all (a, b) in O. For all (a, b) in O, [x, g ax+by ] = [y, g ax+by ] since [ax + by, g ax+by ] = 0 and since ab 0, whence the assertion by (i).

(iii) According to [Bou02, Ch. V, §5, Proposition 3],

d 1 + • • • + d ℓ = b g . So V x,y has dimension at most b g . By [Bol91, Theorem 2.1], V x,y has dimension b g if and only if (x, y) is in Ω g . (iv) According to [Bol91, Theorem 2.1], V x,
y is a totally isotropic subspace with respect to the skew bilinear form on g

(v, w) -→ ax + by, [v, w] for all (a, b) in k 2 . As a result, by invariance of ., . , V x,y is orthogonal to [x, V x,y ]. If (x, y) is in Ω g , g x has dimension ℓ and it is contained in V x,y . Hence, by (iii), dim [x, V x,y ] = b g -ℓ = dim g -dim V x,y so that [x, V x,y ] is the orthogonal complement of V x,y in g. Conversely, if [x, V x,y ] is the orhogonal com- plement of V x,y in g, then dim V x,y + dim [x, V x,y ] = dim g.
Since P x,y ∩ g reg is not empty, g ax+by ∩ V x,y has dimension ℓ for all (a, b) in a dense open subset of k 2 . By continuity, g x ∩ V x,y has dimension at least ℓ so that 2dim V x,yℓ ≥ dim g.

Hence, by (iii), (x, y) is in Ω g . (v) According to [Ko63, Theorem 9], for all z in g and for i = 1, . . . , ℓ, ε i (z) is in g z . Hence for all t in k,

ε i (x + ty) is in V ′ x,y . So ε (m) i (x, y) is in V ′ x,y for all m, whence V x,y ⊂ V ′ x,y . Suppose that (x, y) is in Ω g . According to [Ko63, Theorem 9], for all (a, b) in k 2 \ {0}, ε 1 (ax + by), . . . , ε ℓ (ax + by
) is a basis of g ax+by . Hence g ax+by is contained in V x,y , whence the assertion.

(vi) Let i be in {1, . . . , ℓ}.

Since p i is G-invariant, ε i is a G-equivariant map. As a result, its 2- polarizations ε (0) i , . . . , ε (d i -1) i are G-equivariant under the diagonal action of G in g × g.
Theorem 2.2. (i) The module B g is a free module of rank b g whose a basis is the sequence

ε (0) i , . . . , ε (d i -1) i , i = 1, . . . , ℓ. (ii) For ϕ in S(g × g) ⊗ k g, ϕ is in B g if and only if pϕ ∈ B g for some p in S(g × g) \ {0}. (iii) For all ϕ in B g and for all (x, y) in g × g, ϕ(x, y) is orthogonal to [x, y].
Proof. (i) and (ii) According to Proposition 2.1,(v), ε (m) i is in B g for all (i, m). Moreover, according to Proposition 2.1,(iii), these elements are linearly independent over S(g × g). Let ϕ be an element of

S(g × g) ⊗ k g such that pϕ is in B g for some p in S(g × g) \ {0}. Since Ω g is a big open subset of g × g, for all (x, y) in a dense open subset of Ω g , ϕ(x, y) is in V x,y by Proposition 2.1,(v). According to Proposition 2.1,(iii), the map Ω g -→ Gr b g (g), (x, y) -→ V x,y
is regular. So, ϕ(x, y) is in V x,y for all (x, y) in Ω g and for some regular functions a i,m , i = 1, . . . , ℓ, m = 0, . . . ,

d i -1 on Ω g , ϕ(x, y) = ℓ i=1 d i -1 m=0 a i,m (x, y)ε (m) i (x, y)
for all (x, y) in Ω g . Since Ω g is a big open subset of g × g and since g × g is normal, the a i,m 's have a regular extension to g × g. Hence ϕ is a linear combination of the ε (m) i 's with coefficients in S(g × g). As a result, the sequence ε (m) i , i = 1, . . . , ℓ, m = 0, . . . , d i -1 is a basis of the module B g and B g is the subset of elements ϕ of S(g × g) ⊗ k g such that pϕ ∈ B g for some p in S(g × g) \ {0}.

(iii) Let ϕ be in B g . According to (i) and Proposition 2.1,(iv), for all (x, y) in Ω g , [x, ϕ(x, y)] is orthogonal to V x,y . Then, since y is in V x,y , [x, ϕ(x, y)] is orthogonal to y and ϕ(x, y), [x, y] = 0, whence the assertion.

2.2. Also denote by ., . the natural extension of ., . to the module S(g × g) ⊗ k g.

Proposition 2.3. Let C g be the orthogonal complement of B g in S(g × g) ⊗ k g. (i) For ϕ in S(g × g) ⊗ k g, ϕ is in C g if and only if ϕ(x, y) is in [x, V x,y ] for all (x, y) in a nonempty open subset of g × g.
(ii) The module C g is free of rank b gℓ. Furthermore, the sequence of maps

(x, y) → [x, ε (1) i (x, y)], . . . , (x, y) → [x, ε (d i -1) i (x, y)], i = 1, . . . , ℓ is a basis of C g . (iii) The orthogonal complement of C g in S(g × g) ⊗ k g equals B g . Proof. (i) Let ϕ be in S(g × g) ⊗ k g. If ϕ is in C g , then ϕ(x, y) is orthogonal to V x,y for all (x, y) in Ω g .
Then, according to Proposition 2.1,(iv), ϕ(x, y) is in [x, V x,y ] for all (x, y) in Ω g . Conversely, suppose that ϕ(x, y) is in [x, V x,y ] for all (x, y) in a nonempty open subset V of g × g. By Proposition 2.1,(iv) again, for all (x, y) in V ∩ Ω g , ϕ(x, y) is orthogonal to the ε (m) i (x, y)'s, i = 1, . . . , ℓ, m = 0, . . . , d i -1, whence the assertion by Theorem 2.1.

(ii) Let C be the submodule of S(g × g) ⊗ k g generated by the maps

(x, y) → [x, ε (1) i (x, y)], . . . , (x, y) → [x, ε (d i -1) i (x, y)], i = 1, . . . , ℓ
According to (i), C is a submodule of C g . This module is free of rank b gℓ since [x, V x,y ] has dimension b gℓ for all (x, y) in Ω g by Proposition 2.1, (iii) and (iv). According to (i), for ϕ in C g , for all (x, y) in Ω g ,

ϕ(x, y) = ℓ i=1 d i -1 m=1 a i,m (x, y)[x, ε (m) i (x, y)]
with the a i,m 's regular on Ω g and uniquely defined by this equality. Since Ω g is a big open subset of g × g and since g × g is normal, the a i,m 's have a regular extension to g × g. As a result, ϕ is in C, whence the assertion.

(iii) Let ϕ be in the orthogonal complement of C g in S(g × g) ⊗ k g. According to (ii), for all (x, y) in Ω g , ϕ(x, y) is orthogonal to [x, V x,y ]. Hence by Proposition 2.1,(iv), ϕ(x, y) is in V x,y for all (x, y) in Ω g . So, by Theorem 2.1, ϕ is in B g , whence the assertion.

Denote by B and C the localizations of B g and C g on g × g respectively. For (x, y) in g × g, let C x,y be the image of C g by the evaluation map at (x, y).

Lemma 2.4. There exists an affine open cover O of Ω g verifying the following condition: for all O in O,

there exist some subspaces E and F of g, depending on O, such that

g = E ⊕ V x,y = F ⊕ C x,y
for all (x, y) in O. Moreover, for all (x, y) in O, the orthogonal complement of V x,y in g equals C x,y .

Proof. According to Proposition 2.1,(iii) and (iv), for all (x, y) in Ω g , V x,y and C x,y have dimension b g and b gℓ respectively so that the maps

Ω g -→ Gr b g (g), (x, y) -→ V x,y , Ω g -→ Gr b g -ℓ (g), (x, y) -→ C x,y
are regular, whence the assertion.

Torsion and projective dimension

Let E and E # be the quotients of S(g × g) ⊗ k g by B g and C g respectively. For i positive integer, denote by E i the quotient of i (E) by its torsion module.

Let B *

g and C * g be the duals of B g and C g respectively.

Lemma 3.1. (i) The S(g × g)-modules E and E # have projective dimension at most 1.

(ii) The S(g × g)-modules E and E # are torsion free.

(iii) The modules C g and B g are the duals of E and E # respectively.

(iv) The canonical morphism from E to C * g is an embedding.

Proof. (i) By definition, the short sequences of S(g × g)-modules,

0 -→ B g -→ S(g × g) ⊗ k g -→ E -→ 0 0 -→ C g -→ S(g × g) ⊗ k g -→ E # -→
× g) ⊗ k g, ϕ is in C g if pϕ is in C g for some p in S(g × g) \ {0}
, whence E # is torsion free.

(iii) According to the exact sequences of (i), the dual of E is the orthogonal complement of B g in S(g × g) ⊗ k g and the dual of E # is the orthogonal complement of C g in S(g × g) ⊗ k g, whence the assertion since C g is the orthogonal complement of B g in S(g × g) ⊗ k g by definition and since B g is the orthogonal complement of C g in S(g × g) ⊗ k g by Proposition 2.3,(iii).

(iv) Let ω be in the kernel of the canonical morphism from E to C * g . Let ω be a representative of ω in S(g × g) ⊗ k g. According to Proposition 2.3,(iii), B g is the orthogonal complement of C g in S(g × g) ⊗ k g so that ω is in B g , whence the assertion.

Set:

ε = ∧ ℓ i=1 ε (0) i ∧ • • • ∧ ε (d i -1)
i and for i positive integer, denote by θ i the morphism

S(g × g) ⊗ k i (g) -→ i (g) ∧ b g (B g ), ϕ -→ ϕ ∧ ε.
Proposition 3.2. Let i be a positive integer.

(i) The morphism θ i defines through the quotient an isomorphism from E i onto i (g) ∧ b g (B g ).

(ii) The short sequence of S(g × g)-modules

0 -→ B g ⊗ S(g×g) E i -→ g ⊗ k E i -→ E ⊗ S(g×g) E i -→ 0 is exact.
Proof. (i) For j positive integer, denote by π j the canonical map from S(g × g) ⊗ k j (g) to j (E). Let ω be in the kernel of π i . Let O be an element of the affine open cover of Ω g of Lemma 2.4 and let W be a subspace of g such that g = W ⊕ V x,y for all (x, y) in O so that π 1 induces an isomorphism

k[O] ⊗ k W -→ k[O] ⊗ S(g×g) E
Moreover, B g is the kernel of π 1 . Then, from the equality

k[O] ⊗ k i (g) = i j=0 j (W) ∧ k[O] ⊗ S(g×g) i-j (B g ) it results that the restriction of ω to O is in k[O] ⊗ S(g×g) i-1 (g) ∧ B g .
Hence the restriction of ω ∧ ε to O equals 0 and ω is in the kernel of θ i since i (g) ∧ b g (B g ) has no torsion as a submodule of a free module. As a result, θ i defines through the quotient a morphism from i (E) to i (g) ∧ b g (B g ). Denote it by ϑ ′ i . Since i (g) ∧ b g (B g ) is torsion free, the torsion submodule of i (E) is contained in the kernel of ϑ ′ i . Hence ϑ ′ i defines through the quotient a morphism from E i to i (g) ∧ b g (B g ). Denoting it by ϑ i , ϑ ′ i and ϑ i are surjective since too is θ i .

Let ω be in the kernel of ϑ ′ i and let ω be a representative of ω in S(g × g)

⊗ k i (g). Then ω ∧ ε = 0 so that the restriction of ω to the above open subset O is in k[O] ⊗ S(g×g) i-1 (g) ∧ B g .
As a result, the restriction of ω to O equals 0. So, ω is in the torsion submodule of i (E), whence the assertion.

(ii) By definition, the sequence

0 -→ B g -→ S(g × g) ⊗ k g -→ E -→ 0 is exact. Then the sequence Tor S(g×g) 1 (E, E i ) -→ B g ⊗ S(g×g) E i -→ g ⊗ k E i -→ E ⊗ S(g×g) E i -→ 0
is exact. By definition, E i is torsion free. As a result, B g ⊗ S(g×g) E i is torsion free since B g is a free module. Then, since Tor S(g×g) 1 (E, E i ) is a torsion module, its image in B g ⊗ S(g×g) E i equals 0, whence the assertion.

3.2.

For i positive integer, ., . has a canonical extension to S(g × g) ⊗ k i (g) denoted again by ., . .

Lemma 3.3. Let i be a positive integer. Let T i be the torsion module of E ⊗ S(g×g) E i and let T ′ i be its inverse image by the canonical morphism

g ⊗ k E i → E ⊗ S(g×g) E i .
(i) The canonical morphism from i (E) to i (C * g ) defines through the quotient an embedding of E i into i (C * g ). (ii) The module of T ′ i is the intersection of g ⊗ k E i and B g ⊗ S(g×g) i (C * g ). (iii) The module T ′ i is isomorphic to Hom S(g×g) (E # , E i ). Proof. (i) According to Lemma 3.1,(iii), there is a canonical morphism from i (E) to i (C * g ). Let ω be in its kernel and let ω be a representative of ω in S(g × g) ⊗ k i (g). Then ω is orthogonal to i (C g ) with respect to ., . . So for O as in Lemma 2.4, the restriction of

ω to O is in k[O] ⊗ S(g×g) i-1 (g) ∧ B g .
Hence the restriction of ω to O equals 0. In other words, ω is in the torsion module of i (E), whence the assertion since i (C * g ) is a free module. (ii) Since i (C * g ) is a free module, by Proposition 3.2,(ii), there is a morphism of short exact sequences 0

/ / B g ⊗ S(g×g) E i / / g ⊗ k E i / / E ⊗ S(g×g) E i / / 0 0 / / B g ⊗ S(g×g) i (C * g ) / / g ⊗ k i (C * g ) / / E ⊗ S(g×g) i (C * g ) / / 0
Moreover, the two first vertical arrows are embeddings. Hence T ′ i is the intersection of g ⊗ k E i and B g ⊗ S(g×g) i (C * g ) in g ⊗ k i (C * g ). (iii) According to the identification of g with its dual, g ⊗ k E i = Hom k (g, E i ). Moreover, according to the short exact sequence of S(g × g)-modules

0 -→ C g -→ S(g × g) ⊗ k g -→ E # -→ 0 the sequence of S(g × g)-modules 0 -→ Hom S(g×g) (E # , E i ) -→ Hom k (g, E i ) -→ Hom S(g×g) (C g , E i ) -→ Ext 1 S(g×g) (E # , E i )
is exact. For ϕ in Hom S(g×g) (S(g × g) ⊗ k g, E i ), ϕ is in the kernel of the third arrow if and only if C g is contained in the kernel of ϕ. On the other hand, according to the identification of g and its dual, Hom k (g, i (C * g ) identifies with g ⊗ k i (C * g ). By Proposition 2.3, B g is the orthogonal complement of C g in S(g × g) ⊗ k g and C * g is a free S(g × g)-module. So, for ψ in Hom S(g×g) (S(g × g) ⊗ k g, i (C * g )), ψ equals 0 on C g if and only if it is in B g ⊗ S(g×g) i (C * g ), whence the assertion by (ii).

The following corollary results from Lemma 3.3.

Corollary 3.4. Let i be a positive integer and let E i be the quotient of E ⊗ S(g×g) E i by its torsion module.

Then the short sequence of S(g × g)-modules

0 -→ Hom S(g×g) (E # , E i ) -→ g ⊗ k E i -→ E i -→ 0 is exact.
-→ C g -→ S(g × g) ⊗ k g -→ E # -→ 0 one deduces the exact sequence 0 -→ Hom S(g×g) (E # , M) -→ Hom k (g, M) -→ Hom S(g×g) (C g , M) -→ Ext 1 S(g×g) (E # , M) -→ 0.
Since C g is a free module, Hom S(g×g) (C g , M) is functorially isomorphic to C * g ⊗ S(g×g) M. Then by the right exactness of the functor A g ⊗ S(g×g) •, there is an isomorphism of exact sequences Hom k (g, M)

/ / Hom S(g×g

) (C g , M) / / Ext 1 S(g×g) (E # , M) / / 0 g ⊗ k M / / δ 0 O O C * g ⊗ S(g×g) M / / δ 1 O O A g ⊗ S(g×g) M / / δ O O 0
Since the two sequences depends functorially on M, from the isomorphisms of functors

g ⊗ k • -→ Hom k (g, •), C * g ⊗ S(g×g) • -→ Hom S(g×g) (C g , •)
, we deduce that the restrictions to Mod S(g×g) (0) of the functors Ext 1 S(g×g) (E # , •) and A g ⊗ S(g×g) • are isomorphic.

Suppose the statement true for d -1. Setting Q := ι(S(g × g) ⊗ k g), one has two short exact sequences

0 -→ B g -→ S(g × g) ⊗ k g -→ Q -→ 0, 0 -→ Q -→ C * g -→ A g -→ 0.
Since E # has projective dimension at most 1 by Lemma 3.1, Ext 2 S(g×g) (E # , Z) = 0. Then, by induction hypothesis, one has a commutative diagram

0 0 0 Ext 1 S(g×g) (E # , Z) d / / O O Ext 1 S(g×g) (E # , P) d / / O O Ext 1 S(g×g) (E # , M) / / O O 0 0 / / C * g ⊗ S(g×g) Z d / / δ O O C * g ⊗ S(g×g) P d / / δ O O C * g ⊗ S(g×g) M / / δ M O O 0 Q ⊗ S(g×g) Z d / / δ O O Q ⊗ S(g×g) P d / / δ O O Q ⊗ S(g×g) M / / δ O O 0
with exact lines and columns since C * g is a free module. Let a and a ′ be in C * g ⊗ S(g×g) P such that da

= da ′ . Then a -a ′ = da 1 with a 1 in C * g ⊗ S(g×g) Z so that d•δa -d•δa ′ = d•δ•da 1 = 0 whence a morphism C * g ⊗ S(g×g) M δ M -→ Ext 1 S(g×g) (E # , M) uniquely defined by the equality δ M •d = d•δ. Let a be in Ext 1 S(g×g) (E # , M). Then a = d•δa 1 = δ M •da 1 with a 1 ∈ C * g ⊗ S(g×g) P. Hence δ M is surjective. Let b be in the kernel of δ M . Then b = db 1 , d•δb 1 = 0, δb 1 = d•δb 2 with b 1 ∈ C * g ⊗ S(g×g) P, b 2 ∈ C * g ⊗ S(g×g) Z.
so that b 1db 2 = δb 3 with b 3 in Q ⊗ S(g×g) P, whence b = δ•db 3 . As a result, the above diagram is canonically completed by an exact third column and one has an isomorphism of short exact sequences

Ext 1 S(g×g) (E # , Z) / / Ext 1 S(g×g) (E # , P) / / Ext 1 S(g×g) (E # , M) / / 0 A g ⊗ S(g×g) Z / / O O A g ⊗ S(g×g) P / / O O A g ⊗ S(g×g) M / / O O 0 .
Since the two sequences depends functorially on the short exact sequence 0 -→ Z -→ P -→ M -→ 0 and since the restrictions to Mod S(g×g) (d -1) of the two functors Ext 1 S(g×g) (E # , •) and A g ⊗ S(g×g) • are isomorphic, too is their restrictions to Mod S(g×g) (d), whence the lemma since all object of Mod S(g×g) has a finite projective dimension.

From the exact sequence,

0 -→ B g -→ S(g × g) ⊗ k g -→ C * g -→ A g -→ 0, we deduce the graded homology complex, 0 -→ B g ⊗ S(g×g) E i -→ g ⊗ k E i -→ C * g ⊗ S(g×g) E i -→ A g ⊗ S(g×g) E i -→ 0 denoted by C • .
For i positive integer, let d i and d ′ i be the projective dimensions of E i and Hom S(g×g) (E # , E i ). Lemma 3.6. Let Q be the space of cycles of degree 2 of the complex C • .

(i) Denoting by d ′′ i the projective dimension of Ext 1 S(g×g

) (E # , E i ), d ′ i is at most sup{d ′′ i -2, d i }. (ii)
The complex C • has no homology in degree 0, 1 and 3. Moreover, Q identifies with Hom S(g×g) (E # , E i ). (iii) The module Hom S(g×g) (E # , E i ) has projective dimension at most d i .

Proof. (i) From the short exact sequence

0 -→ C g -→ S(g × g) ⊗ k g -→ E # -→ 0 one deduces the exact sequence 0 -→ Hom S(g×g) (E # , E i ) -→ Hom k (g, E i ) -→ Hom S(g×g) (C g , E i ) -→ Ext 1 S(g×g) (E # , E i ) -→ 0 whence the two short exact sequences 0 -→ Hom S(g×g) (E # , E i ) -→ Hom k (g, E i ) -→ Z -→ 0 0 -→ Z -→ Hom S(g×g) (C g , E i ) -→ Ext 1 S(g×g) (E # , E i ) -→ 0 with Z the image of the arrow Hom k (g, E i ) -→ Hom S(g×g) (C g , E i )
Denoting by d the projective dimension of Z, one deduces the inequalities

d ′ i ≤ sup{d -1, d i }, d ≤ sup{d ′′ i -1, d i } since C g
is a free module, whence the assertion.

(ii) By right exactness of the functor • ⊗ S(g×g) E i , C • has no homology in degree 0 and 1. Moreover, its space of cycles of degree 3 is a torsion submodule of C 3 . Since E i is torsion free and since B g is free, C 3 has no torsion. Hence C • has no homology in degree 3. According to Lemma 3.3,(ii) and (iii), Hom S(g×g) (E # , E i ) identifies with a submodule of g ⊗ k E i . According to these identifications, Q is the space of morphisms from S(g × g) ⊗ k g to E i , equal to 0 on C g , that is Q = Hom S(g×g) (E # , E i ).

(iii) By (ii), one has a short exact sequence

0 -→ Hom S(g×g) (E # , E i ) -→ C * g ⊗ S(g×g) E i -→ A g ⊗ S(g×g) E i -→ 0. So, A g ⊗ S(g×g) E i has projective dimension at most sup{d ′ i + 1, d i }. According to Lemma 3.5, A g ⊗ S(g×g) E i and Ext 1 S(g×g) (E # , E i ) are isomorphic. So by (i), d ′ i ≤ sup{d ′ i -1, d i }, whence d ′ i ≤ d i .
The following corollary results from Corollary 3.4 and Lemma 3.6,(iii), since B g is free.

Corollary 3.7. Let i be a positive integer. Then E i has projective dimension at most d i + 1.

3.4.

For i a positive integer and for M a S(g × g)-module, let consider on M ⊗i the canonical action of the symmetric group S i . For σ in S i , denote by ǫ(σ) its signature. Let M ⊗i sign be the submodule of elements a of M ⊗i such that σ.a = ǫ(σ)a for all σ in S i and let δ i be the endomorphism of M ⊗i ,

a -→ δ i (a) = 1 i! σ∈S i ǫ(σ)σ.a.
Then δ i is a projection of M ⊗i onto M ⊗i sign . For L submodule of C * g , denote by L i the image of L ⊗i by the canonical map from L ⊗i to (C * g ) ⊗i and set L i,sign := L i ∩ (C * g ) ⊗i sign . Let i (L) be the quotient of i (L) by its torsion module. For i ≥ 2, identify S i-1 with the stabilizer of i in S i and denote by L i-1,sign,1 the submodule of elements a of L i such that σ.a = ǫ(σ)a for all σ in S i-1 . Lemma 3.8. Let i be a positive integer and let L be a submodule of C * g . (i) The module L i is isomorphic to the quotient of L ⊗i by its torsion module. (ii) The module L i,sign is isomorphic to i (L). (iii) For i ≥ 2, the module L i,sign is a direct factor of L i-1,sign,1 .

(iv) For i ≥ 2, the module L i-1,sign,1 is isomorphic to the quotient of i-1 (L) ⊗ S(g×g) L by its torsion module.

Proof. (i) Let L 1 and L 2 be submodules of a free module F over S(g × g). From the short exact sequence

0 -→ L 2 -→ F -→ F/L 2 -→ 0 one deduces the exact sequence Tor 1 S(g×g) (L 1 , L 2 ) -→ L 1 ⊗ S(g×g) L 2 -→ L 1 ⊗ S(g×g) F -→ L 1 ⊗ S(g×g) (F/L 2 ) -→ 0.
Since F is free, L 1 ⊗ S(g×g) F is torsion free. Hence the kernel of the second arrow is the torsion module of L 1 ⊗ S(g×g) L 2 since Tor 1 S(g×g) (L 1 , L 2 ) is a torsion module, whence the assertion by induction on i. (ii) There is a commutative diagram

L ⊗i / / δ i (C * g ) ⊗i δ i L ⊗i sign / / (C * g ) ⊗i
sign so that L i,sign is the image of L ⊗i sign by the canonical morphism L ⊗i -→ (C * g ) ⊗i , whence a commutative diagram

L ⊗i sign / / i (L) (C * g ) ⊗i sign / / i (C * g )
According to (i), the kernel of the left down arrow is the torsion module of L ⊗i sign so that the kernel of the right down arrow is the torsion module of i (L) since the horizontal arrows are isomorphisms. Moreover, the image of

L i,sign in i (C * g ) is the image of i (L). Hence i (L) is isomorphic to L i,sign . (iii) Denote by Q i the kernel of the endomorphism δ i of (C * g ) ⊗i . Since δ i is a projection onto (C * g ) ⊗i sign such that δ i (L i ) is contained in L i,sign , (C * g ) ⊗i = (C * g ) ⊗i sign ⊕ Q i , L i = L i,sign ⊕ Q i ∩ L i whence L i-1,sign,1 = L i,sgn ⊕ Q i ∩ L i-1,sign,1 since L i,sign is a submodule of L i-1,sign,1 . (iv) Let L ′ i be the image of L i-1,sign,1 by the canonical morphism (C * g ) ⊗i → i-1 (C * g ) ⊗ S(g×g) C * g . Then L ′ i is contained in i-1 (C * g ) ⊗ S(g×g) L since i-1 (C * g ) ⊗ S(g×g) L is a submodule of i-1 (C * g ) ⊗ S(g×g) C * g . Moreover, the morphism L i-1,sign,1 → L ′ i is an isomorphism since too is the morphism (C * g ) ⊗(i-1) sign ⊗ S(g×g) C * g -→ i-1 (C * g ) ⊗ S(g×g) C * g . From (ii), it results the commutative diagram L ⊗(i-1) sign ⊗ S(g×g) L / / i-1 (L) ⊗ S(g×g) L L i-1,sign,1 / / L ′ i
with the right down arrow surjective. According to (i), the kernel of the left down arrow is the torsion module of L ⊗(i-1)

sign ⊗ S(g×g) L. Hence the kernel of the right down arrow is the torsion module of i-1 (L)⊗ S(g×g) L, whence the assertion. Proposition 3.9. Let i be a positive integer. Then E i and i (g) ∧ b g (B g ) have projective dimension at most i.

Proof. According to Proposition 3.2,(i), the modules E i and i (g) ∧ b g (B g ) are isomorphic. Prove by induction on i that E i has projective dimension at most i. By Lemma 3.1,(i), it is true for i = 1. Suppose that it is true for i -1. According to Corollary 3.7, E i-1 has projective dimension at most i. By Lemma 3.8, for L = E, E i is a direct factor of E i-1 since E is a submodule of C * g by Lemma 3.1,(iv) and since E i = i (E). Hence E i has projective dimension at most i.

Main results

Let I g be the ideal of S(g × g) generated by the functions (x, y) → v, [x, y] with v in g. The nullvariety of I g in g × g is C(g). Let d be the S(g × g)-derivation of the algebra S(g × g) ⊗ k (g) such that dv is the function (x, y) → v, [x, y] on g × g for all v in g. The gradation on (g) induces a gradation on S(g × g) ⊗ k (g) so that S(g × g) ⊗ k (g) is a graded homology complex.

Lemma 4.1. Denote by C • (g) the graded submodule (g) ∧ b g (B g ) of S(g × g) ⊗ k (g). (i) The graded module C • (g) is a graded subcomplex of S(g × g) ⊗ k (g). (ii) The support of the homology of C • (g) is contained in C(g). Proof. (i) Set: ε := ∧ ℓ i=1 ε (0) i ∧ • • • ∧ ε (d i -1) i . Then C • (g) is the ideal of S(g × g) ⊗ k (g) generated by ε since ε (0) i , . . . , ε (d i -1) i , i = 1, .
. . , ℓ is a basis of B g by Theorem 2.2,(i). According to Theorem 2.2,(iii), for i = 1, . . . , ℓ and for m = 0, . . . , d i -1, ε (m) i is a cycle of the complex S(g × g) ⊗ k (g). Hence too is ε and C • (g) is a subcomplex of S(g × g) ⊗ k (g) as an ideal generated by a cycle.

(ii) Let (x 0 , y 0 ) be in g × g \ C(g) and let v be in g such that v, [x 0 , y 0 ] 0. For some affine open subset O of g × g, containing (x 0 , y 0 ), v, [x, y] 0 for all (x, y) in O. Then dv is an invertible element of k

[O]. For c a cycle of k[O] ⊗ S(g×g) C • (g), d(v ∧ c) = (dv)c so that c is a boundary of k[O] ⊗ S(g×g) C • (g).
Theorem 4.2. (i) The complex C • (g) has no homology in degree bigger than b g .

(ii) The ideal I g has projective dimension 2n -1.

(iii) The algebra S(g × g)/I g is Cohen-Macaulay.

(iv) The projective dimension of the module n (g) ∧ b g (B g ) equals n.

Proof. (i) Let Z be the space of cycles of degree b g + 1 of C • (g). Then we deduce from C • (g) the complex

0 -→ C 2n+ℓ (g) -→ • • • -→ C n+ℓ+2 (g) -→ Z -→ 0.
According to Lemma 4.1,(ii), the support of its homology is contained in C g . In particular, its codimension in g × g is 4n

+ 2ℓ -(2n + 2ℓ) = 2n = n + n -1 + 1
ψ of P j+1 whose image ψ ′ in H 0 (X, K j ) has the same restriction to X \ S as ϕ. Since P j is a projective module and since X is irreducible, P j is torsion free. Then ϕ = ψ ′ since ϕψ ′ is a torsion element of P j , whence the assertion.

(ii) Let R ′ be the localization of R ′ on X. Arguing as in (i), since S contains the support of R ′ /R and since 1 < pl, the short sequence 0 -→ H 0 (X \ S , K 0 ) -→ H 0 (X \ S , P 0 ) -→ H 0 (X \ S , R ′ ) -→ 0 is exact. Moreover, the restriction morphism from P 0 to H 0 (X/S , P 0 ) is an isomorphism since the codimension of S in X is at least 2 and since X is irreductible and normal. Let ϕ be in R ′ . Then for some ψ in P 0 , ϕε(ψ) is a torsion element of R ′ . So ϕ = ε(ψ) since R ′ is torsion free, whence the assertion.

Corollary A.3. Let C • be a homology complex of finite k[X]-modules whose length l is finite and positive. For j = 0, . . . , l, denote by Z j the space of cycles of degree j of C • . Suppose that the following conditions are verified:

(1) S contains the support of the homology of the complex C • , (2) for all i, C i is a submodule of a free module, (3) for i = 1, . . . , l, C i has projective dimension at most d, (4) X is normal and l + d ≤ p -1.

Then C • is acyclic and for j = 0, . . . , l, Z j has projective dimension at most l + dj -1.

Proof. Prove by induction on lj that the complex 0 -→ C l -→ • • • -→ C j+1 -→ Z j -→ 0 is acyclic and that Z j has projective dimension at most l + dj -1. For j = l, Z j equals zero since C l is torsion free by Condition (2) and since Z l a submodule of C l , supported by S by Condition (1). Suppose j ≤ l -1 and suppose the statement true for j + 1. By Condition (3), C j+1 has a projective resolution P • whose length is at most d and whose terms are finitely generated. By induction hypothesis, Z j+1 has a projective resolution Q • whose length is at most l + dj -2 and whose terms are finitely generated, whence an augmented complex R • of projective modules whose length is l + dj -1, 0 -→ Q l+d-j-2 ⊕ P l+d-j-1 -→ • • • -→ Q 0 ⊕ P 1 -→ P 0 -→ Z j -→ 0.

Denoting by d the differentials of Q • and P • , the restriction to Q i ⊕ P i+1 of the differential of R • is the map (x, y) → (dx, dy + (-1) i δ(x)), with δ the map which results from the injection of Z j+1 into C j+1 . Since P • and Q • are projective resolutions, the complex R • is a complex of projective modules having no homology in positive degree. Hence the support of the homology of the augmented complex R • is contained in S by Condition (1). Then, by Proposition A.2 and Condition (4), R • is a projective resolution of Z j of length l + dj -1 since Z j is a submodule of a free module by Condition (2), whence the corollary since Z 0 = C 0 by definition.

Remark A.4. Let D(X) be the bounded derived category of finite k[X]-modules. For E an object of D(X), denote by Supp(E) the union of the supports in X of the homology modules H i (E) of E. By definition, the homological dimension of E, written hd (E), is the smallest integer s such that E is quasi-isomorphic

3. 3 .

 3 Denote by Mod S(g×g) the category of finite S(g × g)-modules. Let ι be the morphismS(g × g) ⊗ k g -→ C * g , v -→ (µ → v,µ ) Lemma 3.5. Let A g be the quotient of C * g by ι(S(g × g) ⊗ k g). Then the two functors A g ⊗ S(g×g) • and Ext 1 S(g×g) (E # , •) of the category Mod S(g×g) are isomorphic. Proof. For d nonnegative integer, denote by Mod S(g×g) (d) the full subcategory of Mod S(g×g) whose objects are the modules of projective dimension at most d. Prove by induction on d that the restrictions to Mod S(g×g) (d) of the functors Ext 1 S(g×g) (E # , •) and A g ⊗ S(g×g) • are isomorphic. Let M be a finite S(g × g)module. Denoting by d its projective dimension, there is a short exact sequence 0 -→ Z -→ P -→ M -→ 0 with Z a module of projective dimension d -1 if d > 0 and Z = 0 otherwise. Suppose d = 0. Then, from the short exact sequence 0

  i) Let O be an open subset of k 2 such that ax + by is in g reg for all (a, b) in O. Then V x,y is the sum of the g ax+by 's, (a, b) ∈ O. (ii) The spaces [x, V x,y ] and [y, V x,y ] are equal. (iii) The space V x,y has dimension at most b g and the equality holds if and only if (x, y) is in Ω g . (iv) The space [x, V x,y ] is orthogonal to V x,y . Furthermore, (x, y) is in Ω g if and only if

  0 are exact. Hence E and E # have projective dimension at most 1 since B g and C g are free modules by Theorem 2.2 and Proposition 2.3,(ii).

(ii)

The module E is torsion free by Theorem 2.2,(ii). By definition, for ϕ in S(g

According to Proposition 3.9, for i = n + ℓ + 2, . . . , 2n + ℓ, C i (g) has projective dimension at most n. Hence, by Corollary A.3, this complex is acyclic and Z has projective dimension at most 2n -2, whence the assertion.

(ii) and (iii) Since B g is a free module of rank b g , b g (B g ) is a free module of rank 1. By definition, the short sequence 0 -→ Z -→ g ∧ b g (B g ) -→ I g b g (B g ) -→ 0 is exact, whence the short exact sequence

Moreover, by Proposition 3.9, g ∧ b g (B g ) has projective dimension at most 1. Then, by (i), I g has projective dimension at most 2n -1. As a result the S(g × g)-module S(g × g)/I g has projective dimension at most 2n. Then by Auslander-Buchsbaum's theorem [Bou98, §3, n • 3, Théorème 1], the depth of the graded S(g × g)-module S(g × g)/I g is at least 4b g -2ℓ -2n = 2b g so that, according to [Bou98, §1, n • 3, Proposition 4], the depth of the graded algebra S(g × g)/I g is at least 2b g . In other words, S(g × g)/I g is Cohen-Macaulay since it has dimension 2b g . Moreover, since the graded algebra S(g × g)/I g has depth 2b g , the graded S(g × g)-module S(g × g)/I g has projective dimension 2n. Hence I g has projective dimension 2n -1. (iv) By (i), I g has projective dimension 2n -1. Hence, according to Proposition 3.9 and according to (ii) and Corollary A.3, n (g) ∧ b g (B g ) has projective dimension n.

Theorem 4.3. The subscheme of g × g defined by I g is Cohen-Macaulay and normal. Furthermore, I g is a prime ideal.

Proof. According to Theorem 4.2,(iii), the subscheme of g × g defined by I g is Cohen-Macaulay. According to [Po08, Theorem 1], it is smooth in codimension 1. So by Serre's normality criterion [Bou98, §1, n • 10, Théorème 4], it is normal. In particular, it is reduced and I g is radical. According to [START_REF] Richardson | Commuting varieties of semisimple Lie algebras and algebraic groups[END_REF], C(g) is irreducible. Hence I g is a prime ideal.

Appendix A. Projective dimension and cohomology

Recall in this section classical results. Let X be a Cohen-Macaulay irreducible affine algebraic variety and let S be a closed subset of codimension p of X. Let P • be a complex of finite projective k[X]-modules whose lenght l is finite and let ε be an augmentation morphism of P • whose image is R, whence an augmented complex of k[X]-modules,

Denote by P • , R, K 0 the localizations on X of P • , R, the kernel of ε respectively and denote by K i the kernel of the morphism P i -→ P i-1 for i positive integer.

Lemma A.1. Suppose that S contains the support of the homology of the augmented complex P • .

(i) For all positive integer i < p -1 and for all projective O X -module P, H i (X \ S , P) equals zero.

(ii) For all nonnegative integer j ≤ l and for all positive integer i < pj, the cohomology group H i (X \ S , K l-j ) equals zero.

Proof. (i) Let i < p -1 be a positive integer. Since the functor H i (X \ S , •) commutes with the direct sum, it suffices to prove H i (X \ S , O X ) = 0. Since S is a closed subset of X, one has the relative cohomology long exact sequence

Since X is Cohen-Macaulay, the codimension p of S in X equals the depth of its ideal of definition in k[X] [MA86, Ch. 6, Theorem 17.4]. Hence, according to [Gro67, Theorem 3.8], H i+1 S (X, O X ) and H i (X \ S , O X ) equal zero since i + 1 < p.

(ii) Let j be a nonnegative integer. Since S contains the support of the homology of the complex P • , for all nonnegative integer j, one has the short exact sequence of O X\S -modules

whence the long exact sequence of cohomology

Then, by (i), for 0 < i < p -2, the cohomology groups H i (X \ S , K j ) and H i+1 (X \ S , K j+1 ) are isomorphic since P j+1 is a projective module. Since P i = 0 for i > l, K l-1 and P l have isomorphic restrictions to X \ S . In particular, by (i), for 0 < i < p -1, H i (X \ S , K l-1 ) equal zero. Then, by induction on j, for 0 < i < pj, H i (X \ S , K l-j ) equals zero.

Proposition A.2. Let R ′ be a k[X]-module containing R. Suppose that the following conditions are verified:

(1) p is at least l + 2, (2) X is normal,

(3) S contains the support of the homology of the augmented complex P • .

(i) The complex P • is a projective resolution of R of length l.

(ii) Suppose that R ′ is torsion free and that S contains the support in X of R ′ /R. Then R ′ = R.

Proof. (i) Let j be a positive integer. One has to prove that H 0 (X, K j ) is the image of P j+1 . By Condition (3), the short sequence of O X\S -modules

Since the codimension of S in X is at least 2 and since X is irreducible and normal, the restriction morphism from P j+1 to H 0 (X \S , P j+1 ) is an isomorphism. Let ϕ be in H 0 (X, K j ). Then there exists an element to a complex of projective k[X]-modules of length s. If no such integer exists, hd (E) = ∞. Since X is Cohen-Macaulay, according to [MA86, Ch. 6, Theorem 17.4], we have the following proposition:

Proposition A.5. [BM02, Corollary 5.5] Let E be a non trivial object of D(X). Then for all irreducible component Γ of Supp(E), dim Xdim Γ ≤ hd (E).

Corollary A.3 is a little bit smilar to Proposition A.5. But it is not a consequence of Proposition A.5 since its proof does not use the normality of X.


Jean-Claude Bajard
email: jean-claude.bajard@lip6.fr

Nabil Merkiche
email: nabil.merkiche@intradef.gouv.fr

Double Level Montgomery Cox-Rower Architecture, New Bounds

Keywords: Residue Number System, High Speed, Hardware Implementation, Elliptic Curve Cryptography, FPGA

. We also slightly improve the computation time (latency) and our implementation shows best ratio throughput/area for RNS computation supporting any curve independently of the chosen base.

Introduction

The Residue Number System (RNS) has shown interest for efficient implementation and high performances in large integer computations for public key cryptography and digital signature [START_REF] Kawamura | Cox-Rower Architecture for Fast Parallel Montgomery Multiplication[END_REF][START_REF] Guillermin | A High Speed Coprocessor for Elliptic Curve Scalar Multiplications over Fp[END_REF]. Due to the ability to compute any operation quickly (O(n) complexity in RNS vs O(n log 2 (3) ) in multiprecision for multiplications when using Karatsuba) without carry propagation and with natural parallelism, RNS has gained interest in the literature [START_REF] Schinianakis | An rns implementation of an fp elliptic curve point multiplier[END_REF][START_REF] Szerwinski | Exploiting the Power of GPUs for Asymmetric Cryptography[END_REF][START_REF] Antão | Rns-based elliptic curve point multiplication for massive parallel architectures[END_REF]. Recently, it has also been demonstrated to be suitable for pairing computations [START_REF] Ray | FPGA Implementation of Pairings Using Residue Number System and Lazy Reduction[END_REF][START_REF] Yao | Faster Pairing Coprocessor Architecture[END_REF]. Improvement has been made for efficient computation of the final exponentiation in [START_REF] Bigou | Improving Modular Inversion in RNS Using the Plus-Minus Method[END_REF]. All these implementations are based on the Cox-Rower architecture proposed by Kawamura for RSA [START_REF] Kawamura | Cox-Rower Architecture for Fast Parallel Montgomery Multiplication[END_REF] and improved by Guillermin for ECC computations [START_REF] Guillermin | A High Speed Coprocessor for Elliptic Curve Scalar Multiplications over Fp[END_REF].

In this paper, we reformulate the conditions for the base extension in order to build bases for the RNS Cox-Rower. Then, we present a new ALU that takes advantages of the new conditions for the base extension.

The paper is organised as follow: in Section 2, we will recall briefly mathematical background about RNS, Montgomery over RNS and approximations made in the base extension. Section 3 deals with the range of the moduli set induced by the approximation made during the base extension. The truncation function of the Cox is re-evaluated under those conditions. Section 4 presents a new Rower architecture, together with its base extension algorithm, to take advantage of the maximal range of the moduli set defined in Section 3. Section 5 gives results with scalar multiplication as well as area and performance comparisons with the classical Rower architecture. Section 6 concludes the paper.

2 Background Review

Residue Number System

RNS represents a number using a set of smaller integers. Let B = {m 1 , . . . , m n } be a set of coprime natural integers. B is also called a base. Let M = n i=1 m i . The RNS representation of X ∈ Z/M Z is the unique set of positive integers {X} B = {x 1 , . . . , x n } with x i = X mod m i . The conversion from RNS representation to binary representation can be computed using the Chinese Remainder Theorem (other methodology as Mixed Radix is possible):

X = n i=1 (x i M -1 i mod m i )M i mod M with M i = M m i (1)
Operations in RNS are computed as follows:

∀X, Y ∈ Z/M Z, ∃Z ∈ Z/M Z s.t.: Z = X Y mod M ⇔ z i = x i y i mod m i with ∈ {+, -, * , ÷}
and ÷ only available when Y is coprime with M and a divisor of X.

Notation: In the rest of the paper, {X} B will refer to the representation of X in the RNS base B. We use braces to denote the fact that this is a set of integers.

RNS and Montgomery

RNS arithmetic has several drawbacks over multiprecision arithmetic. One of them is that reduction over p is complex. Reduction over p is still possible when using Montgomery Reduction since it computes exactly the value using a base extension [START_REF] Posch | Base extension using a convolution sum in residue number systems[END_REF][START_REF] Posch | Modulo reduction in residue number systems[END_REF]. Thereafter, we recall the algorithm to compute the Montgomery Reduction in RNS [START_REF] Kawamura | Cox-Rower Architecture for Fast Parallel Montgomery Multiplication[END_REF][START_REF] Guillermin | A High Speed Coprocessor for Elliptic Curve Scalar Multiplications over Fp[END_REF][START_REF] Posch | Modulo reduction in residue number systems[END_REF].

The main part of Montgomery Reduction relies on the Base Extension function (BE in the algorithm) that is described in the next section.

Algorithm 1: Montgomery Reduction in RNS

Input: {X} B , {X} B Output: {S} B , {S} B 1 Precomputed: {-p -1 } B , {p} B , {M -1 } B 2 {Q} B ← {X} B * {-p -1 } B 3 {Q} B ← BE({Q} B , B, B ) 4 {S} B ← ({X} B + {Q} B * {p} B ) * {M -1 } B 5 {S} B ← BE({S} B , B , B)

Base Extension

Let n be the cardinality of the base in RNS. In [START_REF] Posch | Base extension using a convolution sum in residue number systems[END_REF][START_REF] Posch | Modulo reduction in residue number systems[END_REF], Posch and Posch introduced a floating approach to compute the base extension function. In [START_REF] Kawamura | Cox-Rower Architecture for Fast Parallel Montgomery Multiplication[END_REF], Kawamura came to a similar result, but the base extension function introduced by Kawamura supposes that the moduli m i are pseudo-Mersenne numbers of the form

m i = 2 r -µ i with 0 ≤ µ i 2 r , ∀i ∈ [[1, n]].
The base extension function relies on the conversion from RNS representation to binary representation. From (1), we have:

x = n i=1 (x i M -1 i mod m i )M i -kM,
for some k to be determined. Let ξ i (x i ) = x i M -1 i mod m i but we will use ξ i to lighten notations. Then it follows:

n i=1 ξ i /m i = k + x/M Since 0 ≤ x/M < 1, we have k ≤ n i=1 ξ i /m i < k + 1. Hence: k = n i=1 ξ i /m i (2)
Thanks to the special form of m i and to the condition 0 ≤ µ i 2 r , Kawamura has approximated m i by 2 r to ease the computation. Let k be:

k = n i=1 trunc q (ξ i ) 2 r + α where trunc q (ξ i ) = ξ i 2 (r-q) 2 (r-q) and 0 ≤ α < 1 (3)
One can see that 0 ≤ ξ i -trunc q (ξ i ) ≤ 2 (r-q) -1. To evaluate the error due to the truncation approximation, Kawamura introduced some definitions that we recall here:

mi = 2 r -m i 2 r , δ mi = ξ i -trunc q (ξ i ) m i (4) = max i∈[[1,n]] ( mi ), δ = max i∈[[1,n]] (δ mi ) (5)
The denominator's approximations error is called mi whereas δ mi is due to the numerator's approximation. Then, Kawamura proved 2 theorems for the base extension function. The conditions of one of the theorems will help to find the µ i 's upper bound (called µ max ), which is the maximal range of the set from which we can select the moduli to build a base.

Theorem 1 (Kawamura [6]). If 0 ≤ n( + δ) ≤ α < 1 and 0 ≤ x < (1 -α)M , then k = k and the base extension function extends the base without error.

One can see from the proof of the Theorem 1 in [START_REF] Kawamura | Cox-Rower Architecture for Fast Parallel Montgomery Multiplication[END_REF] that the conditions can be relaxed in:

0 ≤ n( + δ(1 -)) ≤ α and 0 ≤ x < (1 -α)M with α < 1 (6)
This new condition will help us to estimate µ max 's upper bound. To our knowledge, conditions on µ max have not been clearly established. In order to ease the moduli selection, we define the conditions on µ max in the next section.

3 New Bounds for the Cox-Rower Architecture 3.1 µ i 's Upper Bound for RNS Base

In the previous section, we have presented Kawamura's approximation of the factor k for the base extension. The only condition given by Kawamura is 0 ≤ µ i 2 r . In this section, we will explore the different equations to evaluate the impact on µ i 's upper bound. From (4) and (5), we have:

= max 2 r -m i 2 r = 2 r -min(m i ) 2 r which leads to min(m i ) = 2 r (1 -)
On the other hand, ∀x ∈ Z/M Z we have:

0 ≤ δ = max ξ i -trunc q (ξ i ) m i ≤ 2 (r-q) -1 min(m i ) = 2 (r-q) -1 2 r (1 -)
From the new condition [START_REF] Kawamura | Cox-Rower Architecture for Fast Parallel Montgomery Multiplication[END_REF], it follows that:

0 ≤ n + 2 (r-q) -1 2 r (1 -) (1 -) ≤ α then 0 ≤ ≤ α n - 2 (r-q) -1 2 r (7)
Now, we will evaluate Equation [START_REF] Ma | A high-speed elliptic curve cryptographic processor for generic curves over GF[END_REF] in to find the condition on m i since = = µmax 2 r . Let substitute in [START_REF] Ma | A high-speed elliptic curve cryptographic processor for generic curves over GF[END_REF]:

0 ≤ µ max 2 r ≤ α n - 2 r-q -1 2 r ⇔ 0 ≤ µ max ≤ 2 r α n -2 r-q + 1 (8)
If q = r, then µ max is maximum and is in the range of:

0 ≤ µ max ≤ 2 r α n (9)
Then, we can rewrite an equivalent condition of the Theorem 1 using only the parameters α, r, n, q and µ max , which is more explicit for implementations: With this new formulation, we can easily build bases for the RNS Cox-Rower architecture.

Theorem 2. If 0 ≤ µ max ≤ 2 r α n -2 r-q + 1 and 0 ≤ x < (1 -α)M with α < 1, then k = k

Lower Bound for the parameter q of the Cox

In [START_REF] Kawamura | Cox-Rower Architecture for Fast Parallel Montgomery Multiplication[END_REF], Kawamura described a procedure to determine n, , δ, α and q for a given p. While n is easy to determine (same order of magnitude as n ≈ log 2 (p)/r), q is determined using the approximations 1 and 2 -(r-q) 1 with Theorem 1's conditions. While those approximations are asymptotically correct, we want to determine q for any range of parameters. We give, here, a new procedure to determine correctly q from α, n, r and µ max .

Once the bases are choosen using ( 9), from the Theorem 2's conditions, the following equation can be applied to find the parameter q:

q ≥ -log 2 α n + 2 -r - µ max 2 r with µ max = max µi∈{B,B } (µ i ) (10)
This is a necessary and sufficient condition to get an exact computation. Unlike Kawamura's method [START_REF] Kawamura | Cox-Rower Architecture for Fast Parallel Montgomery Multiplication[END_REF], no assumption is made on (or equivalently on µ max ) and 2 -(r-q) .

A New Cox-Rower Architecture

In the previous section, conditions on µ max has been determined. In this section, we first present the algorithm and the classical ALU used to compute the reduction inside the Rower. To our knowledge, it is the only ALU used with the RNS Cox-Rower architecture [START_REF] Nozaki | Implementation of RSA Algorithm Based on RNS Montgomery Multiplication[END_REF][START_REF] Guillermin | A High Speed Coprocessor for Elliptic Curve Scalar Multiplications over Fp[END_REF][START_REF] Ray | FPGA Implementation of Pairings Using Residue Number System and Lazy Reduction[END_REF][START_REF] Yao | Faster Pairing Coprocessor Architecture[END_REF][START_REF] Bigou | Improving Modular Inversion in RNS Using the Plus-Minus Method[END_REF].

Then, we introduce the new ALU proposed in this paper. This new ALU has been designed to fit on FPGAs, and we compare it with the classical ALU. Our comparison analysis uses 3 types of cells: DSP (Digital Signal Processing) blocks, LUTs (Look-Up Table ) and registers (basic elements of FPGA) to compare the 2 ALUs. Multipliers are implemented inside DSP blocks on FPGA, with some additional features such as pre/post-adder/substracter. LUTs are the cell bases to implement any combinatorial logic.

Algorithm 2: Efficient Reduction Algorithm

Input: a ≤ 2 r , b ≤ 2 r and mi = 2 r -µi with 0 ≤ µi < √ 2 r Output: z = (ab) mod mi 1 c ← ab = c12 r + c0 2 d ← c1µi = d12 r + d0 3 e ← d1µi 4 z ← (e + d0 + c0) mod mi

Classical Rower Unit

The Cox-Rower architecture defined in [START_REF] Kawamura | Cox-Rower Architecture for Fast Parallel Montgomery Multiplication[END_REF][START_REF] Nozaki | Implementation of RSA Algorithm Based on RNS Montgomery Multiplication[END_REF][START_REF] Guillermin | A High Speed Coprocessor for Elliptic Curve Scalar Multiplications over Fp[END_REF][START_REF] Ray | FPGA Implementation of Pairings Using Residue Number System and Lazy Reduction[END_REF][START_REF] Yao | Faster Pairing Coprocessor Architecture[END_REF] computes the reduction inside the Rower using Algorithm 2 when 0

≤ µ i < √ 2 r .
The last addition (line 4 of Algorithm 2) gives a number up to 3•2 r < 4m i . It is also possible to reduce the last addition during the computation of the multiplications, if the adder/reducer block are not the critical path of the design compared to the multipliers. Such implementation gives good results for efficient implementation and computation for F p /RSA and ECC [START_REF] Kawamura | Cox-Rower Architecture for Fast Parallel Montgomery Multiplication[END_REF][START_REF] Nozaki | Implementation of RSA Algorithm Based on RNS Montgomery Multiplication[END_REF][START_REF] Guillermin | A High Speed Coprocessor for Elliptic Curve Scalar Multiplications over Fp[END_REF][START_REF] Ray | FPGA Implementation of Pairings Using Residue Number System and Lazy Reduction[END_REF][START_REF] Yao | Faster Pairing Coprocessor Architecture[END_REF][START_REF] Bigou | Improving Modular Inversion in RNS Using the Plus-Minus Method[END_REF]. Figure 1 presents the ALU of the Rower unit introduced by Guillermin [START_REF] Guillermin | A High Speed Coprocessor for Elliptic Curve Scalar Multiplications over Fp[END_REF]. The first reduction stage (second level in Fig. 1) is not necessary because its output is reduced within the second stage (third level in Fig. 1) (in the design, we have 2 r +m i < 3m i but 2 r + 2 r < 3m i ). The last part of the design is two accumulators before adding and reducing the 2 branches.

New Rower Unit

A drawback of the previous ALU is the condition 0 ≤ µ i ≤ √ 2 r . This restriction on moduli is taken to allow efficient reduction. Notice that, on the contrary, the condition we derived in [START_REF] Posch | Base extension using a convolution sum in residue number systems[END_REF] has to be met to ensure a base extension without error.

Then the two following cases can be met:

(i) 0 ≤ µ max ≤ 2 r α n < √ 2 r . In that case, choosing moduli in the range [2 r α n ; √ 2 r ] may lead to erroneous computations. (ii) 0 ≤ µ max ≤ √ 2 r < 2 r α n .
In this second case we observe that, using the classical ALU, we are restricted for the choice of moduli while our conditions [START_REF] Posch | Base extension using a convolution sum in residue number systems[END_REF] shows that taking more moduli without inducing errors is possible.

As an example, when r ≥ 14 and log 2 (p) = 521, we are restricted by the condition 0 ≤ µ max ≤ √ 2 r to select the moduli. The condition given for efficient reduction, when r is large, is sufficient to be in (ii), which is the case in [START_REF] Kawamura | Cox-Rower Architecture for Fast Parallel Montgomery Multiplication[END_REF][START_REF] Nozaki | Implementation of RSA Algorithm Based on RNS Montgomery Multiplication[END_REF][START_REF] Guillermin | A High Speed Coprocessor for Elliptic Curve Scalar Multiplications over Fp[END_REF][START_REF] Ray | FPGA Implementation of Pairings Using Residue Number System and Lazy Reduction[END_REF][START_REF] Yao | Faster Pairing Coprocessor Architecture[END_REF][START_REF] Bigou | Improving Modular Inversion in RNS Using the Plus-Minus Method[END_REF].

We propose here a new ALU for the Rower unit to exploit the upper bound µ max ≤ 2 r α n given by our condition [START_REF] Posch | Base extension using a convolution sum in residue number systems[END_REF]. Using this upper bound, we will be able to use smaller radix than the classical ALU for computing equivalent size of p (r = 16 for computing log 2 (p) = 521 whereas we need r = 18 with the classical ALU). Our ALU is based on the Montgomery reduction3 inside the Rower unit (called inner level of Montgomery). Our ALU computes the reduction using Algorithm 3 without any assumption on m i excepted the one that m i is coprime with 2 r to ease the computation in hardware 4 .

Algorithm 3: Inner Montgomery Reduction algorithm

Input: a ≤ 2 r , b ≤ mi, mi = 2 r -µi with gcd(mi, 2 r ) = 1, mi < 2 r Output: z = (ab2 -r ) mod mi 1 c ← ab = c12 r + c0 2 q ← (c0(-m -1 i )) mod 2 r = q0 3 s ← (q0mi) + c = s12 r + s0 4 z ← s1 mod mi
The most significant bits of the last addition (line 3 of Algorithm 3) gives a number up to 2m i (compared to 4m i with the classical ALU). Figure 2 presents the ALU of the Rower unit proposed in this paper.

Levels of multiplication and reduction are also well separated, which makes our design fully pipelinable inside DSP blocks of the FPGA. Our ALU has also one accumulator. Moreover, we can take advantage of the adder integrated in the DSP blocks to compute the last addition of the Montgomery reduction algorithm (Algorithm 3).

Computation Algorithm

The computation of the Montgomery reduction over RNS (called outer level of Montgomery), when using the classical ALU, is given in [START_REF] Guillermin | A High Speed Coprocessor for Elliptic Curve Scalar Multiplications over Fp[END_REF]. We recall this algorithm in the Appendix. It is based on precomputation of values depending on the parameters of the elliptic curve (a4, a6, p with y 2 = x 3 + a 4 x + a 6 ) and on the values of the bases

(m i , M i , M -1 i , M, M -1 , m i , M i , M -1
i , M ). Our ALU uses the same algorithm as the one given in [START_REF] Guillermin | A High Speed Coprocessor for Elliptic Curve Scalar Multiplications over Fp[END_REF]. Differences reside in the precomputed values. Indeed, values that have to be computed are {X2 r } B = { xi = x i 2 r mod m i }5 . Mainly, we precompute the values using Montgomery representation inside the ALU (which is ×2 r mod m i in the inner level of Montgomery). When we use the base extension function, we need to compute the real value (inner level of Montgomery representation to normal representation mod m i ) to extend it to the second base. The new ALU needs the same number of cycles in order to compute the outer Montgomery compared to the classical ALU (Algorithms for outer Montgomery computation, as well as precomputed values, for the classical ALU and our ALU are given in Appendix A).

Comparison Analysis

Despite the fact that our ALU was designed specifically to fit on FPGA, we give some comparisons for ASIC implementations.

Area analysis. Size of the multipliers are not the same between the classical ALU and our ALU. When using the classical ALU, we need 3 multipliers of size r × r → 2r, r × r/2 → 3r/2 and r/2 × r/2 → r (line 1, 2 and 3 of Algorithm 2). Our ALU costs the same number of multipliers, but the size will be r × r → 2r, r × r → r and r × r → 2r. With our ALU, we fully used the full size of the DSP blocks on FPGA whereas quarter and half of the DSP blocks are lost with the classical ALU. When looking at LUTs used on FPGA, our ALU is less complex (in term of additions and reductions) than the classical ALU. This reduces the number of LUTs used within our ALU. The final adder in Montgomery reduction algorithm (Algorithm 3) can also be included inside the DSP blocks of the FPGA to help reducing the number of LUTs used, which is not the case with the classical ALU. Looking at Fig. 2, we can estimate that we would use 5 times less LUTs with our ALU than with the classical one. For ASIC, those considerations are no more true since the cost of the reduction level is far more important on FPGA than in ASIC (where multipliers are far more area consuming than adders). Timing analysis. Timing path of a classical multiplier is an affine function on the size of its inputs. In the classical ALU, for each multiplications, we need the most significant bits of the previous multiplication (line 2 and 3 of Algorithm 2). In ASIC or FPGA, this is usually the critical path of the design if it is not well pipelined. On the other hand, our ALU only needs the least significant bits from one multiplier to the next (line 2 and 3 of Algorithm 3), which reduces the length of the critical timing path.

Others considerations. Stages of multiplications and reductions are well separated, which reduces the fanouts, placement and routing issues. Stages of multiplication are also fully pipelinable without any impact on the final reduction in our ALU.

Remarks. With the classical ALU, Kawamura's approximation on

1 and 2 -(r-q) 1 to determine q is correct when r is large enough to have √ 2 r 2 r α n . With the new ALU, the procedure to determine q, defined in the previous section, is available.

Experiments and Comparison

Validation on FPGA

Target technology. We have implemented our ALU (and also the classical ALU [START_REF] Guillermin | A High Speed Coprocessor for Elliptic Curve Scalar Multiplications over Fp[END_REF] for the purpose of comparison) on a Xilinx Kintex-7 FPGA using the KC705 evaluation board available from Xilinx. This board includes the device xc7k325t which is a mid range FPGA on the 28nm process node.

Parameters design. We have implemented the classical cryptography security level from NIST but no restriction is given on the parameters of the elliptic curve but to be a valid curve. DSP blocks of the Xilinx 7 series family are signed multipliers of size 25 × 18 → 43. Since we need only the unsigned part of the multiplier, and we want to be base-independent, we choose to take radix r = 17. The base has been chosen such that we can take α = 0.5.

Implementation. For both design (classical ALU and our ALU) and each curve, Table 1 gives the area in terms of slices 6 , maximum frequency after Place and Route, number of cycles for a whole computation (binary to RNS or INT2RNS, scalar multiplication or MULT, final inversion or INV, and RNS to binary transformation or RNS2INT), the computation time, q (size of the adder in the Cox module), log 2 (µ max ) and the ratio bits.s -1 /slices. The slice count is independent on DSP slices or BRAM (Block RAM). Table 2, in Appendix A, gives the details account on LUTs, registers, DSP and BRAM, as well as the cycles for each command. Area implementation results take the datapath, the sequencer and the interface into accounts. Only the ALU has been modified as well as the precomputations.

Design

Curve n Cycles Slices Fmax Latency q log 2 (µmax) Ratio Classical ALU (C) 160 Comparison of the 2 ALUs. Because of the condition given for an efficient reduction (0 ≤ µ i ≤ √ 2 r = 362) with the classical ALU, we were not able to build 2 bases with r = 17 for log 2 (p) > 256 which is a critical size for the DSP block for the Xilinx FPGA. On the other hand, using our ALU and the condition (9) (0 ≤ µ max ≤ 2 r α n = 2114), we were able to build 2 bases up to log 2 (p) = 521. To reach similar size of p, Guillermin took r = 18 with the classical ALU to overcome this issue [START_REF] Guillermin | A High Speed Coprocessor for Elliptic Curve Scalar Multiplications over Fp[END_REF], which it's not acceptable if we want to use 1 DSP block per multiplication and don't want to penalize the maximal frequency and latency. As expected in the previous section, we use 35% less area, globally, with the Montgomery ALU than with the classical ALU. The area reduction given here takes into account the logic for the whole datapath, the sequencer and the interface. The area reduction inside the ALU is around 75%. The area of the 256 bits with the classical ALU is almost the same as with the 521 bits for our ALU. The gap on the maximal frequency between the 2 ALUs is due to the placement and routing issues. Indeed, critical timing paths of the classical ALU are from multipliers to adder/reducers blocks (Fig. 1). The multiple interconnections make those paths really difficult to place and route efficiently (essentially due to the fanouts). On the other hand, critical timing paths of our ALU is from one multiplier to the next multiplier. Thus, if we want to increase the frequency, we will have to increase the pipeline. For scalar multiplication in ECC, a pipeline of 5 registers is enough to have 95% of the pipeline used during the whole computation (Guillermin came to similar results [START_REF] Guillermin | A High Speed Coprocessor for Elliptic Curve Scalar Multiplications over Fp[END_REF]). For application to pairing computations, we can increased the pipeline to 10 registers thus expecting better frequency than for scalar multiplication [START_REF] Ray | FPGA Implementation of Pairings Using Residue Number System and Lazy Reduction[END_REF][START_REF] Yao | Faster Pairing Coprocessor Architecture[END_REF].

Comparison

We compare our design with 3 others design RNS and non RNS. Our architecture supports any elliptic curve over F p and implements the Montgomery Ladder algorithm to be SPA resistant. We used projective coordinates for computations. We considered the general elliptic curve in the Weierstrass form y 2 = x 3 +a 4 x+a 6 with no assumption on the parameters. Our architecture does not make assumption on the form of the moduli except that they respect Theorem 2's conditions.

(i) First design is the one given in [START_REF] Guillermin | A High Speed Coprocessor for Elliptic Curve Scalar Multiplications over Fp[END_REF] and is based on RNS. The ALU used is the classical one. A larger size of radix has also been used in his implementation. This design shows really fast computation with any elliptic curve over F p . To our knowledge, it is the fastest implementation of elliptic curve scalar multiplication with generic curves independently of the choosen base on FPGA using RNS Cox-Rower architecture. For ratio comparison, a slice in recent Xilinx devices (virtex-5 and beyond) is equivalent to 3 ALMs7 in Altera. To achieve high running frequency, all the precomputed values and the GPR are implemented into registers inside ALMs. (ii) Second design is an implementation of a specific curve where p is a pseudo-Mersenne number [START_REF] Güneysu | Ultra High Performance ECC over NIST Primes on Commercial FPGAs[END_REF]. Using the property of the pseudo-Mersenne value, this implementation can be specialized to run at high frequency and quickly computing the multiplication scalar. (iii) Third design is based on fast quotient pipelining Montgomery multiplication algorithm in [START_REF] Ma | A high-speed elliptic curve cryptographic processor for generic curves over GF[END_REF]. The scalar multiplication algorithm is based on window method algorithm. Jacobian coordinates is used and a 4 parameter is set to -3 (which is not a real restriction with Weierstrass form through an isogeny). Design (i) is the one we compare during the paper. Our implementation is smaller and a slightly faster than the implementation in [START_REF] Guillermin | A High Speed Coprocessor for Elliptic Curve Scalar Multiplications over Fp[END_REF].

Design (ii) used the specific form of the parameter p to improve the overall performance. This design is faster than ours, but it is dependent on the pseudo-Mersenne form of the parameter p of the elliptic curve.

Design (iii) shows really fast computation of ECC scalar multiplication. Compared to our design, the gain in computation time comes from the use of Jacobian coordinates and the window method algorithm whereas we use Montgomery Ladder and projective coordinates. But when comparing the numbers of cycles to complete a multiplication and an addition/substraction, 35 cycles is needed to compute a multiplication whereas we need 2n + 3 cycles (35 cycles for 256 bits), and 7 cycles is needed to compute an addition/substraction, whereas we need 1 cycle for an addition/substraction. Eventually, the gain in performance is not scalable to any size of elliptic curve as our work.

Conclusion and perspectives

In this paper, we established the link between moduli's properties and base extension for the Cox-Rower architecture. To our knowledge, that was not clearly defined yet. Now, the given bounds are more appropriate for designers. We also give a new procedure to determine q parameter which is used for truncation in the Cox module. We propose a new ALU design, based on an inner Montgomery reduction. This ALU is designed to fully use the bounds of the Cox-Rower architecture and to reduce the combinatorial area of the architecture on FPGA without penalizing performance. Moreover, using the same pipeline depth, we manage to increase the frequency of our ALU compare to the classical one.

In future works, we will increase the pipeline depth in DSP blocks for applications to pairing computations in order to improve computation time. Furthermore, we will take advantage of the pre-substracter of the DSP block to easily compute (-AB) mod p and reduce computation time. In the perspective of improving the algorithmic, we will study the use of different coordinates and implementations, such as Jacobian coordinates and window method. Although our ALU is designed for FPGA, we will also study the potential application of our ALU to ASIC.

2 r

 2 -min(mi) 2 r

  and the base extension function extends the base without error.

Fig. 1 .

 1 Fig. 1. Classical ALU's Rower

Fig. 2 .

 2 Fig. 2. New ALU's Rower

Algorithm 4 : 9 for j = 1 to n do 10 q 1 i 1 iAlgorithm 5 : 1 i mod mi 3 q i ← 0 4 si ← 0 5 end 6 k 8 k 9 for j = 1 to n do 10 q 1 j 2 r 1 i 2 r 1 i

 49101151346891012121 Montgomery Reduction over RNS with classical ALU Input: {X} B = {xi} and {X} B = {x i} Output: {S = (XM -1 mod p) mod M } B = {si} and {S= (XM -1 mod p) mod M } B = {s i} 1 for i = 1 to n do 2 qi ← xi(-p -1 )M -1 k ← 0 // Initialization of the cox with α = 0 7 for i = 1 to n do 8 k ← k + truncq(qi) // Evaluating the factor k j ← (q j + qiM i pM -1 M i = 1 to n do 14 q i ← (q i + k 2 r (-M)pM -1 M -) mod m i 15 end 16 for i = 1 to n do 17 s i ← (q i + x i M -1 M -) mod m i 18 end 19 k ← errinit // Initialization of the cox with α = errinit 20 for i = 1 to n do 21 k ← k + truncq(s i ) // Evaluating the factor k 22 for j = 1 to n do 23 sj ← (sj + s i M i ) mod mj 24 end 25 end 26 for i = 1 to n do 27 si ← (si + k 2 r (-M )) mod mi 28 s i ← (s i M i ) mod m i29 end Montgomery Reduction over RNS with Montgomery ALUInput: { X} B = { xi = xi2 r mod mi} and { X} B = { x i = x i2 r mod m i } Output: { S = (XM -1 mod p)2 r mod M } B = { si = si2 r mod mi} and { S = (XM -1 mod p)2 r mod M } B = { s i = s i2 r mod m i } 1 for i = 1 to n do 2 qi ← xi ⊗ (-p -1 )M -← 0 // Initialization of the cox with α = 0 7 for i = 1 to n do ← k + truncq(qi) // Evaluating the factor k j ← (q j + qi ⊗ M i pM -1 M -) mod m j 11 end 12 end 13 for i = 1 to n do 14 q i ← (q i + k 2 r ⊗ (-M)pM -1 M -) mod m i 15 end 16 for i = 1 to n do 17 s i ← (q i + x i ⊗ M -1 M -) mod m i 18 end 19 k ← errinit //Initialization of the cox with α = errinit 20 for i = 1 to n do 21 k ← k + truncq(s i ) // Evaluating the factor k 22 for j = 1 to n do 23 sj ← (sj + s i ⊗ M i 2 2r ) mod mj 24 end 25 end 26 for i = 1 to n do 27 si ← (si +

Table 1 .

 1 P&R performances and comparisons

	Our ALU (O)	10 78892	1614 233,8 0,337 ms 5 1011 285,7 0,276 ms 5	7 7	293,7 573,1
	C O	192 12 106205	1880 231,3 0,459 ms 5 1190 283,0 0,375 ms 5	7 7	222,4 429,8
	C O	224 14 137360	2249 232,5 0,590 ms 5 1358 285,0 0,481 ms 5	8 8	168,6 342,2
	C O	256 16 172520	2540 224,2 0,769 ms 5 1630 281,5 0,612 ms 5	8 8	130,9 256,2
	O	384 23 339463 2163 281,0 1,208 ms 6	9	146,9
	O	521 31 585926 2565 265,9 2,203 ms 7	10	92,2

  To our knowledge, it is the fastest implementation of scalar multiplication over ECC and smallest design for such performance with generic curves.

	Design	Curve Device	Size (DSP)	Frequency Latency Ratio
	Our work	256 any Kintex-7 521 any	1630 slices (46) 2565 slices (91)	281,5 0,612 ms 256,2 265,9 2,203 ms 92,2
	[5]	256 any Stratix-2 512 any	9177 ALM (96) 17017 ALM (244) 144,97 2,23 ms 40,47 157,2 0,68 ms 123,1
	[4]	256 NIST Virtex-4 1715 slices (32)	490	0,49 ms 304,6
	[7]	256 any	Virtex-4 4655 slices (37) Virtex-5 1725 slices (37)	250 291	0,44 ms 250,0 0,38 ms 390,5

Table 2 .

 2 k 2 r ⊗ (-M )2 2r ) mod mi 28 s i ← (s i ⊗ M i 2 2r ) mod m i Performances details

	29 end
	Design Curve LUTs Regs DSP BRAM INT2RNS MULT INV RNS2INT
		160 4864 2959 28	10	228	66406 11598	682
	Classical	192 5691 3497 34 224 6688 4028 40	12 14	262 300	89659 15446 116227 19805 1058 862
		256 7482 4605 46	16	336	146144 24804 1270
		160 2988 2023 28	10	228	66406 11598	682
		192 3446 2346 34	12	262	89659 15446	862
	Ours	224 3847 2696 40 256 4250 3532 46	14 16	300 336	116227 19805 1058 146144 24804 1270
		384 5517 4962 67	23	462	289101 47810 2090
		521 7067 5882 91	31	606	500577 81437 3306

Barrett reduction is also possible, but we would need larger multipliers for the same results.

For mi = 2 r (only one even number can be selected), we use a classical multiplier and gather the r least significant bits of the multiplier

It is well known that the Montgomery representation is stable for addition and product using Algorithm 3

The slices is the cells counting system on Xilinx FPGA. A slice on a Kintex-7 includes 4 LUTs with 6 inputs and 8 registers.

An ALM, in the Stratix-2 family, contains 2 LUTs with 5 inputs and 2 registers, and equivalent to the Xilinx Virtex-4 slice.

A Algorithm to compute the Montgomery reduction over RNS and Implementation details

Let B and B be 2 RNS bases such that B = {m i } and

Algorithm 4 recalls the Montgomery reduction over RNS, when using the classical ALU. Precomputed values are in bald.

Algorithm 5 is the algorithm for the Montgomery reduction over RNS, when using our ALU. Operation ⊗ will denote the inner Montgomery multiplication and reduction (Algorithm 3) such that a ⊗ b mod m = ab2 -r mod m.


Jean-Claude Bajard

Laurent-Stéphane Didier

Thibault Hilaire

ρ-Direct Form Transposed and Residue Number Systems for Filter implementations (Invited Paper)

, is an numerically efficient structure for FIR or IIR filters. Compared to classical direct forms it uses more computations but less bits are necessary for the same precision. These properties made it well conditioned for fixed point arithmetic and its implementations are economical and numerically efficient comparing to other forms. In other hand, Residue Number Systems (RNS) offer an interesting parallelism where operations are made on small values. RNS are well known for improving the performances of DSP filters. We compare our RNS approach to fixed point implementations of DFII and ρ-DFIIt.

I. INTRODUCTION

The use of residue number systems (RNS) [START_REF] Szabó | Residue arithmetic and its applications to computer technology[END_REF] in digital signal processing has widely been studied [START_REF] Soderstrand | Residue number system arithmetic: modern applications in digital signal processing[END_REF]. The carry free and parallelism properties of this number system make it adapted to digital signal processing applications, where most of computations are additions and multiplications. Thus, many finite impulse response filter designs (FIR) using RNS have been proposed [START_REF] Del Re | Implementation of digital filters in carry-save residue number system[END_REF], [START_REF] Cardarilli | Impact of rns coding overhead on fir filters performance[END_REF].

However, infinite impulse response (IIR) filters are more representative of classical signal processing and are widely used in control applications. They are generally smaller but require to scale intermediate values during the processing. Equivalent forms of IIR filter having different precision requirements can be designed [START_REF] Li | A polynomial-operator-based dfiit structure for iir filters[END_REF], [START_REF] Hilaire | Sensitivity-based pole and input-output errors of linear filters as indicators of the implementation deterioration in fixedpoint context[END_REF].

In this paper a comparison of two forms of recursive filter and their implementation using fixed point arithmetic and residue number system is presented. We describe in section II the two forms chosen for this comparison. The residue numbers system and details on the scaling operation are developed in section III. The implementation of an example is detailed in section IV. II. ρ DIRECT FORM II TRANSPOSED An IIR filter is defined by its transfer function

h : z → b 0 + b 1 z -1 + . . . + b n-1 z -n+1 + b n z -n 1 + a 1 z -1 + . . . + a n-1 z -n+1 + a n z -n (1)
that describes its signal processing characteristics (specially the argument and the magnitude of h e jω with ω ∈ [0, 2π]) and the input-output relationship, since

Y(z) = h(z)U(z),
where Y and U are the Z-transform of the output y(k) and input u(k), respectively. The z -1 operator describes the timeshift operator (delay).

Transposed in time-domain, the output of such a filter is computed from the input by the following equation (called Direct Form I (DFI)) :

y(k) = n i=0 b i u(k -i) - n i=1 a i y(k -i) (2)
But some other algorithms (or realizations) can also be used.

State-space filters and their cascade and parallel decompositions are often used.

It is very interesting to notice that the Finite Word-Length (FWL) effects are strongly dependent on the realization chosen. Some criteria have been developed to evaluate the roundoff noise power [START_REF] Mullis | Synthesis of minimum roundoff noise fixed point digital filters[END_REF] and how much the transfer function and the pole are modified by the quantization of the coefficients [START_REF] Gevers | Parametrizations in Control, Estimation and Filtering Probems[END_REF], [START_REF] Hilaire | Sensitivity-based pole and input-output errors of linear filters as indicators of the implementation deterioration in fixedpoint context[END_REF]. The optimal realization problem consists then in finding the realization that minimize these FWL effects. Li and Hao [START_REF] Li | On the generalized DFIIt structure and its statespace realization in digital filter implementation[END_REF], [START_REF] Hao | An efficient structure for finite precision implementation of digital systems[END_REF], [START_REF] Li | A polynomial-operator-based dfiit structure for iir filters[END_REF] have presented a new sparse structure called rho-Direct Form II transposed (ρDFIIt). This is a generalization of the transposed direct-form II structure where the conventional time-shift operation (x(k) → x(k+1)) is changed in new operators ρ. It is a sparse realization (with 3n + 1 parameters when n is the order of the controller), leading so to an economic (few computations) implementation that could be very numerically efficient. As we will see later, this realization has n extra degrees of freedom that can be used to find an optimal realization.

Let us define

ρ i : z → z -γ i ∆ i , and
̺ i : z → i j=1 ρ j (z), 1 ≤ i ≤ n (3)
where (γ i ) 1≤i≤n and (∆ i > 0) 1≤i≤n are two sets of constants. The idea behind the ρDFIIt is to reparametrized the transfer function with (α i ) 1≤i≤n and (β i ) 0≤i≤n as follows:

h(z) = β 0 + β 1 ̺ -1 1 (z) + . . . + β n-1 ̺ -1 n-1 (z) + β n ̺ -1 n (z) 1 + α 1 ̺ -1 1 (z) + . . . + α n-1 ̺ -1 n-1 (z) + α n ̺ -1 n (z) (4
) and to use a classical transposed Direct Form II (see Figure 1), where each operator ρ -1 i is implemented as shown in Figure 2 (the ̺ -1 i are obtained by cascading the ρ -1 i ). The (α i ) and (β i ) can be directly computed from the (a i ), (b i ), (γ i ) and (∆ i ) (see [START_REF] Li | On the generalized DFIIt structure and its statespace realization in digital filter implementation[END_REF] for details).

The (γ i ) 1≤i≤n and (∆ i ) 1≤i≤n are parameters that can be freely chosen. They are used to minimize the L 2 transfer

+ + + + + βn βi βn-1 β1 β0 ρ -1 n ρ -1 i+1 ρ -1 i ρ -1 1 -α1 -αi -αn-1 -αn y(k) u(k) w1(k) wi(k) wn(k) Fig. 1. Generalized ρ Direct Form II + ∆i z -1 γi ρ -1 i x(k) z(k + 1)
Fig. 2. Realization of operator ρ -1 i function sensitivity and the roundoff noise gain [START_REF] Li | On the generalized DFIIt structure and its statespace realization in digital filter implementation[END_REF], [START_REF] Hilaire | Sensitivity-based pole and input-output errors of linear filters as indicators of the implementation deterioration in fixedpoint context[END_REF] and greatly improve the overall numerical robustness.

III. RESIDUE NUMBER SYSTEM IMPLEMENTATION

A. Introduction to RNS

A Residue Number System is defined by a base of co-prime numbers {m 1 , ..., m n }, and allows to represent integers lower

than M = n i=1 m i with their residues modulo m i . Thus, A < M is represented by (a 1 , ..., a n ) with, a i = |A| mi = A mod m i .
In these systems, operations like additions or multiplications are modular operations independently performed on each modulus (also called channel), and the result is given modulo M . Thus, calculus are distributed on small values and computed in parallel. Summation of products, as in DSP filters, are welcome for this numeration system.

However, the magnitude and the parity of a RNS number can not be obtained easily. As a consequence, general division and scaling remain costly operations compared to additions and multiplications: a conversion, or a partial conversion into a radix system is generally necessary. The conversion from RNS to binary uses the Chinese Remainder Theorem reconstruction (close to Lagrange interpolation), or the Mixed Radix System (MRS) which looks like Newton interpolation. We depict here the MRS version used in this paper. In this algorithm, the digits ζ i of a mixed radix number A M RS are computed from the residues a i of a RNS number A and where the modular inverse of

m i modulo m j is noted m -1 i mod m j . 8 > > > > > > > > > > > > > < > > > > > > > > > > > > > : ζ 1 = a 1 ζ 2 = (a 2 -ζ 1 ) m -1 1 mod m 2 ζ 3 = " (a 3 -ζ 1 ) m -1 1 -ζ 2 " m -1 2 mod m 3 . . . ζn = " . . . " (an -ζ 1 ) m -1 1 -ζ 2 " m -1 2 -• • • -ζ n-1 " m -1 n-1 mod mn. (5)
We just have to evaluate A in the wished radix system with the Horner's scheme :

A = (. . . ((ζn mn-1 + ζn-1) mn-2 + • • • + ζ3) m2 + ζ2) m1 + ζ1. (6)

B. Scaling and fixed-point representation in RNS

In this paper, we deal with DSP filter based on fixed point notation (Algorithms 2 and 1), using RNS arithmetic. The computations are performed using integer with scaling function for maintaining the fixed position of the dot. Additions and multiplications are directly performed in RNS. The impact of the scaling in RNS can be soften by choosing an RNS base simplifying this operation. Thus, we consider bases (where elements are co-prime) of the form: B := (2 k ± c i , i = 1..n) [START_REF] Bajard | Efficient rns bases for cryptography[END_REF] and an auxiliary element m 0 = 2 k . We assume that the precision required for the accumulation register is lower than M = n i=1 m i . The c i are selected such that the mixed radix conversion is done only with few shift and add operations.

Scaling: Let consider the RNS number X = (x 1 , • • • , x n ) and the integer scaling factor T = 2 t . We want to compute

Y = ⌊ X T ⌋, which is equivalent to : Y = X-|X| T T
As the exact division by an integer T is performed RNS by multiplying by its modular inverse |T | -1 M , we compute:

|Y | M = (X -|X| T ) × |T | -1 M M (7)
The value of |X| T is obtained, for each channel of the residue system, directly from the auxiliary residue modulo m 0 for t < k. Hence, if T < m i and t < k, we have:

|X| T = |X| m0 T = |X| T mi (8)
However, as computing equation ( 7) is not possible for m 0 , the modular inverse of 2 t modulo 2 k does not exist. Thus, the construction of |Y | m0 requires a partial conversion using the MRS scheme.

Finally, the scaling operation A >> t for t ≤ k, is performed as follow :

1) r ← a 0 mod 2 t 2)

for i = 1 to n do a i ← (a i -r) × (2 -t mod m i ) 3) MR conversion (ζ 1 , ζ 2 , ..., ζ n ) ← (a 1 , a 2 , ..., a n ) 4) a 0 ← ((ζ n m n-1 + ... + ζ 3 ) m 2 + ζ 2 ) m 1 + ζ 1 mod 2 k

IV. EXAMPLE

We are considering a 6 th -order Butterworth filter, which transfer function is given by the matlab command butter(6,0.125) (see eq. 9).

We also consider two different realizations, the Direct Form I, that directly uses the transfer function coefficients and the ρDFIIt, presented in section II, which parameters (γ i ) and (∆ i ) have been optimized to minimize the Finite Wordlength effects [START_REF] Hilaire | Sensitivity-based pole and input-output errors of linear filters as indicators of the implementation deterioration in fixedpoint context[END_REF].

In order to be implemented, the coefficients should be replaced by their fixed-point approximations. The figure 3 exhibits the difference between the transfer function h and its fixed-point version h † in function of the coefficients' wordlength. It is interesting to notice that the ρDFIIt form requires at least 5 bit-coefficients to approximate the ideal number of bits

A. Implementation

In order to simplify both modular operations on each channel and the conversion, the residue base {m 0 = 2 k , m 1 = 2 k -1, m 2 = 2 k + 1} is used here. Thus for the reconstruction after the scaling using the MRS scheme is :

x 0 = x 2 + (x 1 -x 2 ) × 2 k-1 2 k -1 × (2 k + 1) 2 k (10)
Let note X 2 = (x 1x 2 ), and split the binary representation of this value in to sets X 2,0 and X 2,1 so that :

X 2 = 2 × X 2,1 + X 2,0
Equation ( 10) can be rewritten as follow :

x 0 = x 2 + X 2,0 × 2 k-1 + X 2,1 2 k (11)
The two structures have both been implemented on FPGA, using fixed-point arithmetic and RNS. The designs have been described in VHDL, targeting the Xilinx Virtex4 FPGA familly. The designs have been synthetized, placed and routed using the Xilinx ISE design suite. For the RNS implementations, we used the modular adders described in [START_REF] Beuchat | Some modular adders and multipliers for field programmable gate arrays[END_REF].

Direct Form I

This realization is given by the fixed-point algorithm 2, with 18-bit coefficients, 18-bit variables and 36-bit additions. The constant multiplications are performed by shifts and additions [START_REF] Lefèvre | Multiplication by an integer constant: Lower bounds on the code length[END_REF], [START_REF] Voronenko | Multiplierless multiple constant multiplication[END_REF]. The same multiplication scheme is used in fixed point and RNS implementations. RNS version uses the base {4096, 4095, 4097}, with k = 12.

ρDirect Form II transposed This realization for fixed point requires only 5-bit coefficients, 10-bit variables and 15-bit additions. The fixed-point algorithm is given by algorithm 1. The RNS version uses the base {32, 31, 33}, with k = 5. Because the size of the moduli is small, we implemented the multiplications with lookuptables.

B. Results

The delay and area of the implemented designs are summarized in table I. Firstly, it appears that despite more additions and multiplications, both the RNS and fixed point ρDFIIt outperform the DFI realization with the same arithmetic. This gain is due to the small size of the operands in the ρDFIIt algorithm. This small size allows to choose a small RNS base and thus to tabulate the constant multipliers, reducing the size of the RNS implementation by 13%.

Secondly, the RNS designs appear to be larger and slower than fixed point designs. We observe that the FPGA technology gives little benefit to RNS operators. Indeed, in this technology, the fastest and smallest adders are ripple carry adders. More preciselly, Xilinx architecture provides a fast carry propagation mechanism which makes this kind of adder efficient.

As a consequence, splitting adders into three smaller adders working in parallel gives no reduction on the overall size, making RNS adders larger than binary adders. Furthermore, the carry propagation logic is so fast, that the size of the input size has a reduced impact on the delay. For instance, the delay of a 5-bit adder is 6.6ns while it is 7.1ns for a 15-bit adder. Thus, the gain expected on the delay by reducing the operand size with RNS arithemtic is quite null.

Finally, the scaling operation in RNS has a cost similar to a RNS addition. However, it has an important impact on the size and the delay of the RNS designs.

C. Remark

It is also possible to consider the following four elements base [START_REF] Didier | A generalization of a fast rns conversion for a new 4-modulus base[END_REF]:

B := (2 k -1, 2 k +1, 2 k -2 k-r -1, 2 k -2 k-r +1
) and m 0 = 2 k (12) For example, when k = 5 and r = 2, we obtain B := (31, 33, 23, 25), with M = 588225 > 2 19 and m 0 = 2 5 . The inverses of the moduli relatively the others and the inverses of some power of two allow multiplications reduced to at most two additions (Table II). Note that 1..1 = 10..0(-1). This RNS base seems to be suitable for the Algorithm 2.

Then, for k = 3, we can consider the RNS base B = (5, 9, 7, 11) with M = 3465 > 2 11 and m 0 = 2 3 . Here clearly look-up tables are welcome. With this kind of implementation we can expect an interesting gain, both in terms of time and area. This approach will be developed in detail in further works.

V. DISCUSSION

The ρDirect Form II transposed which gives smaller and faster filter designs in fixed point arithmetic, is also very interesting in RNS. Our first experimentations with non optimized operators, give some hopeful results concerning the delay (Tab. I). About the area some improvements are expected, such as an implementation with four moduli that should be more appropriate.

If we consider the RNS implementation of FIR [START_REF] Cardarilli | Impact of rns coding overhead on fir filters performance[END_REF], we note that the use of very small moduli seems to be a good strategy. We observe that FIR does not need scaling operations as for IIR. In RNS the impact of this operation is very important. It may be interesting to find some scaling methods for residue bases having more moduli, so that some part of the computations may be tabulated.

Actually, the FPGA technology seems not really appropriate for RNS implementations of IIR, compared to binary designs. We are confident that CMOS technology may give more interesting results.

Fig. 3 .

 3 Fig. 3. Relative difference between the ideal transfer function and the fixedpoint implemented transfer function

Acc ← Acc + ((x 6 (k) * 73475) >> 1); T 2 ← Acc >> 13; // States x 1 (k + 1) ← x 2 (k); x 2 (k + 1) ← x 3 (k); x 3 (k + 1) ← x 4 (k); x 4 (k + 1) ← x 5 (k); x 5 (k + 1) ← x 6 (k); Acc ← T 1 ; Acc ← Acc + (T 2 << 10); x 6 (k + 1) ← Acc >> 10; x 7 (k + 1) ← x 8 (k);x 8 (k + 1) ← x 9 (k); x 9 (k + 1) ← x 10 (k);x 10 (k + 1) ← x 11 (k); x 11 (k + 1) ← x 12 (k); x 12 (k + 1) ← u(k); // Outputs y(k) ← x 6 (k + 1); end Algorithm 2: Direct Form I: Fixed-point algorithm