The optimal LLL algorithm is still polynomial in fixed dimension.

DOI10.1016/S0304-3975(02)00616-3zbMath1053.68049MaRDI QIDQ1401288

Ali Akhavi

Publication date: 17 August 2003

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

zbMATH Keywords

complexityoutput basis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (1)

Gradual sub-lattice reduction and a new complexity for factoring polynomials

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On Lovász' lattice reduction and the nearest lattice point problem
• A hierarchy of polynomial time lattice basis reduction algorithms
• Factoring polynomials with rational coefficients
• Lattice reduction: a toolbox for the cryptoanalyst
• Integer Programming with a Fixed Number of Variables
• The Computational Complexity of Simultaneous Diophantine Approximation Problems
• Solving low-density subset sum problems
• The Generalized Gauss Reduction Algorithm
• Worst-case complexity bounds for algorithms in the theory of integral quadratic forms
• Gauss' algorithm revisited
• An Average-Case Analysis of the Gaussian Algorithm for Lattice Reduction

This page was built for publication: The optimal LLL algorithm is still polynomial in fixed dimension.