Academic literature on the topic 'Générateur aléatoire de tresses'

International audience This article presents a methodology that automatically derives a combinatorial specification for the permutation class $\mathcal{C} = Av(B)$, given its basis $B$ of excluded patterns and the set of simple permutations in $\mathcal{C}$, when these sets are both finite. This is achieved considering both pattern avoidance and pattern containment constraints in permutations.The obtained specification yields a system of equations satisfied by the generating function of $\mathcal{C}$, this system being always positive and algebraic. It also yields a uniform random sampler of permutations in $\mathcal{C}$. The method presented is fully algorithmic. Cet article présente une méthodologie qui calcule automatiquement une spécification combinatoire pour la classe de permutations $\mathcal{C} = Av(B)$, étant donnés une base $B$ de motifs interdits et l’ensemble des permutations simples de $\mathcal{C}$, lorsque ces deux ensembles sont finis. Ce résultat est obtenu en considérant à la fois des contraintes de motifs interdits et de motifs obligatoires dans les permutations. La spécification obtenue donne un système d’équations satisfait par la série génératrice de la classe $\mathcal{C}$, système qui est toujours positif et algébrique. Elle fournit aussi un générateur aléatoire uniforme de permutations dans $\mathcal{C}$. La méthode présentée est complètement algorithmique.

Ce travail s'inscrit dans la thématique de la cryptographie basée sur les tresses. Nous nous intéressons au problème de conjugaison et au problème des cyclages présentés par K. H. Ko, S. J. Lee et al. à CRYPTO 2000 (LNCS 1880) dans New public-key cryptosystem using braid groups. D'une part, nous montrons que l'inversion de la fonction cyclage admet une solution polynomiale dans les groupes de Garside, qui sont une généralisation des groupes de tresses ; ceci permet de résoudre efficacement le problème des cyclages. D'autre part, le travail réalisé sur le problème de conjugaison et ses variantes met en relief le rôle joué par les générateurs aléatoires de tresses. Nous proposons un algorithme qui donne une factorisation du secret sous la forme d'un diviseur et d'un multiple. Ceci permet de définir deux nouvelles instances dont les secrets sont de taille réduite. De plus, nous exploitons la double structure de Garside des groupes de tresses afin d'améliorer l'efficacité de cette réduction. Nous observons que le choix du générateur aléatoire influe grandement sur la sécurité d'une instance et donnons plusieurs éléments constructifs et encourageants pour de futures recherches dans la conception d'un bon générateur aléatoire de tresses
. This work deals with braid based cryptography. We study the conjugacy search problem and the cycling problem presented by K. H. Ko, S. J. Lee and al. At CRYPTO 2000 (LNCS 1880) in New public-key cryptosystem using braid groups. On the one hand, we give a polynomial time algorithm to inverse the cycling function in Garside group which are a generalization of braid groups ; that allows to solve practically the cycling problem. On the other hand, our work on the conjugacy search problem and its variants emphasizes the choice of random generator of braids in protocols. We give an algorithm that factorizes the secret into a divisor and a multiple. That allows to define two new conjugacy instances with shorter secrets. Moreover, we exploit the fact that a braid group has two distinct Garside structures to improve the efficiency of the reduction. We observe that the choice of random generators influences greatly the security of an instance and we give several constructive and encouraging elements for further research in the design of good random generator of braids

Les systèmes de sécurité basés sur des algorithmes cryptographiques font un usage important de suites de bits aléatoires. Les générateurs aléatoires, comme tous les composants présents dans une carte à puce, ont toutefois l'obligation d'avoir des tailles très réduites sans pour autant contenir des failles de sécurité. L'objectif principal do cette thèse est de proposer une alternative moins coûteuse aux générateurs aléatoires existant, afin d'être facilement implantés clans de petits composants. Les axes de recherche sont la construction d'une architecture générale permettant d'étudier le fonctionnnement du générateur en cas de perturbations extérieures, l'analyse très précise du correcteur mathématique utilisé pour estimer la qualité de la sortie et les problèmes d'implêmentation
Systems of security based on cryptographic algorithm; use a lot of random HP-quences. For smart card applications, a random generator must to have a small size, without fails in its security. The main objective of this thesis is to propose an alternative to classical generators, in order to be inplemented on small components. The differonts parts of this work are the construction of an architecture for a random generator for small size components, the analysis and the inplementation of the mathematical corrector for an estimation of the quality of the. Output random sequence

