Complexity of the Havas, Majewski, Matthews LLL Hermite Normal Form algorithm

Wilberd van der Kallen

We show that the integers in the HMM LLL HNF algorithm have bit length O(m.log(m.B)), where m is the number of rows and B is the maximum square length of a row of the input matrix.…