Skip to Main content Skip to Navigation
Master thesis

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
Abstract : 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.
Complete list of metadata
Contributor : Vincent Neiger <>
Submitted on : Thursday, January 8, 2015 - 10:37:57 PM
Last modification on : Friday, February 26, 2021 - 3:28:07 PM
Long-term archiving on: : Friday, September 11, 2015 - 6:23:45 AM


  • HAL Id : hal-01101550, version 1



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



Record views


Files downloads