Degree bounds and lifting techniques for triangular sets

� Eric Schost, Laboratoire GAGE, � Ecole polytechnique

91128 Palaiseau, France Eric.Schost@polytechnique.fr

ABSTRACT

We study the representation of the solutions of a polynomial system by triangular sets, and concentrate on the positivedimensional case. We reduce to dimension zero by placing the free variables in the base-field, so the solutions can be represented by triangular sets with coefficients in a rational function field. First, we give bounds on the degree of these coefficients; then we show how to apply lifting techniques in this context, and point out the role played by the evaluation properties of the input system. Our algorithms are implemented in Magma; we present two applications.

1. MAIN RESULTS

We first define triangular sets over a ring A. A triangular set is a family of polynomials T = (T_{1}, …, T_{n}) in A[X_{1}, …, X_{n}] such that, for k ≤ n: T_{k} depends only on (X_{1}, …, X_{k}), T_{k} is monic of degree d_{k} > 0 in X_{k} and T_{k} has degree in X_{j} less than d_{j}, for j < k. We let (T) denote the ideal generated by T. Let now K be a field, V ⊂ 𝔸^{n}(\overline{K}) a zero-dimensional algebraic set defined over K; a family {T^{1}, …, T^{P} } of triangular sets with coefficients in K represents the zeros of V if I(V) = ∩_{i≤P} (T^{i}), and if for i ≠ j, T^{i} and T^{j} have no common zero. Then all (T^{i}) are radical ideals.

Our definition is inspired by that of reduced triangular sets in [18]. If V is irreducible, the family we seek exists, is unique and reduced to a single triangular set; then ∏_{k≤n} deg_{X_{k}} T_{k} is the cardinality of V. If V is not irreducible, a family {T^{1}, …, T^{P} } satisfying our conditions exists but is not unique [18, Prop. 2 and Rem. 1]; then ∑_{i≤P} ∏_{k≤n} deg_{X_{k}} T_{k}^{i} is the cardinality of V. If X_{1} separates the points in V, we obtain a representation by primitive element, called geometric resolution after [12, 10, 11, 13].

For a positive dimensional variety V ⊂ 𝔸^{N}(\overline{K}), several notions of triangular sets exist [16, 19, 3, 6, 24]. In this situation, we choose to reduce to dimension zero, by considering a projection of V on a suitable linear space L. We require the projection V → L to be dominant with generically finite fibers. As a motivation, note that many questions in polynomial systems solving are of parametric nature: the systems come with distinguished variables, some parameters, and admit a finite number of solutions for a generic value of the parameters. Such situations are zero-dimensional over the field of functions on the parameter-space L.

We formalize this situation the following way. We consider a m-dimensional variety V ⊂ 𝔸^{m+n}(\overline{K}), defined over K. Let {V_{i}}_{i∈I} denote the K-irreducible components of V, and π the projection 𝔸^{m+n}(\overline{K}) → 𝔸^{m}(\overline{K}). Our main assumption, already done in [22], is that the image by π of each V_{i} is dense in 𝔸^{m}(\overline{K}). Then the fibers of π are generically finite.

We denote by P = P_{1}, …, P_{m} the first m coordinates, and by X = X_{1}, …, X_{n} the last coordinates in 𝔸^{m+n}(\overline{K}); the variables P are called parameters. Let I ⊂ \overline{K}[P, X] be the radical ideal defining V, I_{P} its extension in \overline{K}(P)[X] and A_{P} the quotient \overline{K}(P)[X]/I_{P}. Our first assumption implies that A_{P} is a finite dimensional \overline{K}(P)-algebra. Our second assumption is that the extension \overline{K}(P) → A_{P} is separable. By [14, Prop. 1], its dimension is the generic number of points in the fibers of π_{|V}, which will be denoted by deg π.

We call generic zeros of V the roots of I_{P}. Since they are in finite number, they can be represented by a family of triangular sets in K(P)[X]. If {T^{1}, …, T^{P} } is such a family, ∑_{i≤P} ∏_{k≤n} deg_{X_{k}} T_{k}^{i} equals deg π by the above discussion.

Our first result is a bound on the degrees in (P_{1}, …, P_{m}) of the coefficients of such triangular sets, using the geometric notion of degree introduced in [14].

Theorem 1. Let W be the reunion of some of the irreducible components of V, defined over K, such that the generic zeros of W can be represented by a single triangular set T = (T_{1}, …, T_{n}), with T_{k} ∈ K(P)[X] for k ≤ n. For k ≤ n, denote by W_{k} ⊂ 𝔸^{m+k}(\overline{K}) the projection of W on 𝔸^{m+k}(\overline{K}) and by D_{k} its degree. Then all coefficients of T_{k} are rational functions in K(P) of degree at most

(2k^{2} + 4k + 3)^{k+1}D_{k}^{2k+3}.

This is in the continuity of the results of Gallo-Mishra [7] and Szanto [24] for Ritt-Wu’s and Kalkbrener’s unmixed representations. If V is given as the zero-set of a system of n equations of degree d, Gallo-Mishra’s bound is 2n(8n)^{2n}d(d + 1)^{4n^{2}} and Szanto’s is d^{O(n^{2})}.

With this notation, the Bézout inequality of [14] implies that D_{k} is at most d^{n} for all k. Thus according to Theorem 1, in a worst-case scenario the degrees of the coefficients in the triangular set (T_{1}, …, T_{n}) are bounded by 81d^{5n} for T_{1}, 6859d^{7n} for T_{2}, …, (2n^{2} + n + 3)^{n+1}d^{n^{2}+3n} for T_{n}. This improves the previous results, which gave the same bounds for all T_{k}; yet we do not know if these bounds are sharp.

Another new feature is that our bounds are given in terms of the intrinsic geometric quantities D_{k}, which may be bounded a priori. In the example presented in Section 4.2, the Bézout bound is 1024, but an a priori estimate based on the semantics of the problem gives D_{k} ≤ 80.

The second part of this article presents lifting techniques for triangular sets. We restrict the context to a variety V given as the zero-set of a system F = F_{1}, …, F_{n} with indeterminates (P, X) = (P_{1}, …, P_{m}, X_{1}, …, X_{n}), with the additional assumption that the Jacobian determinant w.r.t. X is invertible on an open subset of V. Then the previous two assumptions are satisfied, and we want to compute triangular sets in K(P)[X] that represent the generic zeros of V.

The underlying paradigm is that solving a zero-dimensional system over K by means of triangular sets is a well-solved task. Thus, the basic idea is first to specialize the indeterminates P in the system F, and solve the corresponding system in the remaining variables X, by means of triangular sets in K[X]. A lifting process then produces triangular sets with coefficients in a formal power series ring, from which we can recover the required information.

