Applications[edit]

An early successful application of the LLL algorithm was its use by Andrew Odlyzko and Herman te Riele in disproving Mertens conjecture.[5]


The LLL algorithm has found numerous other applications in MIMO detection algorithms[6] and cryptanalysis of public-key encryption schemes: knapsack cryptosystems, RSA with particular settings, NTRUEncrypt, and so forth. The algorithm can be used to find integer solutions to many problems.[7]


In particular, the LLL algorithm forms a core of one of the integer relation algorithms. For example, if it is believed that r=1.618034 is a (slightly rounded) root to an unknown quadratic equation with integer coefficients, one may apply LLL reduction to the lattice in spanned by and . The first vector in the reduced basis will be an integer linear combination of these three, thus necessarily of the form ; but such a vector is "short" only if a, b, c are small and is even smaller. Thus the first three entries of this short vector are likely to be the coefficients of the integral quadratic polynomial which has r as a root. In this example the LLL algorithm finds the shortest vector to be [1, -1, -1, 0.00025] and indeed has a root equal to the golden ratio, 1.6180339887....

Examples[edit]

Example from Z3[edit]

Let a lattice basis , be given by the columns of

as the function lll_reduction_int

Arageli

as a stand-alone implementation

fpLLL

as the function fmpz_lll

FLINT

as the function LLLReducedBasis

GAP

as the function LLL in the package LLLBases

Macaulay2

as the functions LLL and LLLGram (taking a gram matrix)

Magma

as the function IntegerRelations[LLL]

Maple

as the function LatticeReduce

Mathematica

as the function LLL

Number Theory Library (NTL)

as the function qflll

PARI/GP

as the function analysis.get_lll_reduced_lattice

Pymatgen

as the method LLL driven by fpLLL and NTL

SageMath

in the 'archive of formal proofs' entry LLL_Basis_Reduction. This code exports to efficiently executable Haskell.[11]

Isabelle/HOL

LLL is implemented in

Coppersmith method

Napias, Huguette (1996). . Journal de Théorie des Nombres de Bordeaux. 8 (2): 387–396. doi:10.5802/jtnb.176.

"A generalization of the LLL algorithm over euclidean rings or orders"

Cohen, Henri (2000). A course in computational algebraic number theory. GTM. Vol. 138. Springer.  3-540-55640-0.

ISBN

(2002). Computational Excursions in Analysis and Number Theory. ISBN 0-387-95444-9.

Borwein, Peter

Luk, Franklin T.; Qiao, Sanzheng (2011). . Linear Algebra and Its Applications. 434 (11): 2296–2307. doi:10.1016/j.laa.2010.04.003.

"A pivoted LLL algorithm"

Hoffstein, Jeffrey; Pipher, Jill; Silverman, J.H. (2008). An Introduction to Mathematical Cryptography. Springer.  978-0-387-77993-5.

ISBN