An Average-case Analysis of the Gaussian Algorithm for Lattice Reduction

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, the probability distribution decays geometrically, and the dynamics is 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.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00073892
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 2:00:22 PM
Last modification on : Friday, May 25, 2018 - 12:02:02 PM
Long-term archiving on : Thursday, March 24, 2011 - 1:14:22 PM

Identifiers

  • HAL Id : inria-00073892, version 1

Collections

Citation

Hervé Daudé, Philippe Flajolet, Brigitte Vallée. An Average-case Analysis of the Gaussian Algorithm for Lattice Reduction. [Research Report] RR-2798, INRIA. 1996. ⟨inria-00073892⟩

Share

Metrics

Record views

196

Files downloads

261