Search

Polynomials are very used in applied mathematics. Polynomial models provide an analytic framework for mechanics, physics, economy or financial modeling. They play an important role in a growing range of applications. For a real polynomial in one variable, one can consider on the one side the signs of its coefficients and on the other the signs of its possible real roots. The Descartes’ rule of signs imposes restrictions on the number of its positive roots expressed via the number of sign changes in its sequence of coefficients. This allows to deduce restrictions on the number of negative roots as well. A sign pattern (SP) of length d + 1 is a finite sequence of ”+” and/or ”−” signs. For the polynomial P := x^d + a_(d−1)x^(d−1) + ··· + a0, (aj ∈ R∗) we say that the sequence (1, a_(d−1), . . ., a0) defines the SP σ if σ = (+, sgn(a_(d−1)), . . ., sgn(a0)). As we consider only monic polynomials, the first sign of the SP is a ”+”. Denote by c and p the numbers of sign changes and sign preservations in the sequence (1, ad−1, . . ., a0) and by pos and neg the numbers of positive and negative roots of P counted with multiplicity. According to Descartes’ rule of signs, one has pos ≤ c and, applying this rule to the polynomial P (−x) one has neg ≤ p. Fourier’s observation is tantamount to saying that: c−pos ∈ 2Z and p−neg ∈ 2Z. We say that (pos, neg) is an admissible pair (AP) for σ if Descartes’ rule is satisfied (pos is the number of positive roots and neg the number of negative roots). A given couple (SP, AP) is realizable if there exists a monic polynomial whose sequence of coefficients defines the SP σ and which has exactly pos positive and exactly neg negative roots, all of them distinct. Question 1. For a given degree d, what are the non-realizable couples (SP,AP) ? We explore this question and find some sufficient conditions for the (non)existence of degree d real polynomials with two sign changes in the SP. For d ≤ 10 and for SPs with two sign changes, we give the exhaustive answer to Question 1. Up to degree 8, for all the non-realizable cases, one of the numbers pos or neg is 0. The next result presented in this thesis is that for d = 9, there is a non- realizable couple (SP, AP) in which both components of the AP are nonzero (and this is the only couple in degree 9). We formulate a third problem when a polynomial and its derivatives of all orders are considered. In this case we have one more constraint due to Rolle’s theorem. A list of APs of the polynomial P and its derivatives compatible with Descartes’ rule and Rolle’s theorem is called SAP (sequence of admissible pairs). In this part, one has explained the realizability of all possible SAPs in degree up to 5. The fourth result of this thesis concerns the explanation of the non-realizability of certain couples (SP, AP) using pictures showing the discriminant set. We explain the non-existence of the only non-realizable case for d = 5 and the existence of all other cases by means of pictures showing the discriminant set of the family of polynomials x^5 + x^4 + ax^3 + bx^2 + cx + d together with the coordinate axes.; Les polynômes sont très utilisés en mathématiques appliquées. Les modèles utilisant des polynômes fournissent un cadre analytique pour la modélisation mécanique, physique, économique ou financière. Pour un polynôme réel à une variable, nous considérons d’un côté les signes de ses coefficients et de l’autre les signes de ses racines réelles. La règle de Descartes impose des contraintes sur le nombre de racines strictement positives exprimées en termes du nombre de changements de signe dans la suite des coefficients du polynôme. Cela permet de déduire des restrictions sur le nombre de racines négatives. Une suite de signe (SS) de longueur d + 1 est une séquence finie de signes ”+” et/ou ”−”. Pour le polynôme P := x^d + a_(d−1)x^(d−1) + · · · + a0, (aj ∈ R∗) nous disons que la séquence (1, a_(d−1)), . . ., a_0) définit la SS σ si σ = (+, sgn (ad−1), . . ., sgn (a0)). Comme nous ne considérons que les polynômes moniques, le premier signe de la SS est un ”+”. Soit c (respectivement p) le nombre de changements (respectivement préservations) de signe dans la séquence (1, a_(d−1), . . ., a0) et soit pos (respectivement neg) le nombre de racines positives (respectivement négatives) de P compté avec multiplicité. D’aprés la règle de Descartes on a pos ≤ c et, en appliquant cette règle à P (−x), neg ≤ p. Une observation faite par Fourier dit que: c − pos ∈ 2Z et p − neg ∈ 2Z. On dit que (pos, neg) est une paire admissible (PA) pour σ si la règle de Descartes est satisfaite (pos est le nombre de racines positives et neg le nombre de racines négatives). Un couple (SS, PA) est dit réalisable s’il existe un polynôme monique dont la séquence de coefficients définit la SS σ et qui a exactement pos racines positives et neg racines négatives, toutes distinctes. Pour un degré donné d, nous recherchons les couples (SS, PA) non réalisables. Le premier résultat de notre travail donne des conditions suffisantes pour l’existence ou la non-existence de polynômes réels de degré d avec deux changements de signe dans la SS. Pour d ≤ 10 et pour les SS avec deux changements de signe, nous donnons la réponse exhaustive à la question. Jusqu’en degré 8, pour tous les cas non réalisables, l’un des nombres pos ou neg est 0. Le deuxième résultat présenté dans cette these, dit que pour d = 9, il existe un couple non réalisable (SS, PA) dans lequel les deux composantes de la PA sont non nulles (et c’est le seul couple en degré 9). Le troisième résultat porte sur un polynôme et ses dérivées de tous ordres. Dans ce cas, nous avons une contrainte supplémentaire qui est celle du théorème de Rolle. Une liste de PAs du polynôme P et de ses dérivées compatibles avec la règle de Descartes et le théorème de Rolle, est appelée séquence de paires admissibles (SPA). Dans cette partie, nous avons expliqué la (non) réalisabilité de toutes les SPA possibles en degré ≤ 5. Le quatrième résultat de cette thèse concerne l’explication de la non-réalisabilité à l’aide d’images montrant le discriminant. Nous expliquons la non-existence du seul cas non réalisable pour d = 5 et l’existence de tous les autres cas au moyen d’images montrant le discriminant de la famille des polynômes x^5 + x^4 + ax^3 + bx^2 + cx + d.

