New Results on Lattice Basis Reduction in Practice

Abstract. In this paper we introduce several new heuristics as to speed up known lattice basis reduction methods and improve the quality of the computed reduced lattice basis in practice. We analyze substantial experimental data and to our knowledge, we are the rst to present a general heuristic for determining which variant of the reduction algo-rithm, for varied parameter choices, yields the most ecient reduction strategy for reducing a particular problem instance.