We do not give a full algorithm. Difficulties arise when recombining factorized triangular sets, so our first contribution treats the case when V is irreducible: its generic zeros are represented by a single triangular set T = (T_{1}, …, T_{n}), and we propose an algorithm that computes T_{1}, …, T_{k} for any k. If V is not irreducible, we compute the minimal polynomial of X_{1} in A_{P}, which can be read off triangular sets.

The complexity of evaluation of the system F plays a crucial role here: F is given by a Straight-Line Program of size L. In the sequel, M(d, m) is the number of monomials of degree at most d in m variables, and C a universal constant, see Section 3.2. The algorithms are probabilistic in the choice of the points p, p′ below: the choices leading to an error are enclosed in a strict algebraic subset of 𝔸^{2m}(\overline{K}). The degree analysis of this subset is done for Theorem 3 in [23, Ch. 18, 19], and has to be done for Theorem 2.

The following results were improved from an earlier version thanks to the anonymous referees’ comments. All complexities are stated in terms of number of operations in K.

Theorem 2. Assume that V is irreducible. Let p, p′ be generic enough points in K^{m}; assume that a description of the zeros of the systems F (p, X), F (p′, X) by triangular sets is available. Let T be the triangular set in K(P)[X] that represents the generic zeros of V, choose k ≤ n and let 𝔇_{k} be the maximal degree in P of the coefficients of T_{1}, …, T_{k}. Then T_{1}, …, T_{k} can be computed by a probabilistic algorithm in time polynomial in L, C^{n}, deg π, M(𝔇_{k}, m).

Theorem 3. Let p, p′ be generic enough points in K^{m}, and assume that a description of the zeros of the systems F (p, X), F (p′, X) by triangular sets which define prime ideals is available. Let M_{1} ∈ K(P)[X_{1}] be the minimal polynomial of X_{1} in A_{P}, and 𝔇_{1} the maximal degree in P of its coefficients. Then M_{1} can be computed by a probabilistic algorithm in time polynomial in L, C^{n}, deg π, M(𝔇_{1}, m).

This work was greatly motivated by applications. The first accounts for computations done in [9] to study genus 2 curves with (2,2)-split Jacobian, which occur frequently in number theory. The second shows how to compute the modular equations for hyperelliptic curves defined in [8, 23] with a view towards applications in cryptography; our result is now used within Magma’s hyperelliptic curve package [1].

Comparison with primitive elements techniques.

The present results are in the continuation of [22], which focuses on a representation by primitive elements, under the same hypotheses. Caution must be taken when comparing the two approaches. They answer different needs; as such, their complexities cannot be compared directly, since they are stated in terms of different quantities.

Assume for simplicity that the generic zeros of V are represented by a single triangular set. The degree bound in a geometric resolution is linear in the degree of V, see Proposition 1 below. On the other hand, using a primitive element, we cannot take into account the degrees of the projections of V, which can be arbitrarily smaller than the degree of V. This refinement makes the interest of the triangular representation, using results such as Theorem 1.

Consider now the algorithmic aspect. The algorithm in [22] computes a generic geometric resolution in time polynomial in L, deg π, M(deg V, m), where deg V is the degree of V. Here, using Theorem 1, the complexity in Theorems 2 and 3 is seen to depend on the degree of the projections of V on the spaces of coordinates (P, X_{1}, …, X_{k}) for Theorem 2, or (P, X_{1}) for Theorem 3, but not on the degree of V itself, which can be arbitrarily bigger.

Thus, the present approach takes more refined complexity measures into account. It will prove of interest for structured problems, when a partial information (e.g. a minimal polynomial) is wanted: the computational cost will not depend on the whole degree of V, as when using a primitive element, but only on that of a suitable projection, which might turn out to be smaller. The applications in Section 4 are examples of this phenomenon, and illustrate the practical interest of our approach in this situation. Their study inspired this work in the first place.

Related results.

In dimension zero, a landmark paper for the representation by triangular sets is [18]. In arbitrary dimension, several notions and algorithms exist, see [16, 19, 3, 6, 24], and [4] for a comparison of some of them. Our choice to reduce the question to dimension zero over a field of rational functions yields algorithms with good complexity, and easy to implement. Yet, our output is not as strong as for instance [19, 6], since it is only generically valid.

An important feature of our algorithms is the representation of the input system by evaluation. This approach proved successful for solving systems by primitive element techniques, in a series of articles by the TERA group, see [12, 10, 11, 13] and references therein. In particular the article [15], with a similar approach but under more restrictive hypotheses, inspired [22] and the present work. Finally, parallel arithmetic circuits are used for triangular sets in [24].

Notation.

The letter T denotes a triangular set (T_{1}, …, T_{n}). A family of triangular sets is denoted with superscripts as T^{1}, …, T^{P}, each T^{i} being a triangular set (T_{1}^{i}, …, T_{n}^{i}). The letter X stands for X_{1}, …, X_{n}, and P for P_{1}, …, P_{m}. Bold letters denote matrices or vectors. Finally, I_{P} is an ideal in \overline{K}(P)[X], and A_{P} the corresponding quotient algebra.

2. DEGREE BOUNDS

Representation by primitive elements.

The following is a variation on the Primitive Element Theorem. The version we use is a slight extension of [22, Prop. 2], and applies under the assumptions of Section 1; it is inspired by [12, 21].

Proposition 1. There exists (u_{1}, …, u_{n}) ∈ \overline{K}^{n} such that u_{0} := ∑_{i=1}^{n} u_{i}X_{i} generates A_{P}. Besides, there exists some polynomials V, V_{1}, …, V_{n} in \overline{K}[P][U] such that

• the total degrees of V, V_{1}, …, V_{n}, seen in \overline{K}[P, U], are bounded by deg V;

• V′(u_{0}) is invertible in A_{P}, the relations

V (u_{0}) = 0, V′(u_{0})X_{i} = V_{i}(u_{0}) (1 ≤ i ≤ n)

hold in A_{P}, so the ideal I_{P} + (U − u_{0}) coincides with

(V (U), V′(U)X_{1} − V_{1}(U), …, V′(U)X_{n} − V_{n}(U)).

Effective B� ezout bound.

The following is Lemma 5 in [17]; similar results can be seen in [10], originating from [12]. As pointed out by a referee, a bound similar to Theorem 1 can be obtained without this result, by working out an explicit division procedure.

Proposition 2. Let 𝔎 be a field, and (F_{1}, …, F_{N}) a regular sequence in 𝔎[Y_{1}, …, Y_{N}]. Let d be a bound on the degrees of the polynomials F, and δ the maximum of the degrees of the varieties V(F_{1}, …, F_{i}), for i = 1, …, N −1. For i = 0, …, N − 1, let B_{i} be the quotient

