This research addressed the design and implementation of a polynomial-complexity deadlock avoidance controller for a flexible manufacturing cell modeled using Colored Petri Nets. The cell model is robust to changes in the part types to be manufactured in the system and is automatically generated using the interaction of the resources in the cell and the technological capabilities of the machines. The model also captures dynamic routing flexibility options. The framework introduced separates the cell model from the control logic allowing the system designer to implement and test various control algorithms using the same cell model. The controller adopts the neighborhood deadlock avoidance policy to resolve deadlocks and control the resource allocation decisions within the system. The evaluation of the performance of systems controlled by not maximally permissive algorithms is important in determining the applicability of the control algorithms. There are many polynomial time deadlock avoidance algorithms proposed for the control of general resource allocation systems. However, the permissiveness of these algorithms is not quantified and the applicability of these algorithms in terms of effective resource utilization remains unanswered. The performance of automated manufacturing cells controlled using the neighborhood deadlock avoidance policy is benchmarked by comparing its performance with other control policies.

L'objet de cette thèse est l'étude de diverses primitives cryptographiques utiles dans des protocoles Diffie-Hellman. Nous étudions tout d'abord les protocoles Diffie-Helmman sur des structures commutatives ou non. Nous en proposons une formulation unifiée et mettons en évidence les différents problèmes difficiles associés dans les deux contextes. La première partie est consacrée à l'étude de pseudo-paramétrisations de courbes algébriques en temps constant déterministe, avec application aux fonctions de hachage vers les courbes. Les propriétés des courbes algébriques en font une structure de choix pour l'instanciation de protocoles reposant sur le problème Diffie-Hellman. En particulier, ces protocoles utilisent des fonctions qui hachent directement un message vers la courbe. Nous proposons de nouvelles fonctions d'encodage vers les courbes elliptiques et pour de larges classes de fonctions hyperelliptiques. Nous montrons ensuite comment l'étude de la géométrie des tangentes aux points d'inflexion des courbes elliptiques permet d'unifier les fonctions proposées tant dans la littérature que dans cette thèse. Dans la troisième partie, nous nous intéressons à une nouvelle instanciation de l'échange Diffie-Hellman. Elle repose sur la difficulté de résoudre un problème de factorisation dans un anneau de polynômes non-commutatifs. Nous montrons comment un problème de décomposition Diffie-Hellman sur un groupe non-commutatif peut se ramener à un simple problème d'algèbre linéaire pourvu que les éléments du groupe admettent une représentation par des matrices. Bien qu'elle ne soit pas applicable directement au cas des polynômes tordus puisqu'ils n'ont pas d'inverse, nous profitons de l'existence d'une notion de divisibilité pour contourner cette difficulté. Finalement, nous montrons qu'il est possible de résoudre le problème Diffie-Hellman sur les polynômes tordus avec complexité polynomiale. / In this thesis, we study several cryptographic primitives of use in Diffie-Hellman like protocols. We first study Diffie-Hellman protocols on commutative or noncommutative structures. We propose an unified wording of such protocols and bring out on which supposedly hard problem both constructions rely on. The first part is devoted to the study of pseudo-parameterization of algebraic curves in deterministic constant time, with application to hash function into curves. Algebraic curves are indeed particularly interesting for Diffie-Hellman like protocols. These protocols often use hash functions which directly hash into the curve. We propose new encoding functions toward elliptic curves and toward large classes of hyperelliptic curves. We then show how the study of the geometry of flex tangent of elliptic curves unifies the encoding functions as proposed in the litterature and in this thesis. In the third part, we are interested in a new instantiation of the Diffie-Hellman key exchange. It relies on the difficulty of factoring in a non-commutative polynomial ring. We show how to reduce a Diffie-Hellman decomposition problem over a noncommutative group to a simple linear algebra problem, provided that group elements can be represented by matrices. Although this is not directly relevant to the skew polynomial ring because they have no inverse, we use the divisibility to circumvent this difficulty. Finally, we show it's possible to solve the Diffie-Hellman problem on skew polynomials with polynomial complexity.