An upper bound on the average number of iterations of the LLL algorithm

DOI10.1016/0304-3975(94)90071-XzbMath0796.11024OpenAlexW2064749085MaRDI QIDQ1314406

Brigitte Vallée, Hervé Daudé

Publication date: 3 March 1994

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(94)90071-x

zbMATH Keywords

upper boundLLL algorithmaverage number of iterations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Quadratic forms (reduction theory, extreme forms, etc.) (11H55)

Related Items

Bounding basis reduction properties, Distribution of Hermite's constant and the shortest vector in lattices of dimension two, Fast LLL-type lattice reduction, Parallel Cholesky-based reduction for the weighted integer least squares problem, Speeding-Up Lattice Reduction with Random Projections (Extended Abstract), On the reduction of a random basis, Random lattices, threshold phenomena and efficient reduction algorithms.

Cites Work

• Factoring polynomials with rational coefficients
• Distribution of Hermite's constant and the shortest vector in lattices of dimension two
• Lattice points in high-dimensional spheres
• Gauss' algorithm revisited
• Über die mittlere Schrittanzahl bei Divisionsalgorithmen
• The number of steps in the Euclidean algorithm
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item