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.
Type de document :
Communication dans un congrès
LATIN 2010, Apr 2010, Oaxaca, Mexico. LLNCS, 2010
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00452881
Contributeur : Andrew Novocin <>
Soumis le : mercredi 3 février 2010 - 12:02:03
Dernière modification le : vendredi 20 avril 2018 - 15:44:24
Document(s) archivé(s) le : vendredi 18 juin 2010 - 18:37:24

Identifiants

  • 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. LLNCS, 2010. 〈ensl-00452881〉

Partager

Métriques

Consultations de la notice

310

Téléchargements de fichiers

173