The optimal LLL algorithm is still polynomial in fixed dimension.

DOI10.1016/S0304-3975(02)00616-3MaRDI QIDQ1401288zbMATH OpenFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 1512702
• An LLL algorithm with quadratic complexity
• An upper bound on the average number of iterations of the LLL algorithm
• Probabilistic Analyses of Lattice Reduction Algorithms
• Progress on LLL and lattice reduction

Cites work

• scientific article; zbMATH DE number 1944706 (Why is no real title available?)
• scientific article; zbMATH DE number 1512702 (Why is no real title available?)
• scientific article; zbMATH DE number 1775383 (Why is no real title available?)
• A hierarchy of polynomial time lattice basis reduction algorithms
• An Average-Case Analysis of the Gaussian Algorithm for Lattice Reduction
• Factoring polynomials with rational coefficients
• Gauss' algorithm revisited
• Integer Programming with a Fixed Number of Variables
• Lattice reduction: a toolbox for the cryptoanalyst
• On Lovász' lattice reduction and the nearest lattice point problem
• Solving low-density subset sum problems
• The Computational Complexity of Simultaneous Diophantine Approximation Problems
• The Generalized Gauss Reduction Algorithm
• Worst-case complexity bounds for algorithms in the theory of integral quadratic forms

Cited in

(1)

• A physical study of the LLL algorithm

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1401288)