An Average-case Analysis of the Gaussian Algorithm for Lattice Reduction
Overview & Synopsis
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.
Indexed from repository: HAL Open Science
(
hal.science)
Keyboard Shortcuts:
← / → for pages • + / - for zoom • 0 to fit width
Powered by Mozilla PDF.js v3.11
Document Information
| Document Title | An Average-case Analysis of the Gaussian Algorithm for Lattice Reduction |
|---|---|
| Author / Organization | Hervé Daudé, Philippe Flajolet, Brigitte Vallée |
| Subject & Discipline | Multidisciplinary Academic Open Research |
| Categories | Science & Mathematics |
| Publication Year | 1996 |
| License / Rights | Open Access / Creative Commons |
| Resource Verification | Listed PDF (Verification Pending) |
| Original Host Website |
HAL Open Science
(hal.science)
|
| File Format | application/pdf (Portable Document Format) |
| Language | EN |
| Catalog ID | DOC-116091 |
| Original Source Link | Visit Source Page on hal.science » |