La génération aléatoire d'objets combinatoires est un problème qui se pose dans de nombreux domaines de recherche (réseaux de communications, physique statistique, informatique théorique, combinatoire, etc.). Couramment, la distribution des échantillons est définie comme la distribution stationnaire d'une chaîne de Markov ergodique. En 1996, Propp et Wilson ont proposé un algorithme permettant l'échantillonnage sans biais de la distribution stationnaire. Ce dernier appelé aussi algorithme de simulation parfaite, requiert la simulation en parallèle de tous les états possibles de la chaîne. Plusieurs stratégies ont été mises en œuvre afin de ne pas avoir à simuler toutes les trajectoires. Elles sont intrinsèquement liées à la structure de la chaîne considérée et reposent essentiellement sur la propriété de monotonie, la construction de processus bornants qui exploitent la structure de treillis de l'espace d'états ou le caractère local des transitions. Dans le domaine des réseaux de communications, on s'intéresse aux performances des réseaux de files d'attente. Ces derniers se distinguent en deux groupes : ceux dont la distribution stationnaire possède une forme produit qui est facile à évaluer par le calcul et les autres. Pour ce dernier groupe, on utilise la génération aléatoire pour l'évaluation de performances. De par la structure des chaînes qui leurs sont associées, les réseaux ouverts de files d'attente se prêtent bien à la simulation via l'algorithme de simulation parfaite mais pas les réseaux fermés. La difficulté réside dans la taille de l'espace des états qui est exponentielle en le nombre de files à laquelle s'ajoute une contrainte globale à savoir le nombre constant de clients. La contribution principale de cette thèse est une nouvelle structure de données appelée diagramme. Cette structure est inspirée de la programmation dynamique et introduit une nouvelle technique de construction de processus bornant. La première partie du manuscrit est consacrée à la mise en œuvre de l'algorithme de Propp et Wilson pour des réseaux fermés n'étant pas nécessairement à forme produit. La représentation des états par un diagramme et l'opération de transition pour le processus bornant a dès lors une complexité polynomiale en le nombre de files et de clients. Cette technique est ensuite étendue aux réseaux fermés multiclasses ainsi qu'aux réseaux possédant des synchronisations. Une spécification des ensembles d'objets pouvant être représentés par un diagramme ainsi que des algorithmes agissant sur cette structure de données sont également proposés dans cette thèse. La méthode de Botzmann est une autre technique de simulation sans biais. Basée sur la combinatoire analytique, elle permet l'échantillonnage uniforme d'objets appartenant à une même classe combinatoire. Elle est employée dans la seconde partie de cette thèse afin d'échantillonner la distribution stationnaire de réseaux fermés à forme produit et pour la génération des multi-ensembles de taille fixe. Dans ce cadre, les diagrammes sont une nouvelle fois mis à profit. Enfin, la troisième partie présente les logiciels découlant des travaux présentés tout au long de ce travail, et qui implémentent les diagrammes et mettent en œuvre la simulation parfaite de réseaux fermés de files d'attente
Random generation of combinatorial objects is an important problem in many fields of research (communications networks, theoretical computing, combinatorics, statistical physics, ...). This often requires sampling the stationary distribution of an ergodic Markov chain. In 1996, Propp and Wilson introduced an algorithm to produce unbiased samples of the stationary distribution, also called a perfect sampling algorithm. It requires parallel simulation of all possible states of the chain. To avoid simulating all the trajectories, several strategies have been implemented. But they are related to the structure of the chain and require a monotonicity property, or a construction of a bounding chain that exploits the lattice structure of the state space or the local character of the transitions.In the field of communications networks, attention is paid to the performance of queueing networks, that can be distinguished into two groups: the networks that have a product form stationary distribution which is easy to compute. Random generation can be used for the others. Perfect sampling algorithms can be used for open queueing networks, thanks to the lattice structure of their state space. Unfortunately, that is not the case for closed queueing networks, due to the size of the state space which is exponential in the number of queues and a global constraint (a constant number of customers). The main contribution of this thesis is a new data structure called a diagram. It is inspired by dynamic programming and allows a new technique of construction of bounding processes. The first part of the manuscript is devoted to the implementation of the Propp and Wilson algorithm for closed queueing networks. The representation of a set of states by a diagram and the transition operation for the bounding process has a polynomial complexity in the number of queues and customers. This technique is extended to closed multi-class networks and to networks with synchronizations. Specification of sets of objects that can be represented by a diagram and generic algorithms that use this data structure are proposed in this manuscript. The Boltzmann method is another unbiased sampling technique. It is based on analytical combinatorics and produces uniform samples from objects that belong to the same combinatorial class. It is used in the second part of this thesis in order to sample the stationary distribution of closed networks with product form and for the generation of multisets of fixed cardinality. Diagrams are used again in this context. Finally, the third part presents the software produced during this thesis, implementing diagrams and perfect simulation of closed queueing networks

