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 ] ) 

Previous Up Top Next
Index