Séminaire du 25 mai 2009,
10h30: H-LLL : Un LLL flottant vectoriel. Ivan Morel, Équipe-projet Arénaire Inria et ENS Lyon.
La réduction de réseaux a d'importantes applications dans divers domaines, comme la cryptologie, la théorie algorithmique des nombres, l'arithmétique des ordinateurs, etc.. L'algorithme LLL permet de réduire une base quelconque d'un réseau en une 'bonne' base en temps polynomial. Cependant, la taille des entiers manipulés dans l'algorithme rend ce dernier inutilisable en pratique dans sa version exacte quand la dimension ou la taille des entrées augmente. Il est donc naturel de se tourner vers le calcul flottant, particulièrement pour le calcul des coefficients de Gram-Schmidt dont le coût domine le coût total de l'algorithme. Je présenterai ainsi une nouvelle variante flottante de l'algorithme LLL, H-LLL, utilisant l'algorithme de Householder flottant pour calculer la décomposition matricielle QR et ainsi obtenir les coefficients de Gram-Schmidt. J'introduirai les enjeux d'une telle approche, ainsi que ses avantages/inconvénients par rapport aux techniques existantes.