Lenstra–Lenstra–Lovász lattice basis reduction algorithm
Encyclopedia
The LLL-reduction algorithm (Lenstra–Lenstra–Lovász lattice basis reduction) is a polynomial time lattice reduction
algorithm
invented by Arjen Lenstra
, Hendrik Lenstra
and László Lovász
in 1982, see . Given as input a basis
with n-dimensional integer coordinates, for a lattice
L in Rn with
, the LLL algorithm outputs an LLL-reduced (short, nearly orthogonal) lattice basis in time
.
where B is the largest of the lengths of the
under the Euclidean norm.
The original applications were to give polynomial time algorithms for factorizing polynomials with rational coefficients into irreducible polynomials, for finding simultaneous rational approximations to real numbers, and for solving the integer linear programming problem
in fixed dimensions.
with its Gram–Schmidt process
orthogonal basis,
define
, for any 
.
Then the basis
is LLL-reduced if there exists a parameter 
in (0.25,1] such that the following holds:
Lattice reduction
In mathematics, the goal of lattice basis reduction is given an integer lattice basis as input, to find a basis with short, nearly orthogonal vectors. This is realized using different algorithms, whose running time is usually at least exponential in the dimension of the lattice.-Nearly...
algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
invented by Arjen Lenstra
Arjen Lenstra
Arjen Klaas Lenstra is a Dutch mathematician. He studied mathematics at the University of Amsterdam.He is currently a professor at the EPFL , in the Laboratory for Cryptologic Algorithms, and...
, Hendrik Lenstra
Hendrik Lenstra
Hendrik Willem Lenstra, Jr. is a Dutch mathematician.-Biography:Lenstra received his doctorate from the University of Amsterdam in 1977 and became a professor there in 1978...
and László Lovász
László Lovász
László Lovász is a Hungarian mathematician, best known for his work in combinatorics, for which he was awarded the Wolf Prize and the Knuth Prize in 1999, and the Kyoto Prize in 2010....
in 1982, see . Given as input a basis
Basis (linear algebra)
In linear algebra, a basis is a set of linearly independent vectors that, in a linear combination, can represent every vector in a given vector space or free module, or, more simply put, which define a "coordinate system"...
with n-dimensional integer coordinates, for a latticeLattice (group)
In mathematics, especially in geometry and group theory, a lattice in Rn is a discrete subgroup of Rn which spans the real vector space Rn. Every lattice in Rn can be generated from a basis for the vector space by forming all linear combinations with integer coefficients...
L in Rn with
, the LLL algorithm outputs an LLL-reduced (short, nearly orthogonal) lattice basis in time.where B is the largest of the lengths of the
under the Euclidean norm.The original applications were to give polynomial time algorithms for factorizing polynomials with rational coefficients into irreducible polynomials, for finding simultaneous rational approximations to real numbers, and for solving the integer linear programming problem
Linear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
in fixed dimensions.
LLL reduction
The precise definition of LLL-reduced is as follows: Given a basisBasis (linear algebra)
In linear algebra, a basis is a set of linearly independent vectors that, in a linear combination, can represent every vector in a given vector space or free module, or, more simply put, which define a "coordinate system"...
with its Gram–Schmidt process
Gram–Schmidt process
In mathematics, particularly linear algebra and numerical analysis, the Gram–Schmidt process is a method for orthonormalising a set of vectors in an inner product space, most commonly the Euclidean space Rn...
orthogonal basis,
define
, for any .Then the basis
is LLL-reduced if there exists a parameter in (0.25,1] 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 (0.25,1).
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.
LLL Algorithm
The following description is based on , but currently is incorrect.
INPUT:
a lattice basis 
,
parameter 
with 
PROCEDURE:
Perform Gram-Schmidt:-
- for
from 
to 
do
-
- for
from 
to 
do
-
- end for
-
-
- end for
-
(k is the stage at which the vectors 
are reduced according to size-reduced property 1.) - if
then execute reduction subroutine RED(k,k-1):
- for
from 
to 
do
-
-
- for
from 
to 
do
-
- end for
-
-
- end for
- for
- end if
- Calculate
for 1 
and 
for 
from 1 to 
- while
do
- Length reduce
and correct 
according to reduction subroutine in step 4, for 
from 1 till 
- if
then
- Exchange
and 
-
:= max 
- Exchange
- else
-
- end if
- Length reduce
- end while
OUTPUT: LLL reduced basis
Example
The following presents an example due to W. Bosma.
INPUT:
Let a lattice basis
, be given by the columns of
Then according to the LLL algorithm we obtain the following:
1.
2.For
DO:
2.1.For
set 
and
2.2
3.
4.Here the step 4 of the LLL algorithm is skipped as size-reduced property holds for
5.For
and for 
calculate 
and 
:
hence
and
hence
and
6.While
DO
6.1 Length reduce
and correct 
and 
according to reduction subroutine in step 4:
For
EXECUTE reduction subroutine RED(3,1):
i.
and 
ii.
iii.Set
For
EXECUTE reduction subroutine RED(3,2):
i.
and 
ii.Set
iii.
6.2 As
takes place, then
6.2.1 Exchange
and 
6.2.2
:= 2
Apply a SWAP, continue algorithm with the lattice basis, which is given by columns
Implement the algorithm steps again.
1.
2.
3.
.
4.
.
5.For
EXECUTE reduction subroutine RED(2,1):
i.
and 
ii.Set
6. As
takes place, then
7. Exchange
and 
OUTPUT: LLL reduced basis
Applications
The LLL algorithm has found numerous other applications in MIMOMIMOIn radio, multiple-input and multiple-output, or MIMO , is the use of multiple antennas at both the transmitter and receiver to improve communication performance. It is one of several forms of smart antenna technology...
detection algorithms and cryptanalysis of public-key encryption schemes: knapsack cryptosystemsNaccache-Stern knapsack cryptosystemNote: this is not to be confused with the Naccache–Stern cryptosystem based on the higher residuosity problem.The Naccache–Stern Knapsack Cryptosystem is an atypical public-key cryptosystem developed by David Naccache and Jacques Stern in 1997. This cryptosystem is deterministic, and hence is not...
, RSA with particular settings, NTRUEncryptNTRUEncryptThe NTRUEncrypt public key cryptosystem, also known as the NTRU encryption algorithm, is a lattice-based alternative to RSA and ECC and is based on the shortest vector problem in a lattice...
, 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 algorithmInteger relation algorithmAn integer relation between a set of real numbers x1, x2, ..., xn is a set of integers a1, a2, ..., an, not all 0, such thata_1x_1 + a_2x_2 + \cdots + a_nx_n = 0.\,...
s. For example, if it is believed that r=1.618034 is a (slightly rounded) root to a quadratic equationQuadratic equationIn mathematics, a quadratic equation is a univariate polynomial equation of the second degree. A general quadratic equation can be written in the formax^2+bx+c=0,\,...
with integer coefficients, one may apply the LLL reduction to the lattice in
spanned by 
and 
. The first vector in the reduced basis will be an integer linear combinationLinear combinationIn mathematics, a linear combination is an expression constructed from a set of terms by multiplying each term by a constant and adding the results...
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 polynomialPolynomialIn mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
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 1.6180339887…(The Golden Ratio)Golden ratioIn mathematics and the arts, two quantities are in the golden ratio if the ratio of the sum of the quantities to the larger quantity is equal to the ratio of the larger quantity to the smaller one. The golden ratio is an irrational mathematical constant, approximately 1.61803398874989...
Implementations
LLL is implemented in- Arageli as the function lll_reduction_int
- fpLLL as a stand-alone implementation
- GAPGAP computer algebra systemGAP is a computer algebra system for computational discrete algebra with particular emphasis on computational group theory.-History:...
as the function LLLReducedBasis - LiDIA as the function/method lll in the LT package
- Macaulay2Macaulay2Macaulay2 is a free computer algebra system developed by Daniel Grayson and Michael Stillman for computation in commutative algebra and algebraic geometry. Stillman, along with Dave Bayer had authored the predecessor, Macaulay. Macaulay2 uses its own high level programming language, intended to...
as the function LLL in the package LLLBases - MagmaMagma computer algebra systemMagma is a computer algebra system designed to solve problems in algebra, number theory, geometry and combinatorics. It is named after the algebraic structure magma...
as the functions LLL and LLLGram (taking a gram matrix) - Maple as the function IntegerRelations[LLL]
- MathematicaMathematicaMathematica is a computational software program used in scientific, engineering, and mathematical fields and other areas of technical computing...
as the function LatticeReduce - Number Theory Library (NTL) as the function LLL
- PARI/GPPARI/GPPARI/GP is a computer algebra system with the main aim of facilitating number theory computations. It is free software; versions 2.1.0 and higher are distributed under the GNU General Public License...
as the function qflll - Sage as the method LLL driven by fpLLL and NTL
-
