La Tortue de Lyapunov et le Lièvre Dyadique

Nous étudions un algorithme de pgcd dirigé par les bits les moins significatifs des entiers, l'algorithme LSB, et effectuons une analyse en moyenne précise de ses principaux paramètres (nombre d'itérations, nombre de décalages, etc). Cette analyse est basée sur une étude détaillée des systèmes dynamiques qui constituent l'extension continue de l'algorithme. Il apparaît qu'il est plus efficace de travailler ici dans une double extension, à la fois 2-adique et réelle. Ceci nous amène dans le cadre des produits de matrices aléatoires, et notre principal résultat s'exprime à l'aide de l'exposant de Lyapunov de l'ensemble des matrices relatives à l'algorithme. Ce dernier peut finalement être vu comme une course entre un Lièvre dyadique, d'une vitesse de 2 bits par étape, et une Tortue de Lyapunov d'une vitesse de 0.05 bits par étape. Même si la Tortue part avant le Lièvre, celui-ci la rattrape et l'algorithme s'arrête. (Travail commun avec Benoît Daireaux, Veronique Maume)