Le problème du logarithme discret est une brique fondamentale de nombreux protocoles de communication sécurisée. Son instantiation sur les courbes elliptiques a permis, grâce à la petite taille des opérandes considérées, le déploiement de primitives asymétriques efficaces sur des systèmes embarqués. De nos jours, les cryptosystèmes utilisant des courbes elliptiques, aussi appelées courbes de genre 1, sont déjà intensément utilisés: il est donc impératif de savoir estimer précisément la robustesse de ces systèmes. L'existence d'attaques mathématiques permettant de transférer un problème de logarithme discret elliptique dans un autre type de courbe algébrique, et la nouvelle compétitivité des courbes de genre 2 imposent de ne pas se restreindre à la seule compréhension du problème sur les courbes elliptiques.Dans cette optique, le sujet de cette thèse se concentre sur les attaques algébriques sur les courbes de genre supérieur à 1. Les algorithmes de type calcul d'indice sont en général préférés pour ce genre d'attaque. Ces algorithmes se déroulent en deux phases: la première, appelée phase de récolte, dispose de nombreuses modélisations algébriques dépendant de la courbe ciblée. Le problème sous-jacent revient à savoir décomposer efficacement des points dans la variété Jacobienne de la courbe en somme d'autres points.On propose dans un premier temps une approche par crible pour la phase de récolte, s'adaptant à tous les types de courbes de genre plus grand que 1, et qui est expérimentalement plus efficaces que les méthodes de l'état de l'art. Cette méthode a l'avantage de proposer une implémentation immédiate, et évite les problèmes usuels de gestion des relations obtenues.Ensuite, on se concentre les variantes de calcul d'indice appelées attaques par décomposition, et ciblant les courbes définies sur des extensions de corps. Dans cette situation, la phase de récolte est effectuée par résolution de nombreux systèmes polynomiaux multivariés. On propose une nouvelle approche de modélisation de ces systèmes, en généralisant la notion de polynômes de sommation elliptique à tout les types de courbes algébriques. Pour cela on fait appel à la théorie de l'élimination, tandis que l'aspect pratique est gérée par des méthodes de bases de Gröbner.Enfin, on fournit des algorithmes d'amélioration du processus de résolution des systèmes lorsque la caractéristique du corps de base est paire. Par le biais d'une présentation théorique générale et en utilisant des méthodes de bases de Gröbner, on propose une analyse fine de l'impact de ces améliorations sur la complexité de la résolution. Cette analyse fine, ainsi qu'une implémentation dédiée, nous permettent d'attaquer une courbe de genre 2 satisfaisant des bornes de sécurité réaliste en pratique. / The discrete logarithm problem is a fundamental brick for several protocols for secured communications. Its instantiation over elliptic curves allows the deployment of efficient asymmetric primitives in embedded systems, because of the small size of the parameters considered. Nowadays, elliptic curves cryptosystems are already widely used: it is therefore crucial to precisely understand the hardness of such systems. Because of the existence of mathematical attacks enabling the transfer from an elliptic curve discrete logarithm problem to another algebraic curve, and the upcoming competitivity of genus 2 curves, it is mandatory to study the problem not only for elliptic curves, but for the other curves as well.In this way, this thesis focuses on the algebraic attacks over curves with genus greater than 1. The index calculus family of algorithms is in general preferred for this kind of attacks. Those algorithms run in two phases: the first, called harvesting phase, can be modelled by different algebraic approaches, depending in the targetted curve. The underlying problem amounts to knowing how to decompose efficiently points in the Jacobian variety of the curve into sums of other points.First, we propose a sieving approach to the harvesting, that can be adated to any type of curves with genus greater than 1, and which turns to be experimentally more efficient than state-of-the-art's methods. Moreover, our method allows a close-to-immediate implementation, and avoid complications coming from relations management.Our second focus is on a variant of index calculus called decomposition attack, targetting curves defined over field extensions. In this situation, harvesting is done by solving numerous multivariate polynomial systems. We propose a new approach to this modelling by generalizing the notion of elliptic summation polynomias to any type of algebraic curves. This uses elimination theory, and the computational aspect is handled by Gröbner bases methods.Third, we give algorithms to improve the solving process of the systems arising from a decomposition attacks when the characteristic of the base field is even. By mean of a general theoretical presentation, and using Gröbner bases methods, we give a sharp analysis of the impact of such improvement on the complexity of the resolution process. This sharp analysis together with a dedicated implementation allows us to attack a genus 2 curve satisfying realistic security parameters.

