Le sujet de cette thèse est la conception et l'implantation d'algorithmes efficaces pour des opérations de base en calcul formel, ainsi que leurs applications à des domaines connexes, comme la théorie algorithmique des nombres et la cryptographie. Une première partie traite de l'algorithmique de base sur les polynômes à une variable. L'outil systématiquement mis en oeuvre est une version constructive du principe de transposition de Tellegen, qui permet d'obtenir de nouveaux algorithmes pour l'évaluation multipoint et l'interpolation (dans diverses bases polynomiales et pour diverses familles de points d'évaluation), ainsi qu'un théorème d'équivalence entre les complexités de ces deux problèmes. La deuxième partie est consacrée à l'algorithmique des nombres algébriques. Nous étudions d'abord certaines opérations élémentaires, comme la somme, le produit et leur généralisation, le produit diamant de Brawley et Carlitz. Leur calcul repose sur l'utilisation de l'opérateur de Newton formel et de la dualité algébrique, traduite algorithmiquement par l'emploi du principe de transposition et des méthodes de type pas de bébés / pas de géants. Ces méthodes sont ensuite généralisées au cadre des systèmes de polynômes de dimension zéro, pour le calcul de polynômes minimaux dans des algèbres quotient, ainsi que de paramétrisations rationnelles. Dans la troisième partie, nous étudions la question du calcul d'un terme d'une suite récurrente linéaire à coefficients polynomiaux. Comme application, nous obtenons des améliorations théoriques et pratiques des méthodes de comptage de points utilisées en cryptographie. Nous proposons ensuite une méthode de type évaluation-interpolation pour certaines opérations usuelles sur les opérateurs différentiels linéaires à coefficients polynomiaux.

Cette thèse s'intéresse au calcul de solutions globales de problèmes de commande optimale en boucle ouverte. La méthodologie générale se base sur l'approche par les moments, où un problème d'optimisation est relâché en un problème généralisé des moments, dont une hiérarchie de relaxations semi-définies peut être résolue numériquement. L'approche est tout d'abord appliquée aux problèmes impulsionnels linéaires à temps variant, en modélisant le contrôle par une mesure. Les conditions semi-définies qui en résultent permettent de s'affranchir complètement des difficultés liées à la discrétisation temporelle. Ensuite, en se basant sur le formalisme des mesures d'occupations, la méthode peut être étendue aux systèmes impulsionnels non-linéaires, et fournit une suite monotone de bornes inférieures au coût optimal. Enfin, les résultats précédents peuvent être transposés aux systèmes à commutation, en modélisant chaque mode par une mesure d'occupation associée. Ceci permet d'obtenir des gains substantiels en charge de calcul par rapport à l'approche classique où l'espace de contrôle est mesuré.

Depuis ces dix dernières années, les attaques sur le logarithme discret sur les courbes elliptiques (ECDLP) mettant en jeu la résolution de systèmes polynomiaux connaissent un large succès. C'est dans ce contexte que s'inscrit cette thèse dont les contributions sont doubles. D'une part, nous présentons de nouveaux outils de résolution de systèmes polynomiaux par bases de Gröbner. Nous montrons que la résolution de systèmes avec symétries est étroitement liée à la résolution de systèmes quasi-homogènes. Nous proposons ainsi de nouveaux résultats de complexité pour la résolution de tels systèmes. Nous nous intéressons également à l'étape bloquante de la résolution de systèmes : le changement d'ordre pour bases de Gröbner. La complexité classique de cette étape est cubique en le nombre de solutions et domine la complexité totale de la résolution. Nous proposons pour la première fois des algorithmes de changement d'ordre de complexité sous-cubique en le nombre de solutions. D'autre part, nous nous intéressons à l'attaque du logarithme discret sur les courbes elliptiques par calcul d'indice proposée par Gaudry. Nous mettons en évidence des familles de courbes elliptiques possédant des symétries particulières. Ces symétries impliquent un gain exponentiel sur la complexité de la résolution du ECDLP. Nous obtenons ainsi de nouveaux paramètres de sécurité pour certaines instances du ECDLP. Une des étapes principales de cette attaque nécessite le calcul de polynômes de sommation introduits par Semaev. Les symétries des courbes elliptiques binaires nous permettent d'élaborer un nouvel algorithme par évaluation-interpolation pour le calcul des polynômes de sommation. Munis de cet algorithme nous établissons un nouveau record pour le calcul de ces polynômes.

