Polynomial LLL algorithm and applications
Algorithme LLL polynomial et applications
Résumé
In this report, we study the polynomial LLL algorithm and several of its applications. This algorithm was first published as such by A. K. Lenstra in 1985 ; it was then rediscovered by Paulus in 1996, but it was already more or less known as Popov normal form in linear algebra since 1969. A matrix M with coefficients in K[X] being given, it amounts to find an invertible matrix U such that MU has minimal (in a precise sense) coefficients.
We implemented the polynomial LLL algorithm and tested it on two classes of examples, one with K a finite field of small characteristic (using machine integers), the other one with K a finite field of large characteristic (using GMP integers).
Then, we studied several applications of this algorithm : we implemented an algorithm for changing the monomial ordering of a Gröbner basis of an ideal of K[X,Y] ; we studied an algorithm for the list-decoding of Reed-Solomon codes, derived from Boneh's algorithm for CRT list-decoding ; finally, we studied an algorithm for bivariate polynomial factorization over a finite field, derived from van Hoeij's algorithm over Z.
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].