Factorization of Polynomials - Uses of LLL Algorithm

Uses of LLL Algorithm

The first polynomial time algorithm for factoring rational polynomials has been discovered by Lenstra, Lenstra and Lovász and is an application of Lenstra–Lenstra–Lovász lattice basis reduction algorithm, usually called "LLL algorithm". (Lenstra, Lenstra & Lovász 1982) Although theoretically faster in the worst case, their factorization algorithm is not efficient in practice and is not used on computers.

However LLL algorithm is used by the fastest factorization algorithm to lift a modular factorization to a factorization over the integers.

One variation of LLL factorization algorithm runs as follows: calculate a complex (or p-adic) root α of the polynomial P to high precision, then use the Lenstra–Lenstra–Lovász lattice basis reduction algorithm to find an approximate linear relation between 1, α, α2, α3, ... with integer coefficients, which with luck, is an exact linear relation and a polynomial factor of P. One can determine a bound for the precision that guarantees that this method produces either a factor, or an irreducibility proof.