La complexité algorithmique est l'étude des ressources nécessaires — le temps, la mémoire, … — pour résoudre un problème de manière algorithmique. Dans ce cadre, la théorie de la complexité algébrique est l'étude de la complexité algorithmique de problèmes de nature algébrique, concernant des polynômes.Dans cette thèse, nous étudions différents aspects de la complexité algébrique. D'une part, nous nous intéressons à l'expressivité des déterminants de matrices comme représentations des polynômes dans le modèle de complexité de Valiant. Nous montrons que les matrices symétriques ont la même expressivité que les matrices quelconques dès que la caractéristique du corps est différente de deux, mais que ce n'est plus le cas en caractéristique deux. Nous construisons également la représentation la plus compacte connue du permanent par un déterminant. D'autre part, nous étudions la complexité algorithmique de problèmes algébriques. Nous montrons que la détection de racines dans un système de n polynômes homogènes à n variables est NP-difficile. En lien avec la question « VP = VNP ? », version algébrique de « P = NP ? », nous obtenons une borne inférieure pour le calcul du permanent d'une matrice par un circuit arithmétique, et nous exhibons des liens unissant ce problème et celui du test d'identité polynomiale. Enfin nous fournissons des algorithmes efficaces pour la factorisation des polynômes lacunaires à deux variables. / Computational complexity is the study of the resources — time, memory, …— needed to algorithmically solve a problem. Within these settings, algebraic complexity theory is the study of the computational complexity of problems of algebraic nature, concerning polynomials. In this thesis, we study several aspects of algebraic complexity. On the one hand, we are interested in the expressiveness of the determinants of matrices as representations of polynomials in Valiant's model of complexity. We show that symmetric matrices have the same expressiveness as the ordinary matrices as soon as the characteristic of the underlying field in different from two, but that this is not the case anymore in characteristic two. We also build the smallest known representation of the permanent by a determinant.On the other hand, we study the computational complexity of algebraic problems. We show that the detection of roots in a system of n homogeneous polynomials in n variables in NP-hard. In line with the “VP = VNP ?”question, which is the algebraic version of “P = NP?” we obtain a lower bound for the computation of the permanent of a matrix by an arithmetic circuit, and we point out the links between this problem and the polynomial identity testing problem. Finally, we give efficient algorithms for the factorization of lacunary bivariate polynomials.

La classe des systèmes non-linéaires dont la dynamique est définie par un champ de vecteurs polynomial est étudié. Des modèles polynomiaux peuvent représenter différents systèmes réels ou bien définir des approximations plus riches que des modèles linéaires pour des systèmes non-linéaires différentiables. Des techniques de programmation semi-définie développées récemment ont rendu possible l'étude de cette classe de systèmes avec des outils numériques. Le problème d'analyse en stabilité locale est résolu via des conditions basées sur la positivité de polynomes. Dans le cadre de la synthèse de lois de commande nous proposons un changement de variables linéaire pour traiter la synthèse de lois de commande non-linéaire qui garantissent la stabilité locale. Les ensembles définissant des estimations de la région d'attraction, définis par des courbes de niveau de la fonction de Lyapunov pour le système, sont également donnés par des fonctions polynomiales / We study the class of nonlinear dynamical systems which vector field is defined by polynomial functions. A large set of systems can be modeled using such class of functions. Tests for stability are formulated as semidefinite programming problems by considering positive polinomials to belong to the class of Sum of Squares polynomials. Polynomial control law gains are computed based on a linear change of coordinates and guarantee the local stability of the closed-loop system. Lyapunov theory is then applied in order to obtain estimates of the region of attraction for stable equilibrium points. Such estimates are given by level sets of polynomial positive functions