Un système de solides peut être classé suivant trois états de mobilité: l’état non assemblé, l’état assemblé rigide et l’état assemblé mobile. L’étude se focalise sur les systèmes de solides sur-contraints en boucle fermée. Lors de l’étape de conception ou reconception, les dimensions d’un système de solides sur-contraints sont amenées à être modifiées, ce qui peut avoir pour conséquence la perte de son état de mobilité.L’approche présentée dans cette thèse a pour but de proposer une assistance au concepteur lors du redimensionnement, lui permettant de modifier ou conserver l’état de mobilité d’un système de solides. Le redimensionnement de systèmes de solides sur-contraints nécessite la connaissance de relations dépendant de leurs dimensions: les équations d’assemblage et les conditions de mobilité. Ces relations sont obtenues à l’aide d’un outil de résolution algébrique: les bases de Gröbner. La résolution algébrique est parfois coûteuse, voire impossible en un temps raisonnable, c’est ce qui justifie les méthodes décrites dans cette thèse.La solution proposée est composée de deux étapes principales. Tout d’abord, les représentations algébriques d’un système de solides fermé et mobile sont décrites. Les équations de fermeture d’un système de solides composé de plusieurs boucles sont obtenues en utilisant un paramétrage en coordonnées relatives. Les équations de mobilité sont elles générées à partir des équations de fermeture, à l’aide de méthodes directes ou incrémentales. Ensuite, afin de faciliter la génération des équations d’assemblage et de mobilité, une analyse algébrique reposant sur des outils d’analyse numérique est définie. L’état de mobilité du système de solides à redimensionner est déterminé à partir d’un ensemble de valeurs des paramètres le décrivant. Si le concepteur souhaite modifier l’état de mobilité du système de solides, de nouvelles valeurs sont alors générées. Lorsque l’état de mobilité souhaité est obtenu, il est possible de varier les dimensions tout en conservant cet état. Pour cela, certaines dimensions sont spécialisées afin de faciliter la génération des équations d’assemblage et des conditions de mobilité. Si les paramètres choisis sont liés ou trop nombreux, l’analyse mène inéluctablement à une absence de solutions. Des stratégies de partitionnement pour pallier ces problèmes sont aussi proposées. Enfin, les outils développés dans le logiciel Maple® afin d’illustrer les différents concepts proposés sont présentés, et un outil interactif permettant au concepteur de naviguer sur les équations de fermeture, équations d’assemblage et les conditions de mobilité obtenues après spécialisation, est proposé. / An assembly can be partitioned into three mobility states: the impossible state, the rigid state and the mobile state. The study focuses in over-constrained closed-loop assemblies. During the process of design or re-design, the dimensions of the assembly can vary and this can lead to the loss of its mobility state.The method presented in this thesis aims at helping the designer to resize an assembly. There exist relationships between the dimension of the assembly that ensure the closure and the mobility of over-constrained. These relationships called assembly equations and mobility conditions are hence necessary to resize an over-constrained solid assembly. Assembly equations and mobility conditions are computed by a computer algebra tool: Gröbner bases. However, the algebraic solving using Gröbner bases can be costly and may fail because of unreasonable computing time, this is the main reason of the strategies described in this thesis.The approach proposed in this thesis is composed of two main steps. First of all, an algebraic representation of a closed assembly and a mobile assembly is descibed. The closed-loop equations are written by using a coordinate free method and the mobility equations are generated from the closed-loop equations using direct and incremental methods. To simplify the computation of assembly equations and mobility conditions an algebraic analysis that rely on numerical analysis tools is proposed. Starting from a set of values of the parameters that describe the assembly to resize, the mobility state of the assembly is determined. Then, if the designer want to change the mobility state, a new set of values that have the mobility state chosen by the designer is generated. Once the initial set of values has the right mobility state, some dimensions are specialized to ease the computation of assembly equations and mobility conditions. However, if the parameters chosen are linked or its number is to high, there is a high chance that the study lead to no solution. Strategies to avoid these problems are also proposed. Finally, the tools developped in Maple® software that illustrate the methods proposed are described and an interactive tool that permits the designer to visualize the solutions of the closed-loop equations, assembly equations and mobility conditions computed after specialisation is proposed.