Polynomials are very used in applied mathematics. Polynomial models provide an analytic framework for mechanics, physics, economy or financial modeling. They play an important role in a growing range of applications. For a real polynomial in one variable, one can consider on the one side the signs of its coefficients and on the other the signs of its possible real roots. The Descartes’ rule of signs imposes restrictions on the number of its positive roots expressed via the number of sign changes in its sequence of coefficients. This allows to deduce restrictions on the number of negative roots as well. A sign pattern (SP) of length d + 1 is a finite sequence of ”+” and/or ”−” signs. For the polynomial P := x^d + a_(d−1)x^(d−1) + ··· + a0, (aj ∈ R∗) we say that the sequence (1, a_(d−1), . . ., a0) defines the SP σ if σ = (+, sgn(a_(d−1)), . . ., sgn(a0)). As we consider only monic polynomials, the first sign of the SP is a ”+”. Denote by c and p the numbers of sign changes and sign preservations in the sequence (1, ad−1, . . ., a0) and by pos and neg the numbers of positive and negative roots of P counted with multiplicity. According to Descartes’ rule of signs, one has pos ≤ c and, applying this rule to the polynomial P (−x) one has neg ≤ p. Fourier’s observation is tantamount to saying that: c−pos ∈ 2Z and p−neg ∈ 2Z. We say that (pos, neg) is an admissible pair (AP) for σ if Descartes’ rule is satisfied (pos is the number of positive roots and neg the number of negative roots). A given couple (SP, AP) is realizable if there exists a monic polynomial whose sequence of coefficients defines the SP σ and which has exactly pos positive and exactly neg negative roots, all of them distinct. Question 1. For a given degree d, what are the non-realizable couples (SP,AP) ? We explore this question and find some sufficient conditions for the (non)existence of degree d real polynomials with two sign changes in the SP. For d ≤ 10 and for SPs with two sign changes, we give the exhaustive answer to Question 1. Up to degree 8, for all the non-realizable cases, one of the numbers pos or neg is 0. The next result presented in this thesis is that for d = 9, there is a non- realizable couple (SP, AP) in which both components of the AP are nonzero (and this is the only couple in degree 9). We formulate a third problem when a polynomial and its derivatives of all orders are considered. In this case we have one more constraint due to Rolle’s theorem. A list of APs of the polynomial P and its derivatives compatible with Descartes’ rule and Rolle’s theorem is called SAP (sequence of admissible pairs). In this part, one has explained the realizability of all possible SAPs in degree up to 5. The fourth result of this thesis concerns the explanation of the non-realizability of certain couples (SP, AP) using pictures showing the discriminant set. We explain the non-existence of the only non-realizable case for d = 5 and the existence of all other cases by means of pictures showing the discriminant set of the family of polynomials x^5 + x^4 + ax^3 + bx^2 + cx + d together with the coordinate axes.; Les polynômes sont très utilisés en mathématiques appliquées. Les modèles utilisant des polynômes fournissent un cadre analytique pour la modélisation mécanique, physique, économique ou financière. Pour un polynôme réel à une variable, nous considérons d’un côté les signes de ses coefficients et de l’autre les signes de ses racines réelles. La règle de Descartes impose des contraintes sur le nombre de racines strictement positives exprimées en termes du nombre de changements de signe dans la suite des coefficients du polynôme. Cela permet de déduire des restrictions sur le nombre de racines négatives. Une suite de signe (SS) de longueur d + 1 est une séquence finie de signes ”+” et/ou ”−”. Pour le polynôme P := x^d + a_(d−1)x^(d−1) + · · · + a0, (aj ∈ R∗) nous disons que la séquence (1, a_(d−1)), . . ., a_0) définit la SS σ si σ = (+, sgn (ad−1), . . ., sgn (a0)). Comme nous ne considérons que les polynômes moniques, le premier signe de la SS est un ”+”. Soit c (respectivement p) le nombre de changements (respectivement préservations) de signe dans la séquence (1, a_(d−1), . . ., a0) et soit pos (respectivement neg) le nombre de racines positives (respectivement négatives) de P compté avec multiplicité. D’aprés la règle de Descartes on a pos ≤ c et, en appliquant cette règle à P (−x), neg ≤ p. Une observation faite par Fourier dit que: c − pos ∈ 2Z et p − neg ∈ 2Z. On dit que (pos, neg) est une paire admissible (PA) pour σ si la règle de Descartes est satisfaite (pos est le nombre de racines positives et neg le nombre de racines négatives). Un couple (SS, PA) est dit réalisable s’il existe un polynôme monique dont la séquence de coefficients définit la SS σ et qui a exactement pos racines positives et neg racines négatives, toutes distinctes. Pour un degré donné d, nous recherchons les couples (SS, PA) non réalisables. Le premier résultat de notre travail donne des conditions suffisantes pour l’existence ou la non-existence de polynômes réels de degré d avec deux changements de signe dans la SS. Pour d ≤ 10 et pour les SS avec deux changements de signe, nous donnons la réponse exhaustive à la question. Jusqu’en degré 8, pour tous les cas non réalisables, l’un des nombres pos ou neg est 0. Le deuxième résultat présenté dans cette these, dit que pour d = 9, il existe un couple non réalisable (SS, PA) dans lequel les deux composantes de la PA sont non nulles (et c’est le seul couple en degré 9). Le troisième résultat porte sur un polynôme et ses dérivées de tous ordres. Dans ce cas, nous avons une contrainte supplémentaire qui est celle du théorème de Rolle. Une liste de PAs du polynôme P et de ses dérivées compatibles avec la règle de Descartes et le théorème de Rolle, est appelée séquence de paires admissibles (SPA). Dans cette partie, nous avons expliqué la (non) réalisabilité de toutes les SPA possibles en degré ≤ 5. Le quatrième résultat de cette thèse concerne l’explication de la non-réalisabilité à l’aide d’images montrant le discriminant. Nous expliquons la non-existence du seul cas non réalisable pour d = 5 et l’existence de tous les autres cas au moyen d’images montrant le discriminant de la famille des polynômes x^5 + x^4 + ax^3 + bx^2 + cx + d.

