LLL - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

Online Help

All Products    Maple    MapleSim

IntegerRelations

 LLL
 find a reduced basis of a lattice

 Calling Sequence LLL(lvect, integer)

Parameters

 lvect - list, set, or rtable of lists or Vectors, or a Matrix integer - (optional) literal name

Description

 • The LLL(lvect) command finds a reduced basis (in the sense of Lovasz) of the lattice specified by the (row) vectors of lvect using the LLL algorithm.
 • If the lattice is generated by vectors with integer coefficients and the option integer is specified, then the reduction is performed using only integer arithmetic. This version is sometimes faster than the default version, which uses rational arithmetic.
 • This function requires that the dimension of the subspace generated by the vectors equals the number of vectors.
 • The internal working precision of the LLL command corresponds to the value of Digits. For best results, the same value of Digits should be used with which the input approximation was obtained.

Examples

 > $\mathrm{with}\left(\mathrm{IntegerRelations}\right):$
 > $\mathrm{LLL}\left(\left[\left[1,2,3\right],\left[2,1,6\right]\right]\right)$
 $\left[\left[{0}{,}{-3}{,}{0}\right]{,}\left[{1}{,}{-1}{,}{3}\right]\right]$ (1)
 > $\mathrm{LLL}\left(\left[\left[1,2,3\right],\left[2,1,6\right]\right],'\mathrm{integer}'\right)$
 $\left[\left[{0}{,}{-3}{,}{0}\right]{,}\left[{1}{,}{-1}{,}{3}\right]\right]$ (2)
 > $\mathrm{LLL}\left(\mathrm{Matrix}\left(\left[\left[1,2,3\right],\left[-1,0,1\right],\left[0,1,1\right]\right]\right)\right)$
 $\left[\begin{array}{ccc}{-1}& {0}& {1}\\ {0}& {1}& {1}\\ {0}& {-1}& {1}\end{array}\right]$ (3)

References

 Lenstra, A.K.; Lenstra, H.W.; and Lovasz, L. "Factoring Polynomials with Rational Coefficients." Math. Ann., Vol. 261. (1982): 515-534.

 See Also