𝔎[Y_{1}, …, Y_{N}]/(F_{1}, …, F_{N−i}).

Assume that the extension 𝔎[Y_{1}, …, Y_{i}] → B_{i} is integral and that the jacobian of (F_{1}, …, F_{N−i}) w.r.t. (Y_{i+1}, …, Y_{N}) is a non-zero divisor in B_{i}. Then if H belongs to (F_{1}, …, F_{N}), there exists polynomials (Q_{1}, …, Q_{N}) in 𝔎[Y_{1}, …, Y_{N}] such that H = Q_{1}F_{1} + ⋯ + Q_{N}F_{N}, and, for i = 1, …, N, deg Q_{i}F_{i} ≤ 2N^{2}dδ + δ max{deg H, d}.

Proof of Theorem 1.

Let W be the reunion of some of the irreducible components of V, such that the generic zeros of W can be represented by a single triangular set T = (T_{1}, …, T_{n}). For k ≤ n, denote by W_{k} ⊂ 𝔸^{m+k}(\overline{K}) the projection of W on 𝔸^{m+k}(\overline{K}) and by D_{k} its degree. We now prove that all coefficients in T_{k} are of degree bounded by (2k^{2} + 4k + 3)^{k+1}D_{k}^{2k+3}.

Let J ⊂ \overline{K}[P, X] be the ideal defining W, J_{P} its extension in \overline{K}(P)[X], and B_{P} the algebra \overline{K}(P)[X]/J_{P}. Since A_{P} is a separable extension of \overline{K}(P), so is B_{P}. Also, by definition of T, J_{P} is the ideal generated by T = (T_{1}, …, T_{n}) in \overline{K}(P)[X].

Denote by X_{≤k} the variables X_{1}, …, X_{k}, J_{≤k} ⊂ \overline{K}[P, X_{≤k}] the ideal defining W_{k}, that is, J ∩ \overline{K}[P, X_{≤k}], and J_{P,≤k} its extension in \overline{K}(P)[X_{≤k}]. Under our first assumption that none of the prime components of I contains a polynomial in \overline{K}[P], it is a routine check that J_{P,≤k} = J_{P} ∩\overline{K}(P)[X_{≤k}], i.e. the ideal generated by (T_{1}, …, T_{k}) in \overline{K}(P)[X_{≤k}]. Besides, since \overline{K}(P) → B_{P} is separable, it is also the case for \overline{K}(P) → \overline{K}(P)[X_{≤k}]/J_{P,≤k}.

Thus W_{k} satisfies the hypotheses of Proposition 1, so, using a new variable U, there exist scalars u_{1}, …, u_{k} in \overline{K}^{k}, and polynomials V, V_{1}, …, V_{k} such that the ideal generated by T_{k} and U − ∑_{i=1}^{k} u_{k}X_{k} in \overline{K}(P)[X_{≤k}, U] coincides with

(V (U), V′(U)X_{k} − V_{k}(U), …, V′(U)X_{1} − V_{1}(U)).

Let us consider the systems

S = (V (U), V′(U)X_{k} − V_{k}(U), …, V′(U)X_{1} − V_{1}(U)),

and for 0 ≤ i ≤ k,

S_{i} = (V (U), V′(U)X_{k} − V_{k}(U), …, V′(U)X_{i+1} − V_{i+1}(U)),

in \overline{K}(P)[X_{≤k}, U]. We check that the hypotheses of Proposition 2 are satisfied for S, with 𝔎 = \overline{K}(P), N = k + 1, and Y_{1}, …, Y_{N} = X_{1}, …, X_{k}, U. By Proposition 1, V′(U) is invertible modulo V (U). Thus modulo V (U), each equation V′(U)X_{j} − V_{j}(U) can be written X_{j} − W_{j}(U), for some polynomial W_{j}(U) in \overline{K}(P)[U].

This shows that S is a regular sequence. For i in 0, …, k, the ring B_{i} in Proposition 2 is \overline{K}(P)[X_{≤k}, U]/S_{i}, which is an integral extension of \overline{K}(P)[X_{1}, …, X_{i}]. Finally, the jacobian determinant of S_{i} with respect to X_{i+1}, …, X_{k}, U is the (k − i)-th power of V′(U), so it is invertible in B_{i}. Consequently, the hypotheses of Proposition 2 are satisfied. Since the variables P are in the basefield 𝔎 = \overline{K}(P), we estimate all degrees in terms of the variables (X_{≤k}, U) only. By Proposition 1, the degrees of all polynomials in S are bounded by D_{k}. The varieties V(S_{i}) are cylinders built upon zero-dimensional varieties of degree at most D_{k} over \overline{𝔎}, so their degree over \overline{𝔎} is at most D_{k}.

All polynomials T_{1}, …, T_{k} belong to the ideal generated by S. Consequently, for i ≤ k, there exist some polynomials Q_{0,i}, …, Q_{k,i} in \overline{K}(P)[X_{≤k}, U] such that the equality

T_{i} = Q_{0,i}V (U) + ∑_{j=1}^{k} Q_{j,i}(V′(U)X_{i} − V_{i}(U))  (1)

holds in \overline{K}(P)[X_{≤k}, U].

Let us fix i, and apply Proposition 2. Our Conventions on the elements of a triangular set show that the degree of T_{i} in X_{1}, …, X_{k} is at most D_{k}. Proposition 2 then shows that the degree in X_{1}, …, X_{k} of each summand in (1) can be taken less than 2(k + 1)^{2}D_{k}^{2} + D_{k}^{2} = (2k^{2} + 4k + 3)D_{k}^{2}.

The conclusion is now similar to that of [7]. Writing T_{i} = X_{i}^{d_{i}} + R_{i}, with deg_{X_{i}} R_{i} < d_{i}, identity (1) can be rewritten

X_{i}^{d_{i}} = −R_{i} + Q_{0,i}V (U) + ∑_{j=1}^{k} Q_{j,i}(V′(U)X_{i} − V_{i}(U)).

This in turn can be rewritten as a linear system in the coefficients of R_{i}, Q_{0,i}, …, Q_{k,i}. Let G be the number of monomials in k + 1 variables of degree at most (2k^{2} + 4k + 3)D_{k}^{2}, and let G′ ≤ G be the number of unknown coefficients in R_{i}. This system can be written MA = B, where A is the vector of (k + 1)G + G′ unknowns, and B is the zero vector, except for one entry equal to 1, corresponding to the coefficient of X_{i}^{d_{i}}. The matrix M has G rows and (k + 1)G + G′ columns, and its entries are either the constant 1, or the coefficients of V, V′, V_{1}, …, V_{n}. These are polynomials in (P_{1}, …, P_{m}) of degree at most D_{k}, by Proposition 1.

