| Identifiant de l'article : |
 |
ensl-00452881, version 1 |
|
|
| Identifiant arXiv : |
|
arXiv:1002.0739 |
|
|
| Domaine : |
|
|
|
|
| Titre : |
|
Gradual sub-lattice reduction and a new complexity for factoring polynomials |
|
|
| Auteur(s) : |
|
Mark Van Hoeij1, Andrew Novocin2, 3 |
|
|
| Laboratoire : |
|
| 1 : |
FSU - Florida State University |
|
| 2 : |
LIP - Laboratoire de l'Informatique du Parallélisme |
|
| 3 : |
Inria Grenoble Rhône-Alpes / LIP Laboratoire de l'Informatique du Parallélisme - ARENAIRE |
|
|
|
| Équipe de recherche : |
|
[ARENAIRE - Arithmétique des ordinateurs] |
| Résumé : |
|
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. |
|
|
|
Langue du texte
intégral : |
|
Anglais |
|
|
| Mots-clés : |
|
Lattice Reduction – Polynomial Factorization – Computational Complexity – Algebraic Number Reconstruction |
|
|
Récupérer au format
