Mathematics – Combinatorics
Scientific paper
2012-01-25
Mathematics
Combinatorics
Scientific paper
In this paper we review the technique to solve the CVP based on dual HKZ-bases by J. Bloemer. The technique is based on the transference theorems given by Banaszczyk which imply some necessary conditions on the coefficients of the closest vectors with respect to a basis whose dual is HKZ reduced. Recursively, starting with the last coefficient, intervals of length i can be derived for the i-th coefficient of any closest vector. This leads to n! candidates for closest vectors. In this paper we refine the necessary conditions derived from the transference theorems, giving an exponential reduction of the number of candidates. The improvement is due to the fact that the lengths of the intervals are not independent. In the original algorithm the candidates for a coefficient pair (a_i,a_{i+1}) correspond to the integer points in a rectangle of volume i(i+1). In our analysis we show that the candidates for (a_i,a_{i+1}) in fact lie in an ellipse with transverse and conjugate diameter i+1, respectively i. This reduces the overall number of points to be enumerated by an exponential factor of about 0.886^n. We further show how a choice of the coefficients (a_n,...,a_{i+1}) influences the interval from which a_i can be chosen. Numerical computations show that these considerations allow to bound the number of points to be enumerated by n^{0.75 n} for 10 <= n <= 2000. Under the assumption that the Gaussian heuristic for the length of the shortest nonzero vector in a lattice is tight, this number can even be bounded by 2^{-2n} n^{n/2}.
Maze Gerard
Wagner Urs
No associations
LandOfFree
Improvements in closest point search based on dual HKZ-bases does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Improvements in closest point search based on dual HKZ-bases, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improvements in closest point search based on dual HKZ-bases will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-683525