Systems biology aims at system-level understanding of biological systems, in particular cellular networks. The milestones of this understanding are knowledge of the structure of the system, understanding of its dynamics, effective control methods, and powerful prediction capability. The complexity of biological systems makes it inevitable to consider mathematical modeling in order to achieve these goals. The enormous accumulation of experimental data representing the activities of the living cell has triggered an increasing interest in the reverse engineering of biological networks from data. In particular, construction of discrete models for reverse engineering of biological networks is receiving attention, with the goal of providing a coarse-grained description of such networks. In this dissertation we consider the modeling framework of polynomial dynamical systems over finite fields constructed from experimental data. We present and propose solutions to two problems inherent in this modeling method: the necessity of appropriate discretization of the data and the selection of a particular polynomial model from the set of all models that fit the data. Data discretization, also known as binning, is a crucial issue for the construction of discrete models of biological networks. Experimental data are however usually continuous, or, at least, represented by computer floating point numbers. A major challenge in discretizing biological data, such as those collected through microarray experiments, is the typically small samples size. Many methods for discretization are not applicable due to the insufficient amount of data. The method proposed in this work is a first attempt to develop a discretization tool that takes into consideration the issues and limitations that are inherent in short data time courses. Our focus is on the two characteristics that any discretization method should possess in order to be used for dynamic modeling: preservation of dynamics and information content and inhibition of noise. Given a set of data points, of particular importance in the construction of polynomial models for the reverse engineering of biological networks is the collection of all polynomials that vanish on this set of points, the so-called ideal of points. Polynomial ideals can be represented through a special finite generating set, known as Gröbner basis, that possesses some desirable properties. For a given ideal, however, the Gröbner basis may not be unique since its computation depends on the choice of leading terms for the multivariate polynomials in the ideal. The correspondence between data points and uniqueness of Gröbner bases is studied in this dissertation. More specifically, an algorithm is developed for finding all minimal sets of points that, added to the given set, have a corresponding ideal of points with a unique Gröbner basis. This question is of interest in itself but the main motivation for studying it was its relevance to the construction of polynomial dynamical systems. This research has been partially supported by NIH Grant Nr. RO1GM068947-01. / Ph. D.

Neste trabalho estudamos algumas características das álgebras de Koszul, como por exemplo, a maneira como elas se relacionam com suas respectivas álgebras de Yoneda. Descrevemos a álgebra de Yoneda de uma álgebra monomial e como aplicação construímos uma família de álgebras: as chamadas homologicamente auto-duais. Uma álgebra de Koszul pode ser definida a partir da existência de resoluções lineares dos módulos simples. Por isso faz-se necessário a dedicação de parte de nossa atenção ao estudo destas resoluções. Além disso, achamos interessante estudar métodos para a construção de resoluções projetivas de módulos sobre quocientes de álgebras de caminhos. Para tal construção usamos essencialmente a teoria de bases de Gröbner não comutativas. Finalmente, para o caso de módulos lineares sobre álgebras de Koszul, veremos que é possível modicar essa construção de modo que a resolução resultante seja linear. / In this work we study some features of Koszul algebras as, for example, the way that they are related with their Yoneda algebras. We describe the Yoneda algebra of a monomial algebra and as an application we construct a family of algebras: the so called homologically self-dual algebras. A Koszul algebra can be dened as an algebra for which there are linear resolutions of their simple modules. Because of this we dedicate part of our attention to the study of projective resolutions. The study of methods for the construction of projectives resolutions of modules over quotients of path algebras, has an of interest its own. For the study of projective resolutions we used the theory of noncommutative, Gröbner bases. Finally, for the case of linear modules over Koszul algebras, we will see that it is possible to modify the general construction described here, so that the resulting resolution is linear.

