A parallel lattice basis reduction for mesh-connected processor arrays and parallel complexity

Lattice basis reduction has important applications in the areas of computer algebra, cryptography and combinatorial optimization. Several efficient sequential algorithms are known. Recently, parallel algorithms have been developed but until now a formal proof for the efficiency of parallel algorithms with n² processors has been omitted, where n denotes the dimension of the lattice. In this paper, a variant of the well-known basis reduction algorithms is presented that is well suited for the computation with fast floating point arithmetic and for the implementation on a mesh-connected array of n² processors. In addition, an error analysis and a proof of the parallel efficiency is provided