An Average-Case Analysis of the Gaussian Algorithm for Lattice Reduction
- 1 December 1997
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 6 (4) , 397-433
- https://doi.org/10.1017/s0963548397003258
Abstract
The Gaussian algorithm for lattice reduction in dimension 2 is analysed under its standard version. It is found that, when applied to random inputs in a continuous model, the complexity is constant on average, its probability distribution decays geometrically, and the dynamics are characterized by a conditional invariant measure. The proofs make use of connections between lattice reduction, continued fractions, continuants, and functional operators. Analysis in the discrete model and detailed numerical data are also presented.Keywords
This publication has 0 references indexed in Scilit: