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.
Type de document :
Rapport
[Research Report] RR-2798, INRIA. 1996
Liste complète des métadonnées

https://hal.inria.fr/inria-00073892
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 14:00:22
Dernière modification le : vendredi 25 mai 2018 - 12:02:02
Document(s) archivé(s) le : jeudi 24 mars 2011 - 13:14:22

Fichiers

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

174

Téléchargements de fichiers

178