Algorithme LLL polynomial et applications

Jean-René Reinhard 1
1 SPACES - Solving problems through algebraic computation and efficient software
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Résumé : Dans ce rapport, on étudie l'algorithme LLL polynomial et quelques-unes de ses applications. Cet algorithme, publié par Lenstra en 1985, redécouvert par Paulus en 1996 et existant plus ou moins sous le nom de forme normale de Popov en algèbre linéaire depuis 1969, consiste étant donné une matrice M à coefficients dans K[X], à trouver une matrice U inversible telle que MU ait des coefficients en un certain sens minimaux. Nous avons réalisé une implantation de l'algorithme LLL polynomial, que nous avons testée et évaluée sur des exemples avec K fini de petite caractéristique (entiers machine) et de grande caractéristique (entiers GMP). Nous nous sommes ensuite intéressés à des applications de cet algorithme : un algorithme de changement d'ordre pour une base de Gröbner d'un idéal de K[X,Y] que nous avons implanté ; un algorithme de décodage en liste des codes de Reed-Solomon inspiré par l'algorithme de Boneh dans le cadre des codes CRT ; enfin, un algorithme de factorisation de polynômes sur K[X,Y], inspiré de l'algorithme de van Hoeij sur Z[X].
Type de document :
Mémoires d'étudiants -- Hal-inria+
Informatique [cs]. 2003
Liste complète des métadonnées

https://hal.inria.fr/hal-01101550
Contributeur : Vincent Neiger <>
Soumis le : jeudi 8 janvier 2015 - 22:37:57
Dernière modification le : jeudi 11 janvier 2018 - 06:20:00
Document(s) archivé(s) le : vendredi 11 septembre 2015 - 06:23:45

Identifiants

  • HAL Id : hal-01101550, version 1

Collections

Citation

Jean-René Reinhard. Algorithme LLL polynomial et applications. Informatique [cs]. 2003. 〈hal-01101550〉

Partager

Métriques

Consultations de la notice

353

Téléchargements de fichiers

48