– LAREDA

Les algorithmes de réduction de réseaux (désignés par LaRedA) (en particulier l'algorithme LLL, créé par Lenstra, Lenstra et Lovasz en 1982) construisent une base ''réduite'' d'un réseau euclidien, formée de vecteurs assez courts et assez orthogonaux. Ces algorithmes jouent un rôle majeur dans de nombreux domaines des mathématiques et de l'informatique: cryptologie, calcul formel, programmation linéaire entière, théorie des nombres. Cependant, leur comportement est bien mal compris: beaucoup d'observations expérimentales (sur l'exécution des algorithmes et la géométrie de leurs sorties), déjà faites par les membres du projet [MP], posent des questions importantes qui restent sans réponses, et conduisent à des conjectures naturelles, qui restent sans preuves. Le projet cherche à mieux comprendre ces algorithmes, ce qui conduirait à une explication prouvée des phénomènes expérimentaux observés. Cela rendrait possible l'amélioration des principaux algorithmes qui utilisent la réduction des réseaux, dans chaque domaine d'application cité. Une des principales motivations du projet réside dans l'importance, et la diversité des applications des LaRedA. Nous visons d'abord à construire une stratégie algorithmique générale de la réduction des réseaux. Nous nous concentrerons ensuite sur des domaines d'application particuliers: cryptologie, arithmétique, géométrie discrète, dont les MP sont spécialistes, en mettant un accent particulier sur la cryptologie. Ce retour aux applications est un axe important du projet. Ce projet est une entreprise difficile, où nous utiliserons des approches variées et complémentaires. C'est là où réside l'originalité du projet, c'est en cela qu'il peut réussir là où d'autres ont échoué. Nous adopterons trois points de vue: une modélisation dédiée, une approche probabiliste, une approche dynamique. Cette approche mixte a déjà été utilisée avec succès en petite dimension: pour n= 1, dans l'algorithme d'Euclide, et pour n= 2 pour l'algorithme de Gauss. Ces petites dimensions représentent une étape importante du projet, car l'algorithme LLL est une suite de réductions de Gauss sur des sous-réseaux du grand réseau. A-- Modélisation dédiée. Nous définirons d'abord des modèles probabilistes réalistes, liés à chacune des applications citées. Pour chacune d'elles, il existe des types particuliers de réseaux, qui conduisent à des modèles probabilistes différents. Puis nous entreprendrons l'analyse des LaRedA, sous ces modèles probabilistes variés; nous quantifierons le comportement probabiliste des principaux paramètres des algorithmes: le nombre d'itérations, la géométrie des bases réduites, l'évolution des densités lors de l'exécution.... B-- Approche probabiliste. Cette démarche (déjà adoptée par des MP) a donné des résultats tangibles dans des modèles (irréalistes) où les vecteurs de la base d'entrée sont choisis indépendamment, selon une densité invariante par rotation. Dans un tel cadre, on a pu déterminer la probabilité qu'une base d'entrée soit déjà réduite. Nous voulons étendre cette étude au cas des modèles réalistes et de l'algorithme lui-même, et pas seulement de sa distribution d'entrée. Dans le cas où des calculs exacts sont difficiles, nous chercherons à extraire, à partir de la structure algorithmique, des propriétés probabilistes (martingales, indépendance) qui permettront une étude asymptotique. C-- Approche dynamique. Grâce à des résultats déjà obtenus par des MP, la dynamique de l'algorithme d'Euclide est maintenant bien connue, avec de nombreux résultats sur le comportement probabiliste de cet algorithme, obtenus en utilisant la théorie des systèmes dynamiques [SD] et des outils associés, comme les opérateurs de transfert. Ces techniques ont été étendues au cas n= 2. Les LaRedA peuvent être considérés comme des extensions multi-dimensionnelles de l'algorithme d'Euclide. Celui-ci calcule le pgcd de deux entiers u et v (qui est le plus petit entier non nul du réseau Zu+Zv) mais aussi toutes les meilleures approximations du rationnel u/v. Quand on veut étendre cet algorithme à des dimensions supérieures, deux directions principales sont possibles: on peut privilégier les meilleures approximations rationnelles simultanées (comme dans l'algorithme de Jacobi-Perron [JP] ou l'algorithme de Brun, qui donnent lieu à des SD déjà bien étudiés), ou se concentrer sur les petits vecteurs (comme dans le cas de la réduction de réseaux). Dans ce cas, le SD associé n'a jamais été étudié. Nous voulons faire cette étude, et comparer ce SD avec celui de Jacobi-Perron. Le SD associé aux LaRedA est probablement un objet complexe quand n>2: puisque les LaRedA s'arrêtent toujours, leur SD ont un ''trou'' (ce qui n'est pas le cas pour les SD de JP], et les mesures de probabilité conditionnellement invariantes joueront un rôle central dans l'étude des propriétés statistiques de tels systèmes.