Since 1960 and the result of Karatsuba, we know that the complexity of the multiplication (of integers or polynomials) is sub-quadratic: given a ring R, the product in R[X] of polynomials a_0 + a_1 X and b_0 + b_1 X, for any a_0, a_1, b_0 and b_1 in R, can be computed with three and not four multiplications over R: (a_0 + a_1X)(b_0 + b_1X) = m_0 + (m_2 - m_0 - m_1)X + m_1X^2, with the three multiplications m_0 = a_0b_0, m_1 = a_1b_1 et m_2 = (a_0 + a_1)(b_0 + b_1). In the same manner, Strassen's algorithm allows one to multiply two matrices 2nx2n with only seven products of matrices nxn. The two previous examples fall in the category of bilinear maps: these are functions of the form Phi : K^m x K^n -> K^l, given a field K, linear in each variable. Among the most classical bilinear maps, we have the multiplication of polynomials, matrices, or even elements of algebraic extension of finite fields. Given a bilinear map Phi, computing the minimal number of multiplications necessary to the evaluation of this map is a NP-hard problem. The purpose of this thesis is to propose algorithms minimizing this number of multiplications. Two angles of attack have been studied. The first aspect of this thesis is to study the problem of the computation of the bilinear complexity under the angle of the reformulation of this problem in terms of research of matrix subspaces of a given rank. This work led to an algorithm taking into account intrinsic properties of the considered products such as matrix or polynomial products over finite fields. This algorithm allows one to find all the possible decompositions, over F_2, for the product of polynomials modulo X^5 and the product of matrices 3x2 by 2x3. Another aspect of this thesis was the development of fast asymptotic methods for the integer multiplication. There is a particular family of algorithms that has been proposed after an article by Fürer published in 2007. This article proposed a first algorithm, relying on fast Fourier transform (FFT), allowing one to multiply n-bit integers in O(n log n 2^{O(log^* n)}), where log^* is the iterated logarithm function. In this thesis, an algorithm, relying on a number theoretical conjecture, has been proposed, involving the use of FFT and generalized Fermat primes. With a careful complexity analysis of this algorithm, we obtain a complexity in O(nlog n 4^{log^* n}); Depuis 1960 et le résultat fondateur de Karatsuba, on sait que la complexité de la multiplication (d’entiers ou de polynômes) est sous-quadratique : étant donné un anneau R quelconque, le produit sur R[X] des polynômes a_0 + a_1 X et b_0 + b_1 X, pour tous a_0, a_1, b_0 et b_1 dans R, peut être calculé en seulement trois et non pas quatre multiplications sur R : (a_0 + a_1 X)(b_0 + b_1 X) = m_0 + (m_2 - m_0 - m_1)X + m_1 X^2, avec les trois produits m_0 = a_0b_0, m_1 = a_1b_1 et m_2 = (a_0 + a_1)(b_0 + b_1). De la même manière, l’algorithme de Strassen permet de multiplier deux matrices 2nx2n en seulement sept produits de matrices nxn. Les deux exemples précédents tombent dans la catégorie des applications bilinéaires : des fonctions de la forme Phi : K^m x K^n -> K^l, pour un corps donné K, linéaires en chacune des deux variables. Parmi les applications bilinéaires les plus classiques, on trouve ainsi la multiplication de polynômes, de matrices, ou encore d’éléments d’extensions algébriques de corps finis. Étant donnée une application bilinéaire Phi, calculer le nombre minimal de multiplications nécessaires au calcul de cette application est un problème NP-difficile. L'objectif de cette thèse est de proposer des algorithmes minimisant ce nombre de multiplications. Deux angles d'attaques ont été suivis. Un premier aspect de cette thèse est l'étude du problème du calcul de la complexité bilinéaire sous l'angle de la reformulation de ce problème en termes de recherche de sous-espaces vectoriels de matrices de rang donné. Ce travail a donné lieu à un algorithme tenant compte de propriétés intrinsèques aux produits considérés tels que les produits matriciels ou polynomiaux sur des corps finis. Cet algorithme a permis de trouver toutes les décompositions possibles, sur F_2, pour le produit de polynômes modulo X^5 et le produit de matrices 3x2 par 2x3. Un autre aspect de ma thèse est celui du développement d’algorithmes asymptotiquement rapides pour la multiplication entière. Une famille particulière d'algorithmes récents ont été proposés suite à un article de Fürer publié en 2007, qui proposait un premier algorithme, reposant sur la transformée de Fourier rapide (FFT) permettant de multiplier des entiers de n bits en O(n log n 2^{O(log^* n)}), où log^* est la fonction logarithme itéré. Dans cette thèse, un algorithme dont la complexité dépend d'une conjecture de théorie des nombres est proposé, reposant sur la FFT et l'utilisation de premiers généralisés de Fermat. Une analyse de complexité permet d'obtenir une estimation en O(n log n 4^{log^* n})

