New Lattice Reduction Algorithm Based on Gauss and LLL Reduction
Bai Jia · Jisuanji gongcheng · 2013
Lattice is a regular alignment of points in multi-dimensional. There are many people researching the public-key cryptosystem based on lattice recently. This paper introduces the basic knowledge of reduced basis of the lattice and analyzes the Gauss algorithm and LLL algorithm. On this basis, it presents the Gauss-LLL algorithm. It proves that algorithm's validity and gives its realization pseudo code.Gauss-LLL algorithm can reduce arbitrarily set of base for lattice, and eventually get a shorter length lattice. Analysis result shows that Gauss-LLL algorithm not only can get a better reduced basis of the lattice, but also can be faster than the LLL algorithm.