Skip to main content
Article
Adaptive precision floating point LLL
Faculty of Engineering and Information Sciences - Papers
  • Thomas Plantard, University of Wollongong
  • Willy Susilo, University of Wollongong
  • Zhenfei Zhang, University of Wollongong
RIS ID
77595
Publication Date
1-1-2013
Publication Details

Plantard, T., Susilo, W. and Zhang, Z. (2013). Adaptive precision floating point LLL. Lecture Notes in Computer Sciences in Computer Sciences in Computer Science, 7959 104-117.

Abstract

The LLL algorithm is one of the most studied lattice basis reduction algorithms in the literature. Among all of its variants, the floating point version, also known as L2, is the most popular one, due to its efficiency and its practicality. In its classic setting, the floating point precision is a fixed value, determined by the dimension of the input basis at the initiation of the algorithm. We observe that a fixed precision overkills the problem, since one does not require a huge precision to handle the process at the beginning of the reduction. In this paper, we propose an adaptive way to handle the precision, where the precision is adaptive during the procedure. Although this optimization does not change the worst-case complexity, it reduces the average-case complexity by a constant factor. In practice, we observe an average 20% acceleration in our implementation.

Grant Number
ARC/FT0991397
Citation Information
Thomas Plantard, Willy Susilo and Zhenfei Zhang. "Adaptive precision floating point LLL" (2013)
Available at: http://works.bepress.com/wsusilo/191/