Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 22 Février 2000

Analyse en moyenne de la complexité en bits de l'algorithme d'Euclide

par 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.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr