The lattice reduction algorithm of Gauss: an average case analysis
Brigitte Vallée, Philippe Flajolet · 2002
The lattice reduction algorithm of Gauss is shown to have an average-case complexity that is asymptotic to a constant. The analysis makes use of elementary properties of continued fractions and of linear fractional transformations.>