The coefficients of R_{i} are uniquely determined: if there were two possible choices for R_{i}, then their difference would yield a polynomial in the ideal generated by the system S of degree less than d_{i} in X_{i}, an impossibility. Consequently, by Rouché-Fontené’s Theorem, the coefficients of R_{i} can be expressed as quotients of determinants of size at most G, with entries that are polynomials in P_{1}, …, P_{m} of degree at most D_{k}. Then their numerators and denominators have degree at most GD_{k}, which is bounded by (2k^{2} + 4k + 3)^{k+1}D_{k}^{2k+3}. This concludes the proof of Theorem 1.

3. LIFTING TECHNIQUES

We now present some lifting techniques for triangular sets. This requires a stronger assumption than before: V is now supposed to be defined by some polynomials F = F_{1}, …, F_{n} in K[P, X], where P = P_{1}, …, P_{m} and X = X_{1}, …, X_{n}. Furthermore, we assume that the jacobian determinant of F with respect to X is invertible on an open subset of V. For complexity statements, we assume that F is given by a Straight-Line Program that performs L operations.

From the invertibility of the jacobian, Lazard’s lemma [5] as proved in [20] implies that V satisfies the assumptions of Section 1, so the generic zeros of V can be represented by triangular sets. To be specific, we denote by T^{1}, …, T^{P} a family of triangular sets in K(P)[X] that represent the generic zeros of V and define prime ideals in K(P)[X].

In the sequel, given p in 𝔸^{m}(\overline{K}), F (p, X) denotes the system F where the variables P are evaluated at p; then there remain n equations in the n unknowns X. The “specialization” of a triangular set T ∈ K(P)[X] at p denotes the triangular set T ∈ \overline{K}[X], obtained by specializing all coefficients of T at p, if p cancels none of their denominators.

Here is the description of a could-be lifting process. Choose a generic value p in 𝔸^{m}(\overline{K}), and compute a family of triangular sets that represent the solutions of F (p, X). Apply a lifting process, to compute triangular sets with coefficients in the formal power series ring centered at p. When the precision of the power series is high enough, use a rational reconstruction process to recover the requested information. For the introduction of lifting techniques in the context of polynomial systems solving, see [12, 11, 10, 15, 13].

Recovering completely T^{1}, …, T^{P} using such techniques requires delicate recombinations of factorized triangular sets. We will not treat the general case here: we present probabilistic algorithms to treat the case when V is irreducible, and, in the general case, to recover the minimal polynomial of the variable X_{1} (which comes from the first polynomials of each triangular set). We refer to [23] for estimates on the error probability for the minimal polynomial computation.

We now specify the genericity conditions imposed on the specialization value p. There exists an hypersurface Δ of 𝔸^{m}(\overline{K}) such that, for p not in Δ: (H_{1}) all coefficients in T^{1}, …, T^{P} can be specialized at p, and (H_{2}) the jacobian of F (p, X) is invertible on all solutions of F (p, X).

In the sequel, we assume that we are given a point p outside Δ with coordinates in K; randomly choosing this point is our first probabilistic aspect. The following condition is a consequence of the above assumptions; since we do not give the proof of this implication, we take this as a new assumption on p, called H_{3}: all solutions of F (p, X) are described by the specialization of T^{1}, …, T^{P} at p and if i ≠ j, the specializations of T^{i} and T^{j} at p have no common zero.

In 3.2, we recall some lifting techniques from in [22], that enable the lifting of the specializations of T^{1}, …, T^{P} at p. Yet, the solutions of F (p, X) may not be given as the specialization of T^{1}, …, T^{P}, since they may be more factorized. Thus in 3.3, we show that the lifting techniques presented in 3.2 can be applied independently to each factor of the specializations of T^{1}, …, T^{P}. In 3.4, we treat the case when V is irreducible. In 3.5, we drop the irreducibility assumption, and show how to recover the minimal polynomial of X_{1} modulo I_{P}.

3.1 Additional subroutines

Initial resolution.

The first task is to compute a family of triangular sets r^{1}, …, r^{Q} which represent the solutions of F (p, X); this is called Solve(F,p). In Subsection 3.5, we also ask that all triangular sets r^{1}, …, r^{Q} define prime ideals. To this effect, we may use the zero-dimensional solving procedures of [18, 6, 4] … In the sequel, we do not take the cost of this phase into account, all the more as the cost of the lifting phase is predominant in practice.

Rational Reconstruction.

At the end of the lifting process, we need to recover some rational functions in P = P_{1}, …, P_{m} from their power series expansion. More precisely, if c is a formal power series in P of precision 2^{κ+1}, we look for a rational function C with denominators of degree at most 2^{κ} of which c is the power series expansion. Finding such a rational function, if it exists, amounts to solve a linear system for the coefficients of C. This is done in time polynomial in M(2^{κ}, m).

3.2 Lifting step

We now present the lifting techniques of [22]. Let T = (T_{1}, …, T_{n}) be one the triangular sets T^{1}, …, T^{P}. Up to a change of variables, we can assume that the specialization value p is (0, …, 0). We denote by A the power series ring K[[P_{1}, …, P_{m}]], and 𝔪 its maximal ideal, so A/𝔪 = K.

Since T generates a prime, hence radical, ideal in K(P)[X], there exists a n × n matrix A with entries in K(P)[X] such that F = AT, where T is the vector with entries T_{1}, …, T_{n}, and F is the vector F_{1}, …, F_{n}. Assumption H_{1} on p shows that all coefficients in T admit power series expansions in A. Since all polynomials in T are monic in their main variable, the denominators in A are products of those in T, so they all admit power series expansions in A.

We now see F, T, A with coefficients in A, and denote T mod 𝔪 by t = (t_{1}, …, t_{n}), that is, T with all coefficients specialized at p. The hypotheses we now use are the following. The first is a consequence of H_{2} and H_{3}, and the second comes from the above discussion.

H′_{1} : The jacobian determinant of F with respect to X is invertible in the quotient K[X]/(t_{1}, …, t_{n}).

H′_{2} : There exists a n × n matrix A with entries in A[X] such that the equality F = AT holds.

For k > 0, denote by A_{k} the ring A/𝔪^{k}, so that A_{1} = A/𝔪 = K. We want to compute the images of T in the rings A_{2^{κ}}[X], for κ ≥ 0. This amounts to compute the powers series expansions of all coefficients of T in K[[P_{1}, …, P_{m}]] at successive precisions 2^{κ}. The initial value is t = T mod 𝔪, which we assume to be known.

