Analyse des algorithmes d'Euclide : une approche dynanique

We studt in this thesis algorithms designed for gcd computations. We perform probabilistic analyses of many of these algorithms: the alpha-euclidean algorithms, the LSB algorithm and the Lehmer-Euclid algorithm. We obtain precise results on the average behavior of an entire family of parameters, which contains the number of iterations and the bit-complexity. We use the techniques of Dynamical Analysis of Alogirhtms, and the analyses performed in the thesis extend the range of application of this methodology. In particular, we study dynamical system with non surjective branches, dynamical systems defined on the set of p-adic numbers or systems of iterated functions. These analyses are based on a precise study of the Perron-Frobenius operator or of the transfer operator relative to these dynamical systems. In particular, the probabilistic behavior of the algorithms is related to the spectral properties of these operators. We also analyse the evolution of the main parameters of the algorithms during their execution: this leads to a precise study of the interrupted algorithms.Les objets étudiés dans cette thèse sont des algorithmes de calcul de pgcd. Nous effectuons dans cette thèse des analyses probabilistes de plusieurs de ces algorithmes : les algorithmes alpha-euclidiens, l'algorithme LSB et l'algorithme de Lehmer-Euclide. Nous obtenons des résultats précis sur le comportement moyen de toute une gamme de paramètres, entre autres le nombre d'itérations et la complexité en bits. Les techniques employées sont celles de l'analyse dynamique d'algorithmes, et les analyses effectuées dans cette thèse permettent d'élargir le champ d'application de cette méthodologie. En particulier, nous étudions des systèmes dynamiques à branches non surjectives, des systèmes dynamiques définis sur l'ensemble des nombres p-adiques ou encore des systèmes de fonctions itérées. Ces analyses impliquent une étude très précise des opérateurs de Perron-Frobenius et des opérateurs de transfert associés à ces systèmes. En particulier, le comportement probabiliste des algorithmes est relié aux propriétés spectrales de ces opérateurs. Nous analysons également l'évolution des principaux paramètres des algorithmes au cours de leur execution