Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-25T09:02:43.538Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  01 December 1997

HERVÉ DAUDÉ ,
PHILIPPE FLAJOLET  and
BRIGITTE VALLÉE
HERVÉ DAUDÉ
Affiliation:
LATP, URA 225, Département de Mathématiques, CMI, Université de Provence, 39 rue F.Joliot-Curie F-13453 Marseille Cedex 13, France; (e-mail: [email protected])
PHILIPPE FLAJOLET
Affiliation:
Algorithms Project, INRIA-Rocquencourt, F-78153 Le Chesnay, France; (e-mail: [email protected])
BRIGITTE VALLÉE
Affiliation:
GREYC, Département d'Informatique, Université de Caen, F-14032 Caen, France; (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

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.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 6 , Issue 4 , December 1997 , pp. 397 - 433
Copyright
1997 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)