`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.

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

- group around Johannes Buchmann.
- George Havas
- Gerold Jäger
- Erich Kaltofen
- Daniele Micciancio
- group around C.P. Schnorr.
- Victor Shoup, whose portable Number Theory Library contains high performance implementations of LLL.
- Michael Schneider
- Denis Simon
- Damien Stehlé
- Arne Storjohann