qflllalgorithm (and similar algorithms). The method of the original LLL paper does not apply in any obvious way. That is, the original space bounds are much better than just polynomial, and it is not clear how to obtain such good bounds for the entries of the transformation matrix in the presence of dependent vectors. For all we know those entries may get out of hand in rare cases. To get back to a situation with a decent complexity estimate, one may preprocess with the Chou Collins HNF algorithm or with the LLL Hermite Normal Form algorithm of Havas, Majewski, Matthews. In GP/PARI 2.1.3 this is
mathnfwith flag=4. But note that one now has two estimates: one for the the preprocessing stage, one for the final LLL stage.
More directly, one may employ the related
"extended LLL algorithm"
which our complexity analysis also applies,
and which has just one stage, leading to a better estimate. Our
extendedlll uses the size reduction mechanisms of the original
LLL algorithm to
limit both the size of the vectors and the size of the transformation matrix.
One may choose what requirements to put on the transformation
matrix and on the new basis. (Reduce all the way or just keep
entries within bounds.)
The fact that it is an extended algorithm, in the sense
that one also computes the transformation matrix,
than the MLLL of Pohst.
We have several implementations of this extended LLL in the Mathematica language. There is Package Version 1.10.2 or a verbose version of the same code. To document the principles, there is the shorter and more readable code. A related Mathematica package is ShortestVector.
We also have implementations of extended LLL in the GP/PARI language ( implementation for GP/PARI 2.1.4). If you prefer it compiled, see the C source, which also requires the GP/PARI system. If one wants an MLLL with integer arithmetic, without transformation matrix, but to which our complexity analysis applies, then we can offer an implementation of MLLL for GP/PARI 2.1.4 and a C source for MLLL. In contrast with some other implementations of MLLL we have been careful to use only auxiliary integers for which we have a good estimate.
For some work in this area, try the following home pages.
Wilberd van der Kallen