Ali Akhavi

(Travail commun avec Brigitte Vallée)

L’algorithme d’Euclide est un algorithme qui calcule le pgcd de deux entiers par une suite de divisions euclidiennes. Il s’agit d’un des plus anciens algorithmes travaillant sur les nombres entiers qui constitue par ailleurs “la brique de base” de nombreuses applications en calcul formel ou en cryptographie.

Pour autant, l’analyse en moyenne et en distribution de cet algorithme n’a vu le jour que tres recemment (par exemple, une conjecture demontrée en 1994 par Hensley). Tous les resultats connus jusqu’ a present concernent le nombre moyen d’operations arithmetiques effectuées.

Dans cet exposé, nous introduisons un cadre general pour l’analyse en moyenne de l’algorithme d’Euclide (et de ses variantes); nous obtenons de nouveaux résulats concernant la complexité moyenne mesurée de maniere realiste, i.e., faisant intervenir le nombre d’opérations élémentaires sur les bits.

Notre méthode s’appuie sur l’etude des transformations élementaires de l’intervalle [0,1] utilisées par un algorithme de type Euclidien. Les propriétés analytiques de cet ensemble de transformations sont synthetisees dans un operateur dont l’etude determine le comportement en moyenne de l’algorithme.