Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Lattice reduction in ...
Conference paper

Lattice reduction in two dimensions: analyses under realistic probabilistic models

Brigitte Vallée (1), Antonio Vera (1)
(1) Equipe AMACC - Laboratoire GREYC - UMR6072
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2006
Last modified on
March 31, 2025
Volume
DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)
Proceedings
DOI
10.46298/dmtcs.3549
License
https://about.hal.science/hal-authorisation-v1
Indicators
661
Views
615
Downloads

Lattice reduction in two dimensions: analyses under realistic probabilistic models

Brigitte Vallée (1), Antonio Vera (1)
(1) Equipe AMACC - Laboratoire GREYC - UMR6072
Abstract
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.
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]
  • Dynamical analysis of Algorithms.
  • Dynamical Systems
  • probabilistic analysis of algorithms
  • Lattice Reduction
  • Gauss' algorithm
  • LLL algorithm
  • Euclid's algorithm
Cited by

Source: OpenCitations

  • Topographs for binary quadratic forms and class numbers

    Mathematika

    Authors : Cormac O'Sullivan ORCID

    Journal reference : Volume 71, 2025, pp.

    DOI : 10.1112/mtk.70042

  • Smallest Reduction Matrix of Binary Quadratic Forms

    Lecture notes in computer science

    Authors : Aurore Bernard, Nicolas Gama ORCID

    Journal reference : Volume , 2010, pp. 32-49

    DOI : 10.1007/978-3-642-14518-6_7

  • On the Security of Cryptosystems with Quadratic Decryption: The Nicest Cryptanalysis

    Authors : Guilhem Castagnos, Fabien Laguillaumie ORCID

    Journal reference : Volume , 2009, pp. 260-277

    DOI : 10.1007/978-3-642-01001-9_15

  • Probabilistic Analyses of Lattice Reduction Algorithms

    Information security and cryptography

    Authors : Brigitte Vallée ORCID, Antonio Vera

    Journal reference : Volume , 2009, pp. 71-143

    DOI : 10.1007/978-3-642-02295-1_3
Preview
Loading PDF preview...