Benoît Daireaux (GREYC, Université de Caen)

Travail en collaboration avec Véronique Maume-Deschamps, Brigitte Vallée

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 précise des systèmes dynamiques qui constituent l’extension continue de l’algorithme. Il apparaît qu’il est plus efficace de travailler ici sur 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 donc à l’aide de l’exposant de Lyapunov $\gamma$ 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 $\gamma<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.