Implementations of extended LLL

In systems like GP/PARI one uses an implementation of the LLL lattice reduction algorithm which allows dependent vectors and which also returns a transformation matrix. However, no good complexity analysis is available for their qflll algorithm (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 mathnf with 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" extendedlll to 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, makes qflll or extendedlll slower 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.

GCD based HNF

One may use the same principles to avoid coefficient explosion in a straightforward GCD based Hermite Normal Form algorithm. No, it is not the extended GCD which causes the coefficient explosion observed in naive implementations. No complicated countermeasures are required. Just a better understanding of the right order in which to compute. Say one aims for a lower triangular Hermite Normal Form, i.e. the row space is preserved. Then the principle is that one should not allow a new row to enter the computation before the matrix above it is in Hermite Normal Form. Triangular form is not good enough. This goes back to Tsu-Wu J. Chou and George E. Collins: Algorithms for the Solution of Systems of Linear Diophantine Equations. SIAM J. Comput. 11(4): 687-708(1982). Their description of the algorithm does not encourage correct implementation in modern systems, which may explain why their (superior?) method is not used more often. We illustrate the straightforward algorithm in a Mathematica notebook, also viewable as PostScript. Or see the underlying code in Mathematica InputForm. For a version in C, using Victor Shoup's NTL, peek at this directory.

For some work in this area, try the following home pages.

group around Johannes Buchmann.

group around C.P. Schnorr.

Victor Shoup, whose portable Number Theory Library contains high performance implementations of LLL.

Wilberd van der Kallen