Let κ ≥ 0 be given, and suppose that we know a triangular set τ = (τ_{1}, …, τ_{n}) such that τ = T mod 𝔪^{2^{κ}}. Using τ, we want to compute T mod 𝔪^{2^{κ+1}}. We formalize our assumption by seeing τ as a triangular set in A_{2^{κ+1}}[X] such that T = τ mod (𝔪^{2^{κ}} · A_{2^{κ+1}}[X]). Since τ is a triangular set, all τ_{j} are monic, so deg_{X_{j}} T_{j} = deg_{X_{j}} τ_{j} for j ≤ n.

Let Q_{κ} be A_{2^{κ+1}}[X]/(τ_{1}, …, τ_{n}). Then Q_{κ} is a free A_{2^{κ+1}}- module, with a canonical monomial basis. We denote by Jac(τ) and Jac(F_{κ}) the jacobian matrices of τ and F computed in the matrix algebra over Q_{κ}, and F_{κ} the image of F in Q_{κ}. In [22], we prove the following.

Proposition 3. The matrix Jac(F_{κ}) is invertible in the matrix algebra over Q_{κ}. Let then δ = (δ_{1}, …, δ_{n}) be the product Jac(τ)Jac(F_{κ})^{−1}F_{κ} evaluated over the ring Q_{κ}, and δ̃ its canonical preimage in A_{2^{κ+1}}[X]. Then the equality T = τ + δ̃ holds in A_{2^{κ+1}}[X]. Besides, it is enough to compute the inverse of Jac(F_{κ}) modulo 𝔪^{2^{κ}}.

This result shows how to compute the new approximation T mod 𝔪^{2^{κ+1}}, which can be used instead of τ for the next lifting step. In the sequel, given F, p and τ, we will denote Lift(t,F,p) the subroutine which performs the operations above, and outputs T mod 𝔪^{2^{κ+1}}.

Example.

Let us take one parameter P_{1}, two variables X_{1}, X_{2} and

F_{1} : 2X_{1}^{2}−P_{1}+1−X_{1}X_{2}^{2}P_{1}−X_{1}X_{2}^{2}−X_{2}X_{1}^{3}+X_{1}X_{2}P_{1}−X_{1}X_{2}

F_{2} : X_{2}^{2}P_{1} + X_{2}^{2} − X_{1} + X_{2}X_{1}^{2} − X_{2}P_{1} + X_{2}.

This system is constructed so that its solutions can be represented by the following triangular set in ℚ(P_{1})[X_{1}, X_{2}].

T_{1} = X_{1}^{2} − P_{1} + 1, T_{2} = X_{2}^{2} − X_{1}/(P_{1} + 1).

To compute T_{1}, T_{2}, we choose the specialization value P_{1} = 0, and solve the specialized system. This gives:

t_{1} = X_{1}^{2} + 1, t_{2} = X_{2}^{2} − X_{1}.

Here κ = 0, 2^{κ+1} = 2, so the base-ring A_{2} is ℚ[[P_{1}]]/(P_{1}^{2}); τ = (X_{1}^{2} + 1, X_{2}^{2} − X_{1}) and all computations are done over Q_{0} = A_{2}[X_{1}, X_{2}]/(τ_{1}, τ_{2}). The jacobian matrix of τ is

Jac(τ) = [ \begin{matrix}2X_{1} & 0 \\ −1 & 2X_{2} \end{matrix} ] ,

the inverse of the jacobian matrix of F, Jac(F_{κ})^{−1}, is

\frac{1}{8} [ \begin{matrix}2P_{1}X_{2} + (−2P_{1} − 4)X_{1} & 2P_{1}X_{1}X_{2} + 2P_{1} + 4 \\ (P_{1} − 2)X_{2} + 2P_{1} − 4 & (5P_{1} − 6)X_{1}X_{2} − 4X_{1} \end{matrix} ] ,

and the image of F in Q_{0}, denoted F_{κ}, is

(P_{1}X_{1}X_{2}, −P_{1}X_{2} + P_{1}X_{1}).

Then we apply Proposition 3: we compute the value δ = (−P_{1}, P_{1}X_{1}), so the approximation at precision P_{1}^{2} is

X_{1}^{2} + 1 − P_{1}, X_{2}^{2} − X_{1} + P_{1}X_{1}.

This is indeed the expansion of T_{1}, T_{2} at precision P_{1}^{2}. The terms in Jac(F_{κ})^{−1} of degree in P_{1} > 0 are not used, since F_{κ} has valuation 1 in P_{1}; this is the last statement in Proposition 3.

Complexity.

We let C be a universal constant such that, for any ring R and any triangular set T, the operations +, ×, and ÷ when it is possible, can be done modulo T in a numbers of operations in R polynomial in C^{n} and ∏_{i≤n} deg_{X_{i}}T_{i} . The inverse of the determinant of Jac(F_{κ}) is computed by induction on κ by Hensel’s Lemma [25, Ch. 9], using multiplications in Q_{κ}: the only inversion is done for κ = 0, and can be done in K[X]/(t_{1}, …, t_{n}), according to Proposition 3.

An operation +, × in Q_{κ} takes a number of operations in A_{2^{κ+1}} polynomial in C^{n}, ∏_{i≤n} deg_{X_{i}}τ_{i}. In terms of operations in K, an operation in A_{2^{κ+1}} has a cost polynomial in M(2^{κ+1}, m), the number of monomials of degree ≤ 2^{κ+1} in m variables. Since deg_{X_{i}} τ_{i} = deg_{X_{i}} T_{i}, the number of operations in K is polynomial in C^{n}, ∏_{i≤n} deg_{X_{i}}T_{i}, M(2^{κ+1}, m).

Computing Jac(F_{κ}) and F_{κ} requires to evaluate the system F and its jacobian matrix in Q_{κ}. Since we assume that F is given by a Straight-Line Program that performs L operations, this cost is O(nL) operations in Q_{κ} [13]. The other operations are linear algebra with matrices of size n over Q_{κ}, which can be done in n^{O(1)} ∈ O(C^{n}) operations in Q_{κ}. Finally, the total cost of procedure Lift, in operations in K, is polynomial in L, C^{n}, ∏_{i≤n} deg_{X_{i}}T_{i}, M(2^{κ+1}, m).

3.3 Factorized lifting

In practice, we cannot ensure that the resolution of the system F (p, X) is given as the specialization of T^{1}, …, T^{P} at p, since it may be more factorized. Thus, we now prove that the lifting can be applied to any factor of t = T mod 𝔪.

Proposition 4. Let r be a triangular set in K[X] such that the ideal generated by r contains t. Then there exists a triangular set R in A[X] such that R mod 𝔪 = r and the ideal generated by R contains T. The successive approximations R mod 𝔪^{2^{κ}} can be computed using Proposition 3.