Neste trabalho estudamos algumas características das álgebras de Koszul, como por exemplo, a maneira como elas se relacionam com suas respectivas álgebras de Yoneda. Descrevemos a álgebra de Yoneda de uma álgebra monomial e como aplicação construímos uma família de álgebras: as chamadas homologicamente auto-duais. Uma álgebra de Koszul pode ser definida a partir da existência de resoluções lineares dos módulos simples. Por isso faz-se necessário a dedicação de parte de nossa atenção ao estudo destas resoluções. Além disso, achamos interessante estudar métodos para a construção de resoluções projetivas de módulos sobre quocientes de álgebras de caminhos. Para tal construção usamos essencialmente a teoria de bases de Gröbner não comutativas. Finalmente, para o caso de módulos lineares sobre álgebras de Koszul, veremos que é possível modicar essa construção de modo que a resolução resultante seja linear. / In this work we study some features of Koszul algebras as, for example, the way that they are related with their Yoneda algebras. We describe the Yoneda algebra of a monomial algebra and as an application we construct a family of algebras: the so called homologically self-dual algebras. A Koszul algebra can be dened as an algebra for which there are linear resolutions of their simple modules. Because of this we dedicate part of our attention to the study of projective resolutions. The study of methods for the construction of projectives resolutions of modules over quotients of path algebras, has an of interest its own. For the study of projective resolutions we used the theory of noncommutative, Gröbner bases. Finally, for the case of linear modules over Koszul algebras, we will see that it is possible to modify the general construction described here, so that the resulting resolution is linear.

Dans cette thèse, nous étudions le concept d’algèbre pré-Lie libre engendrée par un ensemble (non-vide). Nous rappelons la construction par A. Agrachev et R. Gamkrelidze des bases de monômes dans les algèbres pré-Lie libres. Nous décrivons la matrice des vecteurs d’une base de monômes en termes de la base d’arbres enracinés exposée par F. Chapoton et M. Livernet. Nous montrons que cette matrice est unipotente et trouvons une expression explicite pour les coefficients de cette matrice, en adaptant une procédure suggérée par K. Ebrahimi-Fard et D. Manchon pour l’algèbre magmatique libre. Nous construisons une structure d’algèbre pré-Lie sur l’algèbre de Lie libre $\mathcal{L}$(E) engendrée par un ensemble E, donnant une présentation explicite de $\mathcal{L}$(E) comme quotient de l’algèbre pré-Lie libre $\mathcal{T}$^E, engendrée par les arbres enracinés (non-planaires) E-décorés, par un certain idéal I. Nous étudions les bases de Gröbner pour les algèbres de Lie libres dans une présentation à l’aide d’arbres. Nous décomposons la base d’arbres enracinés planaires E-décorés en deux parties O(J) et $\mathcal{T}$(J), où J est l’idéal définissant $\mathcal{L}$(E) comme quotient de l’algèbre magmatique libre engendrée par E. Ici, $\mathcal{T}$(J) est l’ensemble des termes maximaux des éléments de J, et son complément O(J) définit alors une base de $\mathcal{L}$(E). Nous obtenons un des résultats importants de cette thèse (Théorème 3.12) sur la description de l’ensemble O(J) en termes d’arbres. Nous décrivons des bases de monômes pour l’algèbre pré-Lie (respectivement l’algèbre de Lie libre) $\mathcal{L}$(E), en utilisant les procédures de bases de Gröbner et la base de monômes pour l’algèbre pré-Lie libre obtenue dans le Chapitre 2. Enfin, nous étudions les développements de Magnus classique et pré-Lie, discutant comment nous pouvons trouver une formule de récurrence pour le cas pré-Lie qui intègre déjà l’identité pré-Lie. Nous donnons une vision combinatoire d’une méthode numérique proposée par S. Blanes, F. Casas, et J. Ros, sur une écriture du développement de Magnus classique, utilisant la structure pré-Lie de $\mathcal{L}$(E). / In this thesis, we study the concept of free pre-Lie algebra generated by a (non-empty) set. We review the construction by A. Agrachev and R. Gamkrelidze of monomial bases in free pre-Lie algebras. We describe the matrix of the monomial basis vectors in terms of the rooted trees basis exhibited by F. Chapoton and M. Livernet. Also, we show that this matrix is unipotent and we find an explicit expression for its coefficients, adapting a procedure implemented for the free magmatic algebra by K. Ebrahimi-Fard and D. Manchon. We construct a pre-Lie structure on the free Lie algebra $\mathcal{L}$(E) generated by a set E, giving an explicit presentation of $\mathcal{L}$(E) as the quotient of the free pre-Lie algebra $\mathcal{T}$^E, generated by the (non-planar) E-decorated rooted trees, by some ideal I. We study the Gröbner bases for free Lie algebras in tree version. We split the basis of E- decorated planar rooted trees into two parts O(J) and $\mathcal{T}$(J), where J is the ideal defining $\mathcal{L}$(E) as a quotient of the free magmatic algebra generated by E. Here $\mathcal{T}$(J) is the set of maximal terms of elements of J, and its complement O(J) then defines a basis of $\mathcal{L}$(E). We get one of the important results in this thesis (Theorem 3.12), on the description of the set O(J) in terms of trees. We describe monomial bases for the pre-Lie (respectively free Lie) algebra $\mathcal{L}$(E), using the procedure of Gröbner bases and the monomial basis for the free pre-Lie algebra obtained in Chapter 2. Finally, we study the so-called classical and pre-Lie Magnus expansions, discussing how we can find a recursion for the pre-Lie case which already incorporates the pre-Lie identity. We give a combinatorial vision of a numerical method proposed by S. Blanes, F. Casas, and J. Ros, on a writing of the classical Magnus expansion in $\mathcal{L}$(E), using the pre-Lie structure.

