Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

https://hal.inria.fr/ensl-00994752
Contributor : Gilles Villard <>
Submitted on : Thursday, May 22, 2014 - 8:39:44 AM
Last modification on : Thursday, November 21, 2019 - 2:27:24 AM

Identifiers

  • HAL Id : ensl-00994752, version 1

Collections

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⟩

Share

Metrics

Record views

358