Euclidean lattice basis reduction: algorithms and experiments for disclosing integer relations

Gilles Villard 1, 2
2 ARIC - Arithmetic and Computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : We review polynomial time approaches for computing simultaneous integer relations among real numbers. A variant of the LLL lattice reduction algorithm (A. Lenstra, H. Lenstra, L. Lovász, 1982), the HJLS (J. Hastad, B. Just, J. Lagarias, J. and C.P. Schnorr, 1989) and the PSLQ (H. Ferguson, D. Bailey, 1992) algorithms are de facto standards for solving the problem. We investigate the links between the various approaches and present intensive experiment results. We especially focus on the question of the precision for the underlying floating-point procedures used in the currently fastest known algorithms and software libraries. Part of this work is done in collaboration with Stehlé in relation with the fplll library, and with D. Stehlé and J. Chen for the HJLS/PSLQ comparison.
Type de document :
Communication dans un congrès
International Linear Algebra Society (ILAS), Jun 2013, Providence, Rhode Island, United States
Liste complète des métadonnées

https://hal.inria.fr/ensl-00994752
Contributeur : Gilles Villard <>
Soumis le : jeudi 22 mai 2014 - 08:39:44
Dernière modification le : vendredi 20 avril 2018 - 15:44:26

Identifiants

  • HAL Id : ensl-00994752, version 1

Citation

Gilles Villard. Euclidean lattice basis reduction: algorithms and experiments for disclosing integer relations. International Linear Algebra Society (ILAS), Jun 2013, Providence, Rhode Island, United States. 〈ensl-00994752〉

Partager

Métriques

Consultations de la notice

315