The contribution of the thesis is threefold. The first Problem is computing the discriminant, when the system’s dimension varies. Thus solving polynomial equations and systems by exploiting the structure and sparseness of them have been studied. Specifically, closed formulas for the degree of the sparse (mixed) discriminant and the sparse resultant of polynomial equations have been studied, as well as relationships between them. Closed formulas when one of the polynomials factors in the context of the theory of sparse elimination using the Newton polytope have been proposed. The purpose is to facilitate the computation of the sparse (or mixed) discriminant of a well-constrained polynomial system and to generalize the formula that connects the mixed discriminant with the sparse resultant. Further, we are given a system of n ⩾ 2 homogeneous polynomials in n variables which is equivariant with respect to the symmetric group of n symbols. We then prove that its resultant can be decomposed into a product of several resultants that are given in terms of some divided differences. As an application, we obtain a decomposition formula for the discriminant.The second Problem is computing the Minkowski decomposition of a polytope and the third one was the problem of Multidimensional Subset Sum (kD-SS) in arbitrary dimension. We present an algorithm for computing all Minkowski Decompositions (MinkDecomp) of a given convex, integral d-dimensional polytope. Further, we consider the approximation of two NP-hard problems: Minkowski Decomposition (MinkDecomp) of lattice polygons in the plane and the closely related problem of Multidimensional Subset Sum (kD-SS) in arbitrary dimension. In kD-SS, a multiset S of k-dimensional vectors is given, along with a target vector t, and one must decide whether there exists a subset of S that sums up to t. We prove, through a gap-preserving reduction from Set Cover that, for general dimension k, the corresponding optimization problem kD-SS-opt is not in APX, although the classic 1D-SS-opt has a PTAS. On the positive side, we present an approximation algorithm for 2D-SS-opt, where ε > 0 bounds the additive error in terms of some property of the input. By a reduction of the optimization version of MinkDecomp to 2D-SS-opt we approximate the former.; La contribution de la thèse est triple. Le premier problème est le calcul du discriminant, lorsque la dimension du système varie. Ainsi, la résolution d'équations et de systèmes polynomiaux en exploitant la structure de ceux-ci a été étudiée. Des formules fermées pour le degré du discriminant clairsemé (mixte) et la résultante des équations polynomiales ont été étudiées, ainsi que des relations entre eux, en utilisant le polytope de Newton. Le but est de faciliter le calcul du discriminant creuse (ou mixte) d'un système polynomial bien contraint et de généraliser la formule qui relie le discriminant mixte au résultant creux. De plus, etant donne' un système de n ⩾ 2 polynômes homogènes en n variables qui est équivariant par rapport au groupe symétrique de n symboles, nous montrons que son résultant peut être décomposé en un produit de plusieurs résultants en termes de différences divisées. En tant qu'application, nous obtenons une formule de décomposition pour le discriminant.Le deuxième problème est le calcul de la décomposition de Minkowski d'un polytope et le troisième était le problème de la somme des sous-ensembles multidimensionnels (kD-SubsetSum) dans une dimension arbitraire. Nous présentons un algorithme pour calculer toutes les décompositions de Minkowski (MinkDecomp) d'un polytope d-dimensionnel convexe et entier. Nous considérons l'approximation de deux problèmes NP-hard: la décomposition de Minkowski (MinkDecomp) des polygones dans le plan et le problème de la somme des sous-ensembles multidimensionnels (kD-SS) dans une dimension arbitraire. En kD-SS, un multiset S de vecteurs k-dimensionnels est donné, avec un vecteur cible t, et il faut décider s'il existe un sous-ensemble de S qui somme jusqu'à t. Nous prouvons, à travers une réduction gap-preserving de Set Cover, que le problème d'optimisation correspondant kD-SS-opt n'est pas dans APX, bien que le classique 1D-SS-opt ait un PTAS. Du côté positif, nous présentons un algorithme d'approximation pour 2D-SS-opt, où ε> 0 limite l'erreur additive.

