Retour à l'index du GREYC Retour à la page d'accueil de l'équipe ALGO Site du CNRS

Séminaire de l'équipe ALGO

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 12 Janvier 2010

Modélisation de l'algorithme LLL par des tas de sable

par Brigitte Vallée (GREYC)

L'algorithme LLL est le plus célèbre des algorithmes de réduction de réseaux: il considère un réseau euclidien, c'est-à-dire l'ensemble des combinaisons linéaires entières d'une famille de vecteurs de R^n et en construit une base réduite, c'est-à-dire une base formée de vecteurs assez courts et assez orthogonaux. Cet algorithme peut être vu comme une extension de l'algorithme du pgcd, et joue un rôle essentiel dans beaucoup de domaines de l'informatique et des mathématiques. Cependant, le comportement général de cet algorithme est très mal compris, et il n'existe pas d'analyse probabiliste précise des principaux paramètres -- nombre d'itérations ou géométrie de la base de sortie-- . Les nombreuses expérimentations existantes posent des questions difficiles, qui restent aujourd'hui sans réponse satisfaisante. Ici, nous effectuons de nouvelles expérimentations, complémentaires des existantes, qui décrivent l'exécution précise de l'algorithme, et en particulier un paramètre essentiel de l'éxécution, le ''logarithme du facteur de décroissance''. Ces expérimentations donnent des arguments importants en faveur d'une hypothèse de régularité, qui affirme que ce facteur de décroissance reste constant au cours d'une exécution. Nous proposons alors un modèle simplifié pour l'algorithme LLL, fondé sur cette hypothèse de régularité, qui nous conduit à une classe bien connue de systèmes dynamiques discrets, les tas de sable. Dans ce modèle, il est assez facile d'obtenir des résultats probabilistes précis sur les deux principaux paramètres de l'algorithme: le nombre d'itérations et la géométrie de la sortie. Ces résultats, qui sont donc prouvés sur des exécutions régulières, sont en bonne adéquation avec les résultats expérimentaux obtenus sur des exécutions génériques de l'algorithme. Cela donne du poids à l'hypothèse de régularité, et montre l'utilité d'un tel modèle simplifié.

Travail commun avec Manfred Madritsch.

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.unicaen.fr