Skip to Main content Skip to Navigation
Conference papers

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

Mark van Hoeij 1 Andrew Novocin 2, 3 
3 ARENAIRE - Computer arithmetic
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
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