The contribution of the thesis is threefold. The first Problem is computing the discriminant, when the system’s dimension varies. Thus solving polynomial equations and systems by exploiting the structure and sparseness of them have been studied. Specifically, closed formulas for the degree of the sparse (mixed) discriminant and the sparse resultant of polynomial equations have been studied, as well as relationships between them. Closed formulas when one of the polynomials factors in the context of the theory of sparse elimination using the Newton polytope have been proposed. The purpose is to facilitate the computation of the sparse (or mixed) discriminant of a well-constrained polynomial system and to generalize the formula that connects the mixed discriminant with the sparse resultant. Further, we are given a system of n ⩾ 2 homogeneous polynomials in n variables which is equivariant with respect to the symmetric group of n symbols. We then prove that its resultant can be decomposed into a product of several resultants that are given in terms of some divided differences. As an application, we obtain a decomposition formula for the discriminant.The second Problem is computing the Minkowski decomposition of a polytope and the third one was the problem of Multidimensional Subset Sum (kD-SS) in arbitrary dimension. We present an algorithm for computing all Minkowski Decompositions (MinkDecomp) of a given convex, integral d-dimensional polytope. Further, we consider the approximation of two NP-hard problems: Minkowski Decomposition (MinkDecomp) of lattice polygons in the plane and the closely related problem of Multidimensional Subset Sum (kD-SS) in arbitrary dimension. In kD-SS, a multiset S of k-dimensional vectors is given, along with a target vector t, and one must decide whether there exists a subset of S that sums up to t. We prove, through a gap-preserving reduction from Set Cover that, for general dimension k, the corresponding optimization problem kD-SS-opt is not in APX, although the classic 1D-SS-opt has a PTAS. On the positive side, we present an approximation algorithm for 2D-SS-opt, where ε > 0 bounds the additive error in terms of some property of the input. By a reduction of the optimization version of MinkDecomp to 2D-SS-opt we approximate the former.; La contribution de la thèse est triple. Le premier problème est le calcul du discriminant, lorsque la dimension du système varie. Ainsi, la résolution d'équations et de systèmes polynomiaux en exploitant la structure de ceux-ci a été étudiée. Des formules fermées pour le degré du discriminant clairsemé (mixte) et la résultante des équations polynomiales ont été étudiées, ainsi que des relations entre eux, en utilisant le polytope de Newton. Le but est de faciliter le calcul du discriminant creuse (ou mixte) d'un système polynomial bien contraint et de généraliser la formule qui relie le discriminant mixte au résultant creux. De plus, etant donne' un système de n ⩾ 2 polynômes homogènes en n variables qui est équivariant par rapport au groupe symétrique de n symboles, nous montrons que son résultant peut être décomposé en un produit de plusieurs résultants en termes de différences divisées. En tant qu'application, nous obtenons une formule de décomposition pour le discriminant.Le deuxième problème est le calcul de la décomposition de Minkowski d'un polytope et le troisième était le problème de la somme des sous-ensembles multidimensionnels (kD-SubsetSum) dans une dimension arbitraire. Nous présentons un algorithme pour calculer toutes les décompositions de Minkowski (MinkDecomp) d'un polytope d-dimensionnel convexe et entier. Nous considérons l'approximation de deux problèmes NP-hard: la décomposition de Minkowski (MinkDecomp) des polygones dans le plan et le problème de la somme des sous-ensembles multidimensionnels (kD-SS) dans une dimension arbitraire. En kD-SS, un multiset S de vecteurs k-dimensionnels est donné, avec un vecteur cible t, et il faut décider s'il existe un sous-ensemble de S qui somme jusqu'à t. Nous prouvons, à travers une réduction gap-preserving de Set Cover, que le problème d'optimisation correspondant kD-SS-opt n'est pas dans APX, bien que le classique 1D-SS-opt ait un PTAS. Du côté positif, nous présentons un algorithme d'approximation pour 2D-SS-opt, où ε> 0 limite l'erreur additive.

