The Lenstra–Lenstra–Lovász (LLL) lattice basis reduction algorithm is a
polynomial time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
lattice reduction algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
invented by
Arjen Lenstra,
Hendrik Lenstra and
László Lovász
László Lovász (; born March 9, 1948) is a Hungarian mathematician and professor emeritus at Eötvös Loránd University, best known for his work in combinatorics, for which he was awarded the 2021 Abel Prize jointly with Avi Wigderson. He wa ...
in 1982. Given a
basis with ''n''-dimensional integer coordinates, for a
lattice L (a discrete subgroup of R
''n'') with
, the LLL algorithm calculates an ''LLL-reduced'' (short, nearly
orthogonal
In mathematics, orthogonality is the generalization of the geometric notion of '' perpendicularity''.
By extension, orthogonality is also used to refer to the separation of specific features of a system. The term also has specialized meanings in ...
) lattice basis in time
where
is the largest length of
under the Euclidean norm, that is,
.
The original applications were to give polynomial-time algorithms for
factorizing polynomials with rational coefficients, for finding
simultaneous rational approximations to real numbers, and for solving the
integer linear programming problem in fixed dimensions.
LLL reduction
The precise definition of LLL-reduced is as follows: Given a
basis
define its
Gram–Schmidt process orthogonal basis
and the Gram-Schmidt coefficients
for any
.
Then the basis
is LLL-reduced if there exists a parameter
in such that the following holds:
# (size-reduced) For
. By definition, this property guarantees the length reduction of the ordered basis.
# (Lovász condition) For k = 2,3,..,n
.
Here, estimating the value of the
parameter, we can conclude how well the basis is reduced. Greater values of
lead to stronger reductions of the basis. Initially, A. Lenstra, H. Lenstra and L. Lovász demonstrated the LLL-reduction algorithm for
. Note that although LLL-reduction is well-defined for
, the polynomial-time complexity is guaranteed only for
in
.
The LLL algorithm computes LLL-reduced bases. There is no known efficient algorithm to compute a basis in which the basis vectors are as short as possible for lattices of dimensions greater than 4. However, an LLL-reduced basis is nearly as short as possible, in the sense that there are absolute bounds
such that the first basis vector is no more than
times as long as a shortest vector in the lattice,
the second basis vector is likewise within
of the second successive minimum, and so on.
Applications
An early successful application of the LLL algorithm was its use by
Andrew Odlyzko
Andrew Michael Odlyzko (Andrzej Odłyżko) (born 23 July 1949) is a Polish- American mathematician and a former head of the University of Minnesota's Digital Technology Center and of the Minnesota Supercomputing Institute. He began his career in ...
and
Herman te Riele
Hermanus Johannes Joseph te Riele (born 5 January 1947) is a Dutch mathematician at CWI in Amsterdam with a specialization in computational number theory. He is known for proving the correctness of the Riemann hypothesis for the first 1.5 billio ...
in disproving
Mertens conjecture.
The LLL algorithm has found numerous other applications in
MIMO
In radio, multiple-input and multiple-output, or MIMO (), is a method for multiplying the capacity of a radio link using multiple transmission and receiving antennas to exploit multipath propagation. MIMO has become an essential element of w ...
detection algorithms and cryptanalysis of
public-key encryption
Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...
schemes:
knapsack cryptosystems Knapsack cryptosystems are cryptosystems whose security is based on the hardness of solving the knapsack problem. They remain quite unpopular because simple versions of these algorithms have been broken for several decades. However, that type of cr ...
,
RSA
RSA may refer to:
Organizations Academia and education
* Rabbinical Seminary of America, a yeshiva in New York City
*Regional Science Association International (formerly the Regional Science Association), a US-based learned society
*Renaissance S ...
with particular settings,
NTRUEncrypt, and so forth. The algorithm can be used to find integer solutions to many problems.
In particular, the LLL algorithm forms a core of one of the
integer relation algorithm An integer relation between a set of real numbers ''x''1, ''x''2, ..., ''x'n'' is a set of integers ''a''1, ''a''2, ..., ''a'n'', not all 0, such that
:a_1x_1 + a_2x_2 + \cdots + a_nx_n = 0.\,
An integer relation algorithm is an algorithm fo ...
s. For example, if it is believed that ''r''=1.618034 is a (slightly rounded)
root
In vascular plants, the roots are the organs of a plant that are modified to provide anchorage for the plant and take in water and nutrients into the plant body, which allows plants to grow taller and faster. They are most often below the sur ...
to an unknown
quadratic equation
In algebra, a quadratic equation () is any equation that can be rearranged in standard form as
ax^2 + bx + c = 0\,,
where represents an unknown (mathematics), unknown value, and , , and represent known numbers, where . (If and then the equati ...
with integer coefficients, one may apply LLL reduction to the lattice in
spanned by
and