Dans ce document, nous étudions l’évitabilité de différentes formes de répétitions dans les mots. En particulier 3 des 6 chapitres sont dédiés aux répétitions abéliennes en lien notamment avec deux questions d’Erdős de 1957 et 1961. Nous commençons par montrer qu’il existe un algorithme décidant, sous certaines conditions, si un mot morphique évite des puissances abéliennes. Cet algorithme élargit la classe sur laquelle les précédents algorithmes pouvaient décider. Une généralisation de cet algorithme nous permet de montrer que les longs carrés abéliens sont évitables sur l’alphabet ternaire et que les carrés additifs sont évitables sur Z2 . Le premier résultat répond à une question ouverte de Mäkelä datant de 2003 alors que le deuxième rappelle la question ouverte de 1994 concernant l’évitabilité des carrés additifs sur Z.Une autre généralisation de notre algorithme permet d’étudier l’évitabilité des motifs au sens abélien. Nous montrons que les motifs binaires de longueur supérieure à 14 sont évitables sur l’alphabet binaire, améliorant la précédente borne de 118.Nous donnons des conditions suffisantes pour qu’un morphisme soit sans longues puissances nème k-abéliennes. Ce résultat nous permet de calculer, pour tout k ≥ 3, le nombre minimum de carrés k-abéliens qu’un mot binaire infini doit contenir en facteur. Il permet aussi de montrer que les longs carrés 2-abéliens sont évitables sur l’alphabet binaire et qu’il existe un mot ternaire qui ne contient qu’un seul carré 2-abélien en tant que facteur.Enfin, nous proposons une classification complète des formules binaires en fonction de la taille d’alphabet qu’il faut pour les éviter et du taux de croissance (exponentiel ou polynomial) du langage les évitant. / In this document, we study the avoidability of different kind of repetitions in words. We firstshow that under some conditions one can decide whether a morphic word avoids abelian n-thpowers. This algorithm can decide over a wider class of morphism than the previousalgorithms. We generalize this algorithm and use it to show that long abelian squares areavoidable over the ternary alphabet and that additive squares are avoidable over Z2 . The firstresult answers a weak version of a question formulated by Mäkelä in 2003 and the second oneis related to an open question from 1994 about the avoidability of additive squares over Z.Another generalization of this algorithm can be used to study avoidability of patterns in theabelian sense. In particular, we show that binary patterns of length more than 14 areavoidable over the binary alphabet in the abelian sense. This improves considerably theprevious bound of 118.We give sufficient conditions for a morphism to be long k-abelian n-th power-free. This resultallows us to compute for every k ≥ 3 the number of different k-abelian squares that a binaryword must contain. We prove that long 2-abelian squares are avoidable over the binaryalphabet and that over the ternary alphabet there exists a word that contains only one 2-abelian square.We also give a complete classification of binary formulas based on the size of the smallestalphabet over which they are avoidable and on the growth (exponential or polynomial) of theassociated language.

Abstract The design principles proposed independently by both Ralph Merkle and Ivan Damgård in 1989 are applied widely in hash functions that are used in practice. The construction reads the message in one message block at a time and applies iteratively a compression function that, given a single message block and a hash value, outputs a new hash value. This iterative structure has some security weaknesses. It is vulnerable, for instance, to Joux's multicollision attack, herding attack that uses diamond structures and Trojan message attack. Our principal research topic comprises the deficiencies in hash function security induced by the Merkle-Damgård construction. In this work, we present a variant of Joux's multicollision attack. We also develop a new, time-saving algorithm for creating diamond structures. Moreover, two new efficient versions of Trojan message attack are introduced. The main contribution of the thesis is the analysis of generalized iterated hash functions. We study the combinatorial properties of words from a new perspective and develop results that are applied to give a new upper bound for the complexity of multicollision attacks against the so called q-bounded generalized iterated hash functions. / Tiivistelmä Vuonna 1989 Ralph Merkle ja Ivan Damgård ehdottivat toisistaan riippumatta hash-funktioille suunnitteluperiaatteita, joita käytetään tänä päivänä laajasti. Niin kutsuttu Merkle-Damgård -rakenne lukee viestin sisään viestiblokki kerrallaan ja käyttää tiivistefunktiota, joka liittää hash-arvoon ja viestiblokkiin uuden hash-arvon. Tällä iteratiivisella rakenteella on joitakin turvallisuusheikkouksia. Se on haavoittuva esimerkiksi Joux’n monitörmäyshyökkäykselle, timanttirakenteita hyödyntävälle paimennushyökkäykselle ja Troijan viesti -hyökkäykselle. Väitöskirjan pääasiallinen tutkimusaihe on Merkle-Damgård -rakenteen aiheuttamat puutteet tietoturvassa. Tässä työssä esitetään uusi versio Joux’n monitörmäyshyökkäyksestä, luodaan uusi aikaa säästävä algoritmi timanttirakenteiden kehittämiseksi ja kaksi uutta tehokasta versiota Troijan viesti -hyökkäyksestä. Väitöskirjan tärkein kontribuutio on yleistettyjen iteratiivisten hash-funktioiden turvallisuuden analysointi. Sanojen kombinatorisia ominaisuuksia tutkitaan uudesta näkökulmasta, jonka pohjalta kehitettyjä tuloksia soveltamalla luodaan uusi yläraja niin kutsuttujen q-rajoitettujen yleisten iteratiivisten hash-funktioiden monitörmäyshyökkäysten kompleksisuudelle.

