An upper bound on the average number of iterations of the LLL algorithm (Q1314406)

The authors establish an upper bound \(O(n^ 2\log n)\) for the average number of iterations of the LLL algorithm of \textit{A. K. Lenstra}, \textit{H. W. Lenstra} and \textit{L. Lovász} [Math. Ann. 261, 515-534 (1982; Zbl 0488.12001)] on \(n\)-dimensional lattices. It is deduced from estimates for the number of iterations involving the minimal and maximal length of the vectors of an orthogonalization of the input basis and also the minimum of the lattice. The result is initially proved for lattices with uniformly distributed input bases of vectors of length at most one. This is then followed by a transfer from the continuous model to a discrete model of integer lattices.