Lattice reduction in two dimensions: analyses under realistic probabilistic models
B. Vallée, A. Vera
Abstract
The Gaussian algorithm for lattice reduction in dimension 2 is precisely analysed under a class of realistic probabilistic models, which are of interest when applying the Gauss algorithm ``inside'' the LLL algorithm. The proofs deal with the underlying dynamical systems and transfer operators. All the main parameters are studied: execution parameters which describe the behaviour of the algorithm itself as well as output parameters, which describe the geometry of reduced bases.
Full Text: GZIP Compressed PostScript PostScript PDF