Multivariate polynomial systems arise naturally in many scientific fields. These systems coming from applications often carry a specific algebraic structure.A classical method for solving polynomial systems isbased on the computation of a Gr\"obner basis of the ideal associatedto the system.This thesis presents new tools for solving suchstructured systems, where the structure is induced by the action of a particular group or a monomial structure, which include multihomogeneous or quasihomogeneous systems.On the one hand, this thesis proposes new algorithmsusing these algebraic structures to improve the efficiency of solving suchsystems (invariant under the action of a group or having a support in a particular set of monomials). These techniques allow to solve a problem arising in physics for instances out of reach until now.On the other hand, these tools improve the complexity bounds for solving several families of structured polynomial systems (systems globally invariant under the action of an abelian group or with their support in the same polytope). This allows in particular to extend known results on bilinear systems to general mutlihomogeneous systems.; Les systèmes polynomiaux à plusieurs variables apparaissent naturellement dans de nombreux domaines scientifiques. Ces systèmes issus d'applications possèdent une structure algébrique spécifique. Une méthode classique pour résoudre des systèmes polynomiaux repose sur le calcul d'une base de Gröbner de l'idéal associé au système. Cette thèse présente de nouveaux outils pour la résolution de tels systèmes structurés, lorsque la structure est induite par l'action d'un groupe ou une structure monomiale particulière, qui englobent les systèmes multi-homogènes ou quasi-homogènes. D'une part, cette thèse propose de nouveaux algorithmes qui exploitent ces structures algébriques pour améliorer l'efficacité de la résolution de systèmes (systèmes invariant sous l'action d'un groupe ou à support dans un ensemble de monômes particuliers). Ces techniques permettent notamment de résoudre un problème issu de la physique pour des instances hors de portée jusqu'à présent. D'autre part, ces outils permettent d'améliorer les bornes de complexité de résolution de plusieurs familles de systèmes polynomiaux structurés (systèmes globalement invariant sous l'action d'un groupe abélien, individuellement invariant sous l'action d'un groupe quelconque, ou ayant leur support dans un même polytope). Ceci permet en particulier d'étendre des résultats connus sur les systèmes bilinéaires aux systèmes mutli-homogènes généraux.

