Complexity Analysis of a Parallel Lattice Basis Reduction Algorithm
Christian Heckler, Lothar Thiele · SIAM Journal on Computing · 1998
Lattice basis reduction is an important problem in geometry of numbers with applications in combinatorial optimization, computer algebra, and cryptography. The well-known sequential LLL algorithm finds a short vector in O(n 4 log B) arithmetic operations on integers having binary length O(n log B), where n denotes the dimension of the lattice and B denotes the maximum L 2 norm of the initial basis vectors. In this paper a new analysis of the parallel algorithm of Roch and Villard is presented. It is shown that on an n x n mesh it needs O(n 2 log B) arithmetic operations on integers having binary length O(n log B). This improves the previous analysis and shows that an asymptotical speedup of n 2 is possible using n 2 processors.