The Lenstra–Lenstra–Lovász (LLL) lattice basis reduction algorithm is a
polynomial time
In theoretical 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 p ...
lattice reduction
In mathematics, the goal of lattice basis reduction is to find a basis with short, nearly orthogonal vectors when given an integer lattice basis as input. This is realized using different algorithms, whose running time is usually at least expon ...
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
invented by
Arjen Lenstra
Arjen Klaas Lenstra (born 2 March 1956, in Groningen) is a Dutch mathematician, cryptographer and computational number theorist. He is a professor emeritus from the École Polytechnique Fédérale de Lausanne (EPFL) where he headed of the Labora ...
,
Hendrik Lenstra
Hendrik Willem Lenstra Jr. (born 16 April 1949, Zaandam) is a Dutch mathematician.
Biography
Lenstra received his doctorate from the University of Amsterdam in 1977 and became a professor there in 1978. In 1987, he was appointed to the faculty o ...
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 ...
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 (mathematics), orthogonality is the generalization of the geometric notion of ''perpendicularity''. Although many authors use the two terms ''perpendicular'' and ''orthogonal'' interchangeably, the term ''perpendic ...
) lattice basis in time
where
is the largest length of
under the
Euclidean norm
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are ''Euclidean spaces'' ...
, 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
In mathematics, particularly linear algebra and numerical analysis, the Gram–Schmidt process or Gram-Schmidt algorithm is a way of finding a set of two or more vectors that are perpendicular to each other.
By technical definition, it is a metho ...
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 i ...
and
Herman te Riele in disproving
Mertens conjecture
In mathematics, the Mertens conjecture is the statement that the Mertens function M(n) is bounded by \pm\sqrt. Although now disproven, it had been shown to imply the Riemann hypothesis. It was conjectured by Thomas Joannes Stieltjes, in an 1885 ...
.
The LLL algorithm has found numerous other applications in
MIMO
In radio, multiple-input and multiple-output (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 wirel ...
detection algorithms 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.
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
In vascular plants, the roots are the plant organ, 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 bel ...
to an unknown
quadratic equation
In mathematics, a quadratic equation () is an equation that can be rearranged in standard form as
ax^2 + bx + c = 0\,,
where the variable (mathematics), variable represents an unknown number, and , , and represent known numbers, where . (If and ...
with integer coefficients, one may apply LLL reduction to the lattice in
spanned by
and