In this thesis we study at length the discrete logarithm problem in finite fields. In the first part, we focus on the notion of smoothness and on ECM, the fastest known smoothness test. We present an improvement to the algorithm by analyzing the Galois properties of the division polynomials. We continue by an application of ECM in the last stage of the number field sieve (NFS). In the second part, we present NFS and its related algorithm on function fields (FFS). We show how to speed up the computation of discrete logarithms in all the prime finite fields of a given bit-size by using a pre-computation. We focus later on the polynomial selection stage of FFS and show how to compare arbitrary polynomials with a unique function. We conclude the second part with an algorithm issued from the recent improvements for discrete logarithm. The key fact was to create a descent procedure which has a quasi-polynomial number of nodes, each requiring a polynomial time. This leads to a quasi-polynomial algorithm for finite fields of small characteristic, Dans cette thèse nous examinons en détail le problème du logarithme discret dans les corps finis. Dans la première partie, nous nous intéressons à la notion de friabilité et à l'algorithme ECM, le plus rapide test de friabilité connu. Nous présentons une amélioration de l'algorithme en analysant les propriétés galoisiennes des polynômes de division. Nous continuons la présentation par une application d'ECM dans la dernière étape du crible algébrique (NFS). Dans la deuxième partie, nous présentons NFS et son algorithme correspondant utilisant les corps de fonctions (FFS). Parmi les améliorations examinées, nous montrons qu'on peut accélérer le calcul de logarithme discret au prix d'un pré-calcul commun pour une plage de premiers ayant le même nombre de bits. Nous nous concentrons ensuite sur la phase de sélection polynomiale de FFS et nous montrons comment comparer des polynômes quelconques à l'aide d'une unique fonction. Nous concluons la deuxième partie avec un algorithme issu des récentes améliorations du calcul de logarithme discret. Le fait marquant est la création d'une procédure de descente qui a un nombre quasi-polynomial de noeuds, chacun exigeant un temps polynomial. Cela a conduit à un algorithme quasi-polynomial pour les corps finis de petite caractéristique

Contribution à un ouvrage.; International audience; The main purpose of this chapter is to show how to use algorithms and methodology provided by computer algebra to manipulate in a symbolic way the real solutions of an algebraic system of equations.