|
|
| |
| Greedy Algorithm Computing Minkowski Reduced Lattice Bases with Quadratic Bit Complexity of Input Vectors |
| |
Citation： |
Hao CHEN,Liqing XU.Greedy Algorithm Computing Minkowski Reduced Lattice Bases with Quadratic Bit Complexity of Input Vectors[J].Chinese Annals of Mathematics B,2011,32(6):857~862 |
| Page view： 2073
Net amount： 2218 |
Authors： |
Hao CHEN; Liqing XU; |
Foundation： |
the National Natural Science Foundation of China (No. 10871068) and the Danish
National Research Foundation and National Natural Science Foundation of China Joint Grant
(No. 11061130539). |
|
|
| Abstract： |
The authors present an algorithm which is a modification of the
Nguyen-Stehle 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 \cdot (4n!)^n \cdot
(\frac{n!}{2^n})^{\frac n2} \cdot
(\frac{4}{3})^{\frac{n(n-1)}{4}}\cdot
(\frac{3}{2})^{\frac{n^2(n-1)}{2}} \cdot \log^2A)$, 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! \cdot 3^n (\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! \cdot (\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. |
Keywords： |
Lattice, Successive minima, Minkowski reduced bases, Greedy reduction |
Classification： |
11H55, 68U05 |
|
|
Download PDF Full-Text
|
