DMTCS Proceedings, 2007 Conference on Analysis of Algorithms, AofA 07

Font Size:  Small  Medium  Large

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

Valid XHTML 1.0 Transitional