Gradual sub-lattice reduction and a new complexity for factoring polynomials - Archive ouverte HAL Access content directly
Conference Papers Year : 2010

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

(1) , (2, 3)
1
2
3

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.
Fichier principal
Vignette du fichier
LATIN2010_novocin.pdf (198.62 Ko) Télécharger le fichier
Vignette du fichier
with_appendix_LATIN2010_novocin.pdf (233.13 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Format : Other
Loading...

Dates and versions

ensl-00452881 , version 1 (03-02-2010)

Identifiers

Cite

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

Altmetric

Share

Gmail Facebook Twitter LinkedIn More