L'analyse dynamique intègre des outils propres aux systèmes dynamiques (comme l'opérateur de transfert) au cadre de la combinatoire analytique, et permet ainsi l'analyse d'un grand nombre d'algorithmes et objets qu'on peut associer naturellement à un système dynamique. Dans ce manuscrit de thèse, nous présentons, dans la perspective de l'analyse dynamique, l'étude probabiliste de plusieurs problèmes qui semblent à priori bien différents : l'analyse probabiliste de la fonction de récurrence des mots de Sturm, et l'étude probabiliste de l'algorithme du “logarithme continu”. Les mots de Sturm constituent une famille omniprésente en combinatoire des mots. Ce sont, dans un sens précis, les mots les plus simples qui ne sont pas ultimement périodiques. Les mots de Sturm ont déjà été beaucoup étudiés, notamment par Morse et Hedlund (1940) qui en ont exhibé une caractérisation fondamentale comme des codages discrets de droites à pente irrationnelle. Ce résultat relie ainsi les mots de Sturm au système dynamique d'Euclide. Les mots de Sturm n'avaient jamais été étudiés d'un point de vue probabiliste. Ici nous introduisons deux modèles probabilistes naturels (et bien complémentaires) et y analysons le comportement probabiliste (et asymptotique) de la “fonction de récurrence” ; nous quantifions sa valeur moyenne et décrivons sa distribution sous chacun de ces deux modèles : l'un est naturel du point de vue algorithmique (mais original du point de vue de l'analyse dynamique), et l'autre permet naturellement de quantifier des classes de plus mauvais cas. Nous discutons la relation entre ces deux modèles et leurs méthodes respectives, en exhibant un lien potentiel qui utilise la transformée de Mellin. Nous avons aussi considéré (et c'est un travail en cours qui vise à unifier les approches) les mots associés à deux familles particulières de pentes : les pentes irrationnelles quadratiques, et les pentes rationnelles (qui donnent lieu aux mots de Christoffel). L'algorithme du logarithme continu est introduit par Gosper dans Hakmem (1978) comme une mutation de l'algorithme classique des fractions continues. Il calcule le plus grand commun diviseur de deux nombres naturels en utilisant uniquement des shifts binaires et des soustractions. Le pire des cas a été étudié récemment par Shallit (2016), qui a donné des bornes précises pour le nombre d'étapes et a exhibé une famille d'entrées sur laquelle l'algorithme atteint cette borne. Dans cette thèse, nous étudions le nombre moyen d'étapes, tout comme d'autres paramètres importants de l'algorithme. Grâce à des méthodes d'analyse dynamique, nous exhibons des constantes mathématiques précises. Le système dynamique ressemble à première vue à celui d'Euclide, et a été étudié d'abord par Chan (2005) avec des méthodes ergodiques. Cependant, la présence des puissances de 2 dans les quotients change la nature de l'algorithme et donne une nature dyadique aux principaux paramètres de l'algorithme, qui ne peuvent donc pas être simplement caractérisés dans le monde réel.C'est pourquoi nous introduisons un nouveau système dynamique, avec une nouvelle composante dyadique, et travaillons dans ce système à deux composantes, l'une réelle, et l'autre dyadique. Grâce à ce nouveau système mixte, nous obtenons l'analyse en moyenne de l'algorithme. / Dynamical Analysis incorporates tools from dynamical systems, namely theTransfer Operator, into the framework of Analytic Combinatorics, permitting the analysis of numerous algorithms and objects naturally associated with an underlying dynamical system.This dissertation presents, in the integrated framework of Dynamical Analysis, the probabilistic analysis of seemingly distinct problems in a unified way: the probabilistic study of the recurrence function of Sturmian words, and the probabilistic study of the Continued Logarithm algorithm.Sturmian words are a fundamental family of words in Word Combinatorics. They are in a precise sense the simplest infinite words that are not eventually periodic. Sturmian words have been well studied over the years, notably by Morse and Hedlund (1940) who demonstrated that they present a notable number theoretical characterization as discrete codings of lines with irrationalslope, relating them naturally to dynamical systems, in particular the Euclidean dynamical system. These words have never been studied from a probabilistic perspective. Here, we quantify the recurrence properties of a ``random'' Sturmian word, which are dictated by the so-called ``recurrence function''; we perform a complete asymptotic probabilistic study of this function, quantifying its mean and describing its distribution under two different probabilistic models, which present different virtues: one is a naturaly choice from an algorithmic point of view (but is innovative from the point of view of dynamical analysis), while the other allows a natural quantification of the worst-case growth of the recurrence function. We discuss the relation between these two distinct models and their respective techniques, explaining also how the two seemingly different techniques employed could be linked through the use of the Mellin transform. In this dissertation we also discuss our ongoing work regarding two special families of Sturmian words: those associated with a quadratic irrational slope, and those with a rational slope (not properly Sturmian). Our work seems to show the possibility of a unified study.The Continued Logarithm Algorithm, introduced by Gosper in Hakmem (1978) as a mutation of classical continued fractions, computes the greatest common divisor of two natural numbers by performing division-like steps involving only binary shifts and substractions. Its worst-case performance was studied recently by Shallit (2016), who showed a precise upper-bound for the number of steps and gave a family of inputs attaining this bound. In this dissertation we employ dynamical analysis to study the average running time of the algorithm, giving precise mathematical constants for the asymptotics, as well as other parameters of interest. The underlying dynamical system is akin to the Euclidean one, and was first studied by Chan (around 2005) from an ergodic, but the presence of powers of 2 in the quotients ingrains into the central parameters a dyadic flavour that cannot be grasped solely by studying this system. We thus introduce a dyadic component and deal with a two-component system. With this new mixed system at hand, we then provide a complete average-case analysis of the algorithm by Dynamical Analysis.