Lattice reduction

This is realized using different algorithms, whose running time is usually at least exponential in the dimension of the lattice.

This compares the product of the lengths of the basis vectors with the volume of the parallelepiped they define.

In the fully dimensional case where the number of basis vectors is equal to the dimension of the space they occupy, this matrix is square, and the volume of the fundamental parallelepiped is simply the absolute value of the determinant of this matrix

If the number of vectors is less than the dimension of the underlying space, then volume is

, this volume is the same (up to sign) for any basis, and hence is referred to as the determinant of the lattice

The orthogonality defect is the product of the basis vector lengths divided by the parallelepiped volume; From the geometric definition it may be appreciated that

However, there exist polynomial time algorithms to find a basis with defect

where c is some constant depending only on the number of basis vectors and the dimension of the underlying space (if different)[citation needed].

This is a good enough solution in many practical applications[citation needed].

For a basis consisting of just two vectors, there is a simple and efficient method of reduction closely analogous to the Euclidean algorithm for the greatest common divisor of two integers.

Although determining the shortest basis is possibly an NP-complete problem, algorithms such as the LLL algorithm[2] can find a short (not necessarily shortest) basis in polynomial time with guaranteed worst-case performance.

LLL is widely used in the cryptanalysis of public key cryptosystems.

When used to find integer relations, a typical input to the algorithm consists of an augmented

The LLL algorithm for computing a nearly-orthogonal basis was used to show that integer programming in any fixed dimension can be done in polynomial time.