HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

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

Abstract : We present a lattice algorithm specifically designed for some classical applications of lattice reduction. The applications are for lattice bases with a generalized knapsack-type structure, where the target vectors are boundably short. For such applications, the complexity of the algorithm improves traditional lattice reduction by replacing some dependence on the bit-length of the input vectors by some dependence on the bound for the output vectors. If the bit-length of the target vectors is unrelated to the bit-length of the input, then our algorithm is only linear in the bit-length of the input entries, which is an improvement over the quadratic complexity floating-point LLL algorithms. To illustrate the usefulness of this algorithm we show that a direct application to factoring univariate polynomials over the integers leads to the first complexity bound improvement since 1984. A second application is algebraic number reconstruction, where a new complexity bound is obtained as well.
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download

Contributor : Andrew Novocin Connect in order to contact the contributor
Submitted on : Wednesday, February 3, 2010 - 12:02:03 PM
Last modification on : Friday, February 4, 2022 - 3:15:43 AM
Long-term archiving on: : Friday, June 18, 2010 - 6:37:24 PM


  • HAL Id : ensl-00452881, version 1
  • ARXIV : 1002.0739



Mark van Hoeij, Andrew Novocin. Gradual sub-lattice reduction and a new complexity for factoring polynomials. LATIN 2010, Apr 2010, Oaxaca, Mexico. ⟨ensl-00452881⟩



Record views


Files downloads