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 metadatas

Cited literature [23 references]  Display  Hide  Download

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00452881
Contributor : Andrew Novocin <>
Submitted on : Wednesday, February 3, 2010 - 12:02:03 PM
Last modification on : Wednesday, November 20, 2019 - 3:02:26 AM
Long-term archiving on : Friday, June 18, 2010 - 6:37:24 PM

Identifiers

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

Collections

Citation

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

Share

Metrics

Record views

528

Files downloads

289