Proof. First consider a particular case: we suppose that there exists J ≤ n such that the following holds. Let B denote A[X_{1}, …, X_{J−1}]/(T_{1}, …, T_{J−1}) and 𝔫 the ideal of B induced by 𝔪 + (T_{1}, …, T_{J−1}). Thus, the quotient B/𝔫 is K[X_{1}, …, X_{J−1}]/(t_{1}, …, t_{J−1}). Our assumption is:

• r_{1}, …, r_{J−1} = t_{1}, …, t_{J−1};

• there exists a polynomial q_{J} in B/𝔫 [X_{J}] such that t_{J} = q_{J}r_{J} holds in B/𝔫 [X_{J}];

• for j in J + 1, …, n, we see t_{j} as a polynomial in the variables X_{J+1}, …, X_{j} with coefficients in B/𝔫 [X_{J}], and assume that r_{j} is obtained by reducing all these coefficients modulo r_{J}.

Since A is complete with respect to the 𝔪-adic topology, B is complete with respect to the 𝔫-adic topology. Hypotheses H′_{1} and H′_{2} imply that the derivative of t_{J} w.r.t. X_{j} is invertible in B/𝔫 [X_{J}]/(t_{J}). Hensel’s Lemma then shows that there exists Q_{J} and R_{J} in B such that T_{J} = Q_{J}R_{J} holds in B[X_{J}] and r_{J} = R_{J} mod 𝔫. The polynomial R_{J} is defined in B[X_{J}], but we may identify it to its canonical preimage in A[X_{1}, …, X_{J}] ⊂ A[X_{1}, …, X_{n}].

For j < J, we define R_{j} = T_{j}. For j > J, we define R_{j} as follows. We see T_{j} as polynomial in the variables X_{J+1}, …, X_{j} with coefficients in B[X_{J}], and define R_{j} by reducing all these coefficients modulo R_{J}. As such, this polynomial is a multivariate polynomial in X_{J+1}, …, X_{j} with coefficients in A[X_{1}, …, X_{J}] modulo T_{1}, …, T_{J−1}, R_{J}, but as above, we may identify it with its canonical preimages in A[X_{1}, …, X_{n}]. Through this identification, r = R mod 𝔪.

We then prove the existence of a matrix B such that the equality T = BR holds, by successively constructing its lines. For j < J, we have T_{j} = R_{j}, so we take a line composed only of 0’s, with 1 at entry j. Let us now take j = J. The equality T_{J} = Q_{J}R_{J} in B[X_{J}] can be rewritten in A[X_{1}, …, X_{J}] as T_{J} = Q_{J}R_{J} + S_{J}, where S_{J} is in the ideal (T_{1}, …, T_{J−1}) = (R_{1}, …, R_{J−1}), and R_{J} is seen in A[X_{1}, …, X_{J}]. This enables to define the J-th line of B. Finally, we take j > J. Then R_{j} is such that R_{j} = T_{j} with all coefficients reduced modulo R_{J} in B[X_{J}]. Thus, T_{j} = R_{j} + s_{j}, where s_{j} is in the ideal generated by R_{J} in B[X_{J}, …, X_{j}]. From the definition of B, this can be rewritten as T_{j} = R_{j} + S_{j} in A[X_{1}, …, X_{j}], where S_{j} is in the ideal (T_{1}, …, T_{J−1}, R_{J}) = (R_{1}, …, R_{J}). This enables to complete the definition of B.

We now turn to the proposition itself. Let J be the least integer such that r_{J} ≠ t_{J}. If r = t, we take J = n + 1. We prove by induction on J that if T satisfies hypotheses H′_{1}, H′_{2}, and t = T mod 𝔪 belongs to the ideal generated by r, then there exists a triangular set R such that r = R mod 𝔪, and a n × n matrix B with entries in A[X] such that T = BR. We call this property P (J); P (n + 1) is obvious, so we suppose that J ≤ n and that P is proved for J + 1, …, n + 1.

Since t_{J} is in the ideal generated by r, it is easy to deduce that r_{J} divides t_{J} in K[X_{1}, …, X_{J−1}]/(t_{1}, …, t_{J−1})[X_{J}]. We then define a triangular set s in K[X_{1}, …, X_{n}] as follows. We take s_{1}, …, s_{J} = r_{1}, …, r_{J}, and for j > J we define s_{j} as t_{j} with all coefficient reduced modulo s_{J}. Thus T and s satisfy the hypotheses of the previous paragraphs, which enables to define a triangular set S and a matrix B such that T = BS and s = S mod 𝔪.

The triangular set S satisfies H′_{1} and H′_{2}. For j > J, s_{j} − t_{j} is in the ideal generated by r. Since t_{j} is in this ideal, s_{j} is in this ideal too. Consequently, we can apply our induction argument on S and r, since now s and r coincide at least up to level J. This shows the existence of a triangular set R and a matrix B′ such that S = B′R, and R mod 𝔪 = r. Thus, T = BB′R. This shows P (J), which gives the first part of the proposition. We have F = ABB′R, which gives H′_{2} for R. It is easy to check that R satisfies H′_{1}, so Proposition 3 applies to R. □

3.4 The irreducible case

We now assume that V is irreducible. Then its generic zeros can be described by a single triangular set T. We fix k ≤ n, and show how to compute (T_{1}, …, T_{k}) by lifting techniques.

By assumption H_{3}, the specialization of T at p gives a description of the solutions of the system F (p, X). Yet, the specialized system may not define an irreducible set, and could be represented by more than one triangular set. Thus, we explicitly require that Solve(F,p) outputs a single triangular set, which must then be the specialization of T at p. Then the algorithm is straightforward:

r <- Solve(F,p)
while not(Finished) do
  r <- Lift(r,F,p)
  Finished,R1,...,Rk <- Stop(r)
end while
return R1,...,Rk

The subroutine Stop first tries to compute a rational reconstruction of all the coefficients in r_{1}, …, r_{k}, yielding polynomials R_{1}, …, R_{k}. Even if the reconstruction is possible, it might not coincide with T_{1}, …, T_{k}, if we have stopped the lifting too early. So we choose a witness value p′, which must satisfy the same conditions as p, and compute a description t′_{1}, …, t′_{n} of the solutions of the system F (p, X). Stop tests if the specialization of R_{1}, …, R_{k} at p′ is t′_{1}, …, t′_{k}. If the reconstruction is possible and R passes the test, Stop outputs true and R; else it returns false. The choices of , p, p′ that lead to an error belong to a proper algebraic set of 𝔸^{2m}(\overline{K}).

