# 50.33 LLLReducedBasis

`LLLReducedBasis([L],vectors[,y][,"linearcomb"])`

`LLLReducedBasis` provides an implementation of the LLL lattice reduction algorithm by Lenstra, Lenstra and Lovaccent19 asz (see~LLL82, Poh87). The implementation follows the description on pages 94f. in~Coh93.

`LLLReducedBasis` returns a record whose component `basis` is a list of LLL reduced linearly independent vectors spanning the same lattice as the list vectors.

L must be a lattice record whose scalar product function is stored in the component `operations.NoMessageScalarProduct` or `operations.ScalarProduct`. It must be a function of three arguments, namely the lattice and the two vectors. If no lattice L is given the standard scalar product is taken.

In the case of option `"linearcomb"`, the record contains also the components `relations` and `transformation`, which have the following meaning. `relations` is a basis of the relation space of vectors, i.e., of vectors x such that `x * vectors` is zero. `transformation` gives the expression of the new lattice basis in terms of the old, i.e., `transformation * vectors` equals the `basis` component of the result.

Another optional argument is y, the ``sensitivity'' of the algorithm, a rational number between frac{1}{4} and 1 (the default value is frac{3}{4}).

(The function LLLReducedGramMat computes an LLL reduced Gram matrix.)

```    gap> vectors:= [ [ 9, 1, 0, -1, -1 ], [ 15, -1, 0, 0, 0 ],
>                [ 16, 0, 1, 1, 1 ], [ 20, 0, -1, 0, 0 ],
>                [ 25, 1, 1, 0, 0 ] ];;
gap> LLLReducedBasis( vectors, "linearcomb" );
rec(
basis :=
[ [ 1, 1, 1, 1, 1 ], [ 1, 1, -2, 1, 1 ], [ -1, 3, -1, -1, -1 ],
[ -3, 1, 0, 2, 2 ] ],
relations := [ [ -1, 0, -1, 0, 1 ] ],
transformation :=
[ [ 0, -1, 1, 0, 0 ], [ -1, -2, 0, 2, 0 ], [ 1, -2, 0, 1, 0 ],
[ -1, -2, 1, 1, 0 ] ] ) ```

GAP 3.4.4
April 1997