Actuellement, nous vivons dans une société numérique. L'avènement de l'Internet et l'arrivée du multimédia et des supports de stockage numériques, ont transformé profondément la façon dont nous communiquons. L'image en particulier occupe une place très importante dans la communication interpersonnelle moderne. Toutefois, elle présente l'inconvénient d'être représentée par une quantité d'information très importante. De ce fait, la transmission et le stockage des images soulèvent certains problèmes qui sont liés essentiellement à la sécurité et à la compression d'images. Ce sont ces considérations qui ont guidé cette thèse. En effet, la problématique que nous posons dans cette thèse est de proposer une solution conduisant à la crypto-compression d'images afin d'assurer un archivage et un transfert sécurisés tout en conservant les performances de la méthode de compression utilisée. En effet, nos travaux de recherche ont porté essentiellement sur la compression et le cryptage des images numériques. Concernant la compression, nous avons porté un intérêt particulier au codage arithmétique vu sont efficacité en terme de ta ux de compression et son utilisation par les nouvelles normes et standards de compression tel que JPEG2000, JBIG, JBIG2 et H.264/AVC. Quant au cryptage, nous avons opté pour l'utilisation du chaos combiné avec les fractions continues afin de générer des flux de clés ayant à la fois de bonnes propriétés cryptographiques et statistiques. Ainsi, nous avons proposé deux nouvelles méthodes de compression sans perte basées sur le codage arithmétique tout en introduisant de nouveaux paramètres de codage afin de réduire davantage la taille en bits des images compressées. Deux autres méthodes s'appuient sur l'utilisation du chaos et des fractions continues pour le développement d'un générateur de nombres pseudo-aléatoires et le cryptage par flot d'images. Enfin, nous proposons une nouvelle méthode qui emploie conjointement le cryptage avec la compression. Cette dernière méthode se base sur l'échange des sous-intervalles associés aux symboles d'un codeur arit hmétique binaire de façon aléatoire tout en exploitant notre générateur de nombres pseudo-aléatoire. Elle est efficace, sécurisée et conserve le taux de compression obtenu par le codage arithmétique et ceci quelque soit le modèle statistique employé : statique ou adaptatif
Actually, we live in a digital society. The proliferation of the Internet and the rapid progress in information technology on multimedia, have profoundly transformed the way we communicate. An enormous amount of media can be easily exchanged through the Internet and other communication networks. Digital image in particular occupies an important place in modern interpersonal communication. However, image data have special features such as bulk capacity. Thus, image security and compression issues have became exceptionally acute. It is these considerations that have guided this thesis. Thus, we propose throw this thesis to incorporating security requirements in the data compression system to ensure reasonable security without downgrading the compression performance.For lossless image compression, we have paid most attention to the arithmetic coding (AC) which has been widely used as an efficient compression algorithm in the new standards including JBIG, JBIG2, JPEG2000 and H.264/AVC. For image encryption, we are based on the combination of a chaotic system and the Engel continued fraction map to generate key-stream with both good chaotic and statistical properties. First, we have proposed two new schemes for lossless image compression based on adding new pre-treatment steps and on proposing new modeling methods to estimate probabilities for AC. Experimental results demonstrate that the proposed schemes give mean compression ratios that are significantly higher than those by the conventional AC. In addition, we have proposed a new pseudo-random bit generator (PRBG). The detailed analysis done by NIST statistical test Suite demonstrates that the proposed PRGB is suitable for cryptography. The proposed PRBG is used to develop a new symmetr ic stream cipher for image encryption. Theoretic and numerical simulation analyses indicate that our image encryption algorithm is efficient and satisfies high security. Finally, we have proposed a new scheme which performs both lossless compression and encryption of image. The lossless compression is based on the binary AC (BAC) and the encryption is based on the proposed PRBG. The numerical simulation analysis indicates that the proposed compression and encryption scheme satisfies highly security with no loss of the BAC compression efficiency

