Abstract
Recently Koy proposed primal-dual bases which have better quality than LLL-reduced bases in high-dimensional lattice, but his efforts did not take into account the low and upper bounds for the ratios of primal-dual bases to successive minima. In this paper some useful properties of Koy's primal-dual bases are analyzed and then the low and upper bounds for the ratios of primal-dual bases to successive minima are introduced and proved. At the end, the Round-off algorithm for the approximate-CVP is improved using primal-dual bases and its result has a better approximation factor than L. Babai's.
| Original language | English |
|---|---|
| Pages (from-to) | 1124-1129 |
| Number of pages | 6 |
| Journal | Tien Tzu Hsueh Pao/Acta Electronica Sinica |
| Volume | 36 |
| Issue number | 6 |
| Publication status | Published - Jun 2008 |
Keywords
- Lattice
- Length defect
- Reduced bases
- Successive minima
- The closest vector problem (CVP)