In this paper we discuss the global optimality of vector lengths for lattice bases. By introducing a partial order on lattice bases and the concept of successive minimal basis （SMB for short）, we show that any of it...In this paper we discuss the global optimality of vector lengths for lattice bases. By introducing a partial order on lattice bases and the concept of successive minimal basis （SMB for short）, we show that any of its minimal elements is a general greedy-reduced basis, and its least element （if exists） is an SMB. Furthermore, we prove the existence of SMB for lattices of dimension up to 6.展开更多
The authors present an algorithm which is a modilication of the Nguyen-Stenle greedy reduction algorithm due to Nguyen and Stehle in 2009. This algorithm can be used to compute the Minkowski reduced lattice bases for ...The authors present an algorithm which is a modilication of the Nguyen-Stenle greedy reduction algorithm due to Nguyen and Stehle in 2009. This algorithm can be used to compute the Minkowski reduced lattice bases for arbitrary rank lattices with quadratic bit complexity on the size of the input vectors. The total bit complexity of the algorithm is O（n^2·（4n!）^n·（n!/2^n）^n/2·（4/3）^n（n-1）/2）.log^2 A）where n is the rank of the lattice and A is maximal norm of the input base vectors. This is an O（log^2 A） algorithm which can be used to compute Minkowski reduced bases for the fixed rank lattices. A time complexity n!. 3n（log A）^O（1） algorithm which can be used to compute the successive minima with the help of the dual Hermite-Korkin-Zolotarev base was given by Blomer in 2000 and improved to the time complexity n!- （log A）^O（1） by Micciancio in 2008. The algorithm in this paper is more suitable for computing the Minkowski reduced bases of low rank lattices with very large base vector sizes.展开更多
文摘In this paper we discuss the global optimality of vector lengths for lattice bases. By introducing a partial order on lattice bases and the concept of successive minimal basis （SMB for short）, we show that any of its minimal elements is a general greedy-reduced basis, and its least element （if exists） is an SMB. Furthermore, we prove the existence of SMB for lattices of dimension up to 6.
基金supported by the National Natural Science Foundation of China (No.10871068)the Danish National Research Foundation and National Natural Science Foundation of China Joint Grant (No.11061130539)
文摘The authors present an algorithm which is a modilication of the Nguyen-Stenle greedy reduction algorithm due to Nguyen and Stehle in 2009. This algorithm can be used to compute the Minkowski reduced lattice bases for arbitrary rank lattices with quadratic bit complexity on the size of the input vectors. The total bit complexity of the algorithm is O（n^2·（4n!）^n·（n!/2^n）^n/2·（4/3）^n（n-1）/2）.log^2 A）where n is the rank of the lattice and A is maximal norm of the input base vectors. This is an O（log^2 A） algorithm which can be used to compute Minkowski reduced bases for the fixed rank lattices. A time complexity n!. 3n（log A）^O（1） algorithm which can be used to compute the successive minima with the help of the dual Hermite-Korkin-Zolotarev base was given by Blomer in 2000 and improved to the time complexity n!- （log A）^O（1） by Micciancio in 2008. The algorithm in this paper is more suitable for computing the Minkowski reduced bases of low rank lattices with very large base vector sizes.
