Adaptive precision floating point LLL

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.