La résolution de systèmes polynomiaux est un problème aux multiples applications, et les bases de Gröbner sont un outil important dans ce cadre. Il est connu que de nombreux systèmes issus d'applications présentent une structure supplémentaire par rapport à des systèmes arbitraires, et que ces structures peuvent souvent être exploitées pour faciliter le calcul de bases de Gröbner.Dans cette thèse, on s'intéresse à deux exemples de telles structures, pour différentes applications. Tout d'abord, on étudie les systèmes homogènes avec poids, qui sont homogènes si on calcule le degré en affectant un poids à chaque variable. Cette structure apparaît naturellement dans de nombreuses applications, dont un problème de cryptographie (logarithme discret). On montre comment les algorithmes existants, efficaces pour les polynômes homogènes, peuvent être adaptés au cas avec poids, avec des bornes de complexité générique divisées par un facteur polynomial en le produit des poids.Par ailleurs, on étudie un problème de classification de racines réelles pour des variétés définies par des déterminants. Ce problème a une application directe en théorie du contrôle, pour l'optimisation de contraste de l'imagerie à résonance magnétique. Ce système particulier s'avère insoluble avec les stratégies générales pour la classification. On montre comment ces stratégies peuvent tirer profit de la structure déterminantielle du système, et on illustre ce procédé en apportant des réponses aux questions posées par le problème d'optimisation de contraste. / Polynomial system solving is a problem with numerous applications, and Gröbner bases are an important tool in this context. Previous studies have shown that systèmes arising in applications usually exhibit more structure than arbitrary systems, and that these structures can be used to make computing Gröbner bases easier.In this thesis, we consider two examples of such structures. First, we study weighted homogeneous systems, which are homogeneous if we give to each variable an arbitrary degree. This structure appears naturally in many applications, including a cryptographical problem (discrete logarithm). We show how existing algorithms, which are efficient for homogeneous systems, can be adapted to a weighted setting, and generically, we show that their complexity bounds can be divided by a factor polynomial in the product of the weights.Then we consider a real roots classification problem for varieties defined by determinants. This problem has a direct application in control theory, for contrast optimization in magnetic resonance imagery. This specific system appears to be out of reach of existing algorithms. We show how these algorithms can benefit from the determinantal structure of the system, and as an illustration, we answer the questions from the application to contrast optimization.