A lattice is a repeating grid of points in n-dimensional space. It is being generated by integer multiples of some basis vectors.

To represent lattices we write the basis vectors in coordinates with respect to the Cartesian coordinates. Then we represent the lattice as a matrix of basis vector coefficients

    B = matrix([[1, 2, 3], [0, 1, 2], [0, 0, 1]])

There are many different bases for the same lattice. For example the same lattice is given by

    matrix([[1, 0, 0], [0, 1, 0], [0, 0, 1]])

The LLL algorithm, named after its inventors Lenstra, Lenstra, and Lovasz, computes a basis of the lattice that has relatively short vectors. We only need the first (shortest) vector in this basis.

To quantify this, LLL finds a vector that is within a factor of 2^n/2 of the shortest vector. This is pretty loose, but good enough for our purposes.

Matrices in Sage have an LLL method that runs the LLL algorithm.