# 50.34 LLLReducedGramMat

`LLLReducedGramMat( G [,y] )`

`LLLReducedGramMat` 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.

Let G the Gram matrix of the vectors (b_1, b_2, ldots, b_n); this means G is either a square symmetric matrix or lower triangular matrix (only the entries in the lower triangular half are used by the program).

`LLLReducedGramMat` returns a record whose component `remainder` is the Gram matrix of the LLL reduced basis corresponding to (b_1, b_2, ldots, b_n). If G was a lower triangular matrix then also the `remainder` component is a lower triangular matrix.

The result record contains also the components `relations` and `transformation`, which have the following meaning.

`relations` is a basis of the space of vectors (x_1,x_2,ldots,x_n) such that sum_{i=1}^n x_i b_i is zero, and `transformation` gives the expression of the new lattice basis in terms of the old, i.e., `transformation` is the matrix T such that T cdot <G> cdot T^{tr} is the `remainder` component of the result.

The optional argument y denotes the ``sensitivity of the algorithm, it must be a rational number between frac{1}{4} and 1; the default value is <y> = frac{3}{4}.

(The function LLLReducedBasis computes an LLL reduced basis.)

```    gap> g:= [ [ 4, 6, 5, 2, 2 ], [ 6, 13, 7, 4, 4 ],
>    [ 5, 7, 11, 2, 0 ], [ 2, 4, 2, 8, 4 ], [ 2, 4, 0, 4, 8 ] ];;
gap> LLLReducedGramMat( g );
rec(
remainder :=
[ [ 4, 2, 1, 2, -1 ], [ 2, 5, 0, 2, 0 ], [ 1, 0, 5, 0, 2 ],
[ 2, 2, 0, 8, 2 ], [ -1, 0, 2, 2, 7 ] ],
relation := [  ],
transformation :=
[ [ 1, 0, 0, 0, 0 ], [ -1, 1, 0, 0, 0 ], [ -1, 0, 1, 0, 0 ],
[ 0, 0, 0, 1, 0 ], [ -2, 0, 1, 0, 1 ] ],
scalarproducts := [ , [ 1/2 ], [ 1/4, -1/8 ], [ 1/2, 1/4, -2/25 ],
[ -1/4, 1/8, 37/75, 8/21 ] ],
bsnorms := [ 4, 4, 75/16, 168/25, 32/7 ] ) ```

GAP 3.4.4
April 1997