Nous étudions dans cette thèse une matrice de processeurs élémentaires optoélectronique (parfois appelé rétine artificielle optoélectronique ou encore spa - pour smart pixel array) capable de réaliser plusieurs fonctions de traitement d'images bas niveau a cadence vidéo. Plus précisément, il s'agit d'une machine simd optoélectronique fonctionnant par recuit simule : chaque processeur élémentaire (pe ou sp - pour smart pixel) est l'équivalent d'un neurone dont l'état évolue en fonction de celui de ses voisins, et cela de façon probabiliste grâce a un générateur de nombres aléatoires optique base sur le phénomène de speckle laser. Dans une première version du processeur (circuit en silicium cmos 0,8 m), chaque pe est interconnecté de façon électronique a ces quatre plus proches voisins. Un montage base sur deux modulateurs spatiaux de lumière ferroélectriques et un hologramme de dammann permet d'étendre le voisinage d'interconnexion et de simuler des interconnexions intra-processeur optiques reconfigurables. Le montage servira a demontrer la détection du mouvement sur des séquences d'images a niveaux de gris ; toutefois, les performances restent médiocres (2 a 5 secondes par image). En fin de thèse est étudié un nouveau prototype base sur une matrice a entrées et sorties optiques (diodes p-i-n a puits quantiques multiples) réalisé en technologie hybride si/gaas par flip-chip bonding . Les performances du système sont considérablement améliorées (l'architecture comporte alors de véritables interconnexions optiques intra-processeur). L'étude théorique permet de conclure que l'utilisation d'une puce a entrées et sorties optiques rendrait le système a la fois compact (taille comparable avec celle d'un processeur pentium avec ses éléments de réfrigération) et extrêmement rapide (dizaines de milliers d'images a la seconde), ce qui en ferait un dispositif de choix pour les applications embarques de traitement d'images bas-niveau et temps réel.

La jonction tunnel magnétique (JTM) commutée par la couple de transfert de spin (STT) a été considérée comme un candidat prometteur pour la prochaine génération de mémoires non-volatiles et de circuits logiques, car elle fournit une solution pour surmonter le goulet d'étranglement de l'augmentation de puissance statique causée par la mise à l'échelle de la technologie CMOS. Cependant, sa commercialisation est limitée par la fiabilité faible, qui se détériore gravement avec la réduction de la taille du dispositif. Cette thèse porte sur l'étude de la fiabilité des circuits basés sur JTM. Tout d'abord, un modèle compact de JTM incluant les problèmes principaux de fiabilité est proposé et validé par la comparaison avec des données expérimentales. Sur la base de ce modèle précis, la fiabilité des circuits typiques est analysée et une méthodologie d'optimisation de la fiabilité est proposée. Enfin, le comportement de commutation stochastique est utilisé dans certaines nouvelles conceptions d'applications classiques
Spin transfer torque magnetic tunnel junction (STT-MTJ) has been considered as a promising candidate for next generation of non-volatile memories and logic circuits, because it provides a perfect solution to overcome the bottleneck of increasing static power caused by CMOS technology scaling. However, its commercialization is limited by the poor reliability, which deteriorates severely with device scaling down. This thesis focuses on the reliability investigation of MTJ based non-volatile circuits. Firstly, a compact model of MTJ including main reliability issues is proposed and validated by the comparison with experimental data. Based on this accurate model, the reliability of typical circuits is analyzed and reliability optimization methodology is proposed. Finally, the stochastic switching behavior is utilized in some new designs of conventional applications

Le courant d'alimentation d'une carte à puce présente des corrélations significatives avec les données traitées par son microcontrôleur. Les techniques de cryptanalyse dites « par analyse en courant » exploitent ces corrélations pour déterminer les clés secrètes des cryptosystèmes embarqués. Cette étude traite de la conception d'un système d'alimentation sur puce destiné à protéger les microcontrôleurs encartables contre les attaques par analyse en courant. Le nouveau système proposé permet de réguler la tension d'alimentation interne du microcontrôleur à partir de la tension d'alimentation externe fournie par le lecteur, tout en décorrélant le courant d'alimentation externe du courant d'alimentation interne. Sa surface et son rendement respectent les contraintes imposées par le support. De plus, son architecture inclut un nouveau générateur d'horloge aléatoire basé, entre autres, sur un attracteur chaotique de type « double-scroll ». Le système a été simulé avec Eldo et les paramètres MM9 d'un procédé CMOS 0.18 µm standard de la société STMicroelectronics; les résultats des simulations témoignent de son efficacité. Par ailleurs, l'oscillateur chaotique a été fabriqué suivant le procédé CMOS 0.35 µm 2P/4M du fondeur AMS; les mesures expérimentales confirment les résultats théoriques.