Reducing lattice bases with Bergman exchange
Jingwei Chen, Yong Feng, Wenyuan Wu · 2017
We present a new algorithm to reduce bases for Euclidean lattices. In contrast to the celebrated Lenstra-Lenstra-Lovász (LLL) algorithm that uses the local Lovász exchange rule, the algorithm in this paper utilizes a global exchange strategy that is introduced by Bergman (1980). We show that the algorithm computes an LLL-reduced basis within polynomial time in the size of the input basis.