Lenstra–Lenstra–Lovász lattice basis reduction algorithm

The LLL algorithm is a named after Arjen Lenstra, Hendrik Lenstra and László Lovász algorithm that computes a base made as short as possible vectors for a grid. These vectors are approximations for the shortest linearly independent vectors of the lattice. For his discovery of the LLL algorithm was the first effective lattice reduction algorithm.

Short lattice vectors

A lattice basis can be specified as a matrix. The shortest lattice vector minimizes the norm of the vector, not all are equal to 0. The LLL algorithm performs this minimization by regarding the Euclidean norm.

LLL - bases

Definition

Usually LLL - bases are defined by their QR decomposition. An LLL - basis for reduction factor is defined by the following two properties:

Here are the entries of the matrix. It is assumed that the QR decomposition is performed by such a way that includes the diagonal of any negative elements.

The reduction factor indicates the amount of reduction, the closer it is to 1, the shorter are the vectors of the reduced basis. For it is not known whether there is an efficient algorithm.

Properties

LLL reduced bases approximate the shortest vectors with approximation factor, which is exponential in the number of vectors. In the following,. Obviously. Of th LLL reduced vector approximates the gradually -th minimum as follows: wherein the -th successive minimum the length of the shortest -th vector is linearly independent of any amount less vectors.

Algorithm

The algorithm follows directly from the definition: Force column by column, that a LLL - based. Length reduction can easily bring. Only the LLL property is complicated because it brings indirectly widely separated columns in relationship. Therefore it is necessary to swap columns and then go back one step.

Length reduction

The matrix is ​​an upper triangular matrix with positive diagonal. The aim of the reduction in length is ( in absolute terms ) to make all non- diagonal elements small as possible without changing the lattice. Each row of the following structure: zero or more zeros, the diagonal element, zero or more other elements. The zeros are fitted with the smallest possible amount. The LLL property ensures that the diagonal element can not be too large. The length reduction causes now for all of the following that they are in absolute terms the highest half as large as the diagonal element. This can be through bringing about that the column that contains the corresponding diagonal element, so often added for each to large non - diagonal element or subtracted until the excessive element of magnitude is minimal. The following algorithm reduces the length - th column of:

Here, the -th column vector of and the rounding function, which rounds to the nearest integer. It is important that the second step is carried out with decreasing and not increasing.

Applications

The algorithm finds application in many areas, partly in a modified version. It can also be applied to isometrically isomorphic to lattices, in which the reduction is then performed on the local scalar product. A rather unerwaretes example of this is the algorithm of Unger from the group theory, which is used for finding the irreducible characters of a group.