An Experimental Comparison of Some LLL-Type Lattice Basis Reduction Algorithms

In this paper we experimentally compare the performance of the L² lattice basis reduction algorithm, whose importance recently became evident, with our own Gram-based lattice basis reduction algorithm, which is a variant of the Schnorr–Euchner algorithm. We conclude with observations about the algorithms under investigation for lattice basis dimensions up to the theoretical limit.We also reexamine the notion of “buffered transformations” and its impact on performance of lattice basis reduction algorithms.We experimentally compare four different algorithms directly in the Sage Mathematics Software: our own algorithm, the L² algorithm and “buffered” versions of them resulting in a total of four algorithms.