Brigitte Vallée ; Antonio Vera - Lattice reduction in two dimensions: analyses under realistic probabilistic models

dmtcs:3549 - Discrete Mathematics & Theoretical Computer Science, January 1, 2007, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07) - https://doi.org/10.46298/dmtcs.3549
Lattice reduction in two dimensions: analyses under realistic probabilistic modelsConference paper

Authors: Brigitte Vallée 1; Antonio Vera 1

  • 1 Equipe AMACC - Laboratoire GREYC - UMR6072


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.

https://doi.org/10.46298/dmtcs.3549
Source: HAL:hal-01184797v1
Volume: DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)
Section: Proceedings
Published on: January 1, 2007
Imported on: May 10, 2017
Keywords: [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], [en] Dynamical analysis of Algorithms., Dynamical Systems, probabilistic analysis of algorithms, Lattice Reduction, Gauss' algorithm, LLL algorithm, Euclid's algorithm

3 Documents citing this article

Share and export

Consultation statistics

This page has been seen 380 times.
This article's PDF has been downloaded 388 times.