Abstract FR:

Le probleme de la reduction est d'un grand interet en particulier par ses nombreuses application en theorie algorithmique des nombres, en optimisation entiere ou encore en cryptographie. En dimension 2, il existe un algorithme de reduction du a gauss. En dimension n, le probleme a interesse des mathematiciens tels que hermite et minkowski. Cependant, ce n'est que depuis 1982 qu'il existe un algorithme d'approximation polynomial qui construit une base reduite (au sens de t-lovasz) dans un reseau : l'algorithme lll(t). Dans cette these, nous considerons plusieurs nouvelles definitions de bases reduites et comparons ces reductions a celle de t-lovasz. Les nouvelles reductions sont a priori moins fortes mais la qualite des bases de sortie reste similaire a celle des bases lll-reduites, alors que les nouveaux algorithmes de reduction sont en moyenne plus rapides. Les chapitres 2-5 etudient le comportement des differents algorithmes de reduction sur des reseaux aleatoires. En analysant les agorithmes de reduction dans le pire des cas et en moyenne sur les bases du modele uniforme, nous fournissons une etude comparative de leurs comportements et montrons que les nouveaux algorithmes sont plus rapides. Cette etude est completee (chapitre 7) par des exprerimentations qui confirment nos resultats sur des reseaux aleatoires provenant de problemes reels. Dans le chapitre 6, nous considerons la complexite de l'algorithme lll, lorsque son parametre d'approximation t prend sa valeur optimale 1 (la meilleure base reduite est alors construite). C'etait un probleme ouvert auquel nous apportons ici une reponse partielle : l'algorithme lll optimal reste polynomiale en la taille de la base lorsque la dimension n du reseau ext fixe.