For such lifting techniques, the whole cost is equivalent to the cost of the last lifting step. Let 𝔇_{k} be the maximal degree in P of the coefficients in T_{1}, …, T_{k}. Then the lifting must be run to precision 2^{p+1}, with p = ⌈log_{2}(𝔇_{k})⌉. From the analysis of Subsection 3.2, the cost of the last lifting step is polynomial in L, C^{n}, ∏_{i≤n} deg_{X_{i}}T_{i}, M(2^{p+1}, m). The product of the degrees is the number of generic solutions, i.e. deg π (see the introduction); since M(2^{p+1}, m) is polynomial in M(𝔇_{k}, m), the cost of the lifting is polynomial in L, C^{n}, deg π, M(𝔇_{k}, m). From Subsection 3.1, the cost of the rational reconstruction fits into this bound, so Theorem 2 is proved.

3.5 Computing a minimal polynomial

Let us drop the irreducibility assumption, and let M_{1} ∈ K(P)[X_{1}] be the minimal polynomial of X_{1} modulo I_{P}. We now show how to compute M_{1} by lifting techniques.

The introduction mentions the use of primitive element techniques for this question (X_{1} is not necessarily a primitive element of A_{P}); we now relate this to triangular sets. The first polynomials of each triangular set, T_{1}^{1}, …, T_{1}^{P}, may not be all distinct. Without loss of generality, assume that T_{1}^{1}, …, T_{1}^{p} are representatives of the distinct polynomials among them, for some p ≤ P. Since T^{1}, …, T^{p} define prime ideals, T_{1}^{1}, …, T_{1}^{p} are irreducible, so their product is M_{1}.

We need a new assumption on p. We denote by V_{p} the zero-set of F (p, X), and by m_{1} the minimal polynomial of X_{1} modulo I(V_{p}). Then we make the following assumption, denoted H_{4}, on p, which is satisfied on an open subset of 𝔸^{m}(\overline{K}): m_{1} is the specialization of M_{1} at p.

Let r^{1}, …, r^{Q} be triangular sets that describe the solutions of F (p, X), and define prime ideals in K[X]. By assumption H_{3}, T^{1}, …, T^{P} can be specialized at p, and their specializations t^{1}, …, t^{P} also describe the solutions of F (p, X). Besides, H_{3} shows that the intersection of the ideals generated by t^{1}, …, t^{P} is actually their product. Then for i ≤ Q, there exists j such that t^{j} is in the ideal defined by r^{i}, so Proposition 3 shows that the lifting process can be applied to r^{i}. Let thus R^{1}, …, R^{Q} be triangular sets with coefficients in K[[P]] such that, for i ≤ Q, R^{i} mod 𝔪 = r^{i}, and there exists j such that T^{j} is contained in the ideal generated by R^{i}. In this case, we see that R_{1}^{i} divides T_{1}^{j}.

The polynomials T_{1}^{j} and M_{1} are actually in K(P)[X_{1}], so if we see them in K[[P]][X_{1}], their coefficients are the Taylor expansions of some rational functions. This is likely not the case for the polynomials R_{1}^{i}, but we can still recover M_{1}.

Proposition 5. Reorder r^{1}, …, r^{Q} so that r_{1}^{1}, …, r_{1}^{q} are representatives of the distinct polynomials in r_{1}^{1}, …, r_{1}^{Q}, for some q ≤ Q. Then ∏_{i≤q} R_{1}^{i} = M_{1} in K[[P]][X_{1}].

Proof. We first show that R_{1}^{1}, …, R_{1}^{Q} are irreducible in the factorial ring K[[P]][X_{1}]. Suppose that R_{1}^{i} = GH in K[[P]][X_{1}]. Since R_{1}^{i} is monic, we may suppose that G and H are monic. Then r_{1}^{i} = (G mod 𝔪)(H mod 𝔪). Since r_{1}^{i} is irreducible, it follows that for instance G mod 𝔪 is a unit. Since G is monic, G is the constant 1, so R_{1}^{i} is irreducible.

The product ∏_{i≤q} r_{1}^{i} is the minimal polynomial of X_{1} modulo I(V_{p}), that is m_{1}. The corresponding R_{1}^{1}, …, R_{1}^{q} are all pairwise distinct, hence pairwise coprime, since they are irreducible. Since each of them divides one of the polynomials T_{1}^{j}, each of them divides M_{1}. Thus ∏_{i≤q} R_{1}^{i} divides M_{1}. The degree of ∏_{i≤q} R_{1}^{i} is the degree of ∏_{i≤q} r_{1}^{i}, that is the degree of m_{1}. By hypothesis H_{4}, it coincides with the degree of M_{1}. Thus, ∏_{i≤q} R_{1}^{i} = M_{1}. □

This gives the following algorithm to compute M_{1}:

                                                        r^1,..,r^Q <- Solve(F,p)
                                                        ## r^1,..,r^Q are chosen to define prime ideals.
                                                        ## we reorder them and take q so that
                                                        ## r^1_1,..,r^q_1 are a set of representatives of
                                                        ## the distinct polynomials among r^1_1,..,r^Q_1.
                                                        while not(Finished) do
                                                          for i in [1..q] do r^i <- Lift(r^i,F,p)
                                                          Finished,M <- Stop(r^1,..,r^q)
                                                        end while
                                                        return M

The subroutine Stop computes the product of all polynomials r_{1}^{i}, and if possible, a rational reconstruction of all coefficients of the product. This gives a polynomial M, on which we apply a probabilistic check: as before, we test whether M specializes on the minimal polynomial of X_{1} for a randomly chosen witness p′.

Let 𝔇_{1} be the maximal degree in P of the coefficients in M_{1}, and p = ⌈log_{2}(𝔇_{1})⌉. As in Subsection 3.4, the complexity is polynomial in L, C^{n}, M(𝔇_{1}, m) and ∑_{i≤q} ∏_{j≤n} deg_{X_{j}} r_{j}^{i}. This last sum is at most the number of generic solutions of the system F, i.e. deg π. This proves Theorem 3.

4. APPLICATIONS

We present two applications of our algorithms, from number theory and cryptography. Our Magma [1] implementation outperformed the built-in functions on these examples; the probabilistic aspect was not a problem: problem-specific arguments show that our output is correct. Our computations were done on a Compaq XP/1000 EV6 from the MEDICIS resource center [2].

4.1 Genus 2 curves with (2,2)-split Jacobian

Genus 2 curves with Jacobian (2,2)-isogeneous to a product of elliptic curves appear frequently in number theory: current rank and torsion records are obtained for such curves. In [9], we give an explicit classification of such situations, using the algorithms presented here. We now describe part of the necessary computations.

Isomorphism classes of genus 2 (resp. elliptic) curves are classified by the Igusa invariants j_{1}, j_{2}, j_{3} (resp. by their j-invariant). There exists a polynomial T (J_{1}, J_{2}, J_{3}) such that a genus 2 curve has (2,2)-split Jacobian if and only if its Igusa invariants cancel T; then the j-invariants of the elliptic curves are given by a polynomial of degree 2, whose coefficients are rational functions of j_{1}, j_{2}, j_{3}.

