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

Previous Up Top Next
Index