Cette thèse s’intéresse au calcul de solutions globales de problèmes de commande optimaleen boucle ouverte. La méthodologie générale se base sur l’approche par les moments, oùun problème d’optimisation est relâché en un problème généralisé des moments, dont unehiérarchie de relaxations semi-définies peut être résolue numériquement. L’approche esttout d’abord appliquée aux problèmes impulsionnels linéaires à temps variant, en modélisantle contrôle par une mesure. Les conditions semi-définies qui en résultent permettentde s’affranchir complètement des difficultés liées à la discrétisation temporelle. Ensuite, ense basant sur le formalisme des mesures d’occupations, la méthode peut être étendue auxsystèmes impulsionnels non-linéaires, et fournit une suite monotone de bornes inférieuresau coût optimal. Enfin, les résultats précédents peuvent être transposés aux systèmes àcommutation, en modélisant chaque mode par une mesure d’occupation associée. Ceci permetd’obtenir des gains substantiels en charge de calcul par rapport à l’approche classiqueoù l’espace de contrôle est mesuré / This thesis details a global method for optimal control of open-loop systems. This is doneby relaxing the control problem as a generalized moment problem, which can be solvednumerically by a hierarchy of semi-definite relaxations. The approach is first applied tothe impulsive control of linear time varying systems, by modeling the controls by a measure.The resulting semi-definite conditions circumvent time discretiziation and relateddifficulties. By the use of occupation measures, the method is then extended to a classof impulsive non-linear problems. This results in a monotone sequence of lower boundsto the original control problem. Finally, those results are transposed to switched system,by modeling each mode by a corresponding occupation measure. This allows for largecomputational gains with respect to the classical approach, where the control space ismeasured

Cette thèse porte sur la commande H∞ par loop-shaping pour les systèmes linéaires à temps invariant d'ordre faible avec ou sans retard et dépendant de paramètres inconnus. L'objectif est d'obtenir des correcteurs H∞ paramétriques, c'est-à-dire dépendant explicitement des paramètres inconnus, pour application à des viseurs gyrostabilisés.L'existence de ces paramètres inconnus ne permet plus l'utilisation des techniques numériques classiques pour la résolution du problème H∞ par loop-shaping. Nous avons alors développé une nouvelle méthodologie permettant de traiter les systèmes linéaires de dimension finie grâce à l'utilissation de techniques modernes de calcul formel dédiées à la résolution des systèmes polynomiaux (bases de Gröbner, variétés discriminantes, etc.).Une telle approche présente de multiples avantages: étude de sensibilités du critère H∞ par rapport aux paramètres, identification de valeurs de paramètres singulières ou remarquables, conception de correcteurs explicites optimaux/robustes, certification numérique des calculs, etc. De plus, nous montrons que cette approche peut s'étendre à une classe de systèmes à retard.Plus généralement, cette thèse s'appuie sur une étude symbolique des équations de Riccati algébriques. Les méthodologies génériques développées ici peuvent s'étendre à de nombreux problèmes de l'automatique, notamment la commande LQG, le filtrage de Kalman ou invariant. / This PhD thesis deals with the H∞ loop-shaping design for low order linear time invariant systems depending on unknown parameters. The objective of the PhD thesis is to obtain parametric H∞ controllers, i.e. controllers which depend explicitly on the unknown model parameters, and to apply them to the stabilization of gyrostabilized sights.Due to the unknown parameters, no numerical algorithm can solve the robust control problem. Using modern symbolic techniques dedicated to the solving of polynomial systems (Gröbner bases, discriminant varieties, etc.), we develop a new methodology to solve this problem for finite-dimensional linear systems.This approach shows several advantages : we can study the sensibilities of the H∞ criterion to the parameter variations, identify singular or remarquable values of the parameters, compute controllers which depend explicitly on the parameters, certify the numerical computations, etc. Furthermore, we show that this approach can be extended to a class of linear time-delay systems.More generally, this PhD thesis develops an algebraic approach for the study of algebraic Riccati equations. Thus, the methodology obtained can be extended to many different problems such as LQG control and Kalman or invariant filtering.