A genus 2 curve with (2,2)-split Jacobian admits the equation y^{2} = x^{6} +ax^{4} +bx^{2} +1; its Igusa invariants are rational functions J_{1}(a, b), J_{2}(a, b), J_{3}(a, b). The underlying elliptic curves are isomorphic to the curves y^{2} = x^{3} + ax^{2} + bx + 1; their j-invariant is a rational function J(a, b).

Let F be the system {j − J(a, b), j_{i} − J_{i}(a, b) (i ≤ 3)} in ℚ[j_{1}, j_{2}, j_{3}, j, a, b] and take j_{1}, j_{2} for parameters: we work in ℚ(j_{1}, j_{2})[j_{3}, j, a, b] modulo the ideal generated by F after canceling denominators. This ideal is prime of dimension zero, so its solutions are represented by a triangular set in ℚ(j_{1}, j_{2})[j_{3}, j, a, b]. The first polynomial T_{1} ∈ ℚ(j_{1}, j_{2})[j_{3}] is the relation T mentioned above. The second polynomial T_{2} ∈ ℚ(j_{1}, j_{2})[j_{3}, j] gives j in terms of j_{1}, j_{2}, j_{3} when the denominators of its coefficients do not vanish.

We use the algorithm of Section 3.4. T_{1} is computed in 22 sec., and T_{1}, T_{2} in 140 sec. As a comparison, using the algorithm of [22], a representation by primitive element requires more than 400 sec. — see [23, Ch. 16, 20, 25] for details. This illustrates the interest of our “triangular” approach, when only a partial information is wanted.

4.2 Modular equations

In [8, 23], modular equations in high genus are defined. For a hyperelliptic curve C, and a prime ℓ, we study the ℓ-torsion divisors in the Jacobian of C: over a finite field, this enables to compute the cardinality of the Jacobian, a question of primary importance for hyperelliptic cryptosystems [8].

The ℓ-torsion divisors form a finite group G_{ℓ}, and are solutions of an algebraic system, in suitable coordinates. We define t_{ℓ} as a well-chosen function defined on G_{ℓ}, and the modular equation is the minimal polynomial Ξ_{ℓ} of t_{ℓ} in G_{ℓ}. It behaves like a revolvent: in [8], it is shown how to use its factorization patterns for cardinality determination.

Computing Ξ_{ℓ} for a generic curve is done following Section 3.5. We treated the 3-torsion in genus 2; the corresponding system has 3 equations in 3 unknowns X_{1}, X_{2}, X_{3} and 3 parameters P_{1}, P_{2}, P_{3} which parameterize curves of genus 2. The output Ξ_{3} ∈ ℚ(P_{1}, P_{2}, P_{3})[T] is computed within 4.5 h.; for comparison, it takes more than 20 h. to compute a representation by primitive element. Our result is used within Magma’s hyperelliptic curves package CrvHyp.

5. REFERENCES

[1] http://www.maths.usyd.edu.au:8000/u/magma/.

[2] http://www.medicis.polytechnique.fr/.

[3] P. Aubry. Ensembles triangulaires de polynômes et résolution de systèmes algébriques. Implantation en Axiom. PhD thesis, Université Paris VI, 1999.

[4] P. Aubry, D. Lazard, and M. Moreno Maza. On the theories of triangular sets. J. Symb. Comp., 28(1,2):45–124, 1999.

[5] F. Boulier, D. Lazard, F. Ollivier, and M. Petitot. Representation for the radical of a finitely generated differential ideal. In Proceedings ISSAC ’95, pages 158–166. ACM Press, 1995.

[6] S. Dellière. Triangularisation de systèmes constructibles — Application à l’évaluation dynamique. PhD thesis, Université de Limoges, 1999.

[7] G. Gallo and B. Mishra. Efficient algorithms and bounds for Wu-Ritt characteristic sets. In Proceedings MEGA ’90. Birkhäuser, 1990.

[8] P. Gaudry. Algorithmique des courbes hyperelliptiques et applications à la cryptologie. PhD thesis, École polytechnique, 2000.

[9] P. Gaudry and É. Schost. On the invariants of the quotients of the Jacobian of a curve of genus 2. In Proceedings AAECC 14, LNCS, 2001.

[10] M. Giusti, K. Hägele, J. Heintz, J. E. Morais, J. L. Montaña, and L. M. Pardo. Lower bounds for Diophantine approximation. Number 117,118 in J. of Pure and App. Algebra, pages 277–317, 1997.

[11] M. Giusti, J. Heintz, J. E. Morais, J. Morgenstern, and L. M. Pardo. Straight-line programs in geometric elimination theory. J. of Pure and App. Algebra, 124:101–146, 1998.

[12] M. Giusti, J. Heintz, J. E. Morais, and L. M. Pardo. When polynomial equation systems can be solved fast ? In Proceedings AAECC 11, LNCS, 1995.

[13] M. Giusti, G. Lecerf, and B. Salvy. A Gröbner free alternative for polynomial system solving. J. Complexity, 17(1):154–211, 2001.

[14] J. Heintz. Definability and fast quantifier elimination in algebraically closed fields. Theor. Comput. Sci., 24(3):239–277, 1983.

[15] J. Heintz, T. Krick, S. Puddu, J. Sabia, and A. Waissbein. Deformation techniques for efficient polynomial equation solving. J. Complexity, 16:70–109, 2000.

[16] M. Kalkbrener. Three contributions to elimination theory. PhD thesis, Kepler University, Linz, 1991.

[17] T. Krick, J. Sabia, and P. Solernó. On intrinsic bounds in the Nullstellensatz. AAECC Journal, 8:125–134, 1997.

[18] D. Lazard. Solving zero-dimensional algebraic systems. J. Symb. Comp., 13:117–133, 1992.

[19] M. Moreno Maza. Calculs de pgcd au-dessus des tours d’extensions simples et résolution des systèmes d’équations algébriques. PhD thesis, Université Paris VI, 1997.

[20] S. Morrison. The differential ideal [P] : M^{∞}. J. Symb Comp., 28:631–656, 1999.

[21] J. Sabia and P. Solernó. Bounds for traces in complete intersections and degrees in the Nullstellensatz. AAECC Journal, 6:353–376, 1996.

[22] É. Schost. Computing parametric geometric resolutions. Preprint École polytechnique, 2000.

[23] É. Schost. Sur la résolution des systèmes polynomiaux à paramètres. PhD thesis, École polytechnique, 2000.

[24] A. Szanto. Computation with polynomial systems. PhD thesis, Cornell University, 1999.

[25] J. von zur Gathen and J. Gerhard. Modern computer algebra. Cambridge University Press, 1999.