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 Mars 2005

Le Lièvre Dyadique et la Tortue de Lyapunov

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

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