Primal-dual bases and successive minima

Chao Hai Xie; Ran Tao; Yue Wang; Ji Yong Li

Primal-dual bases and successive minima

Chao Hai Xie^*, Ran Tao, Yue Wang, Ji Yong Li

^*此作品的通讯作者

科研成果: 期刊稿件 › 文章 › 同行评审

摘要

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.

源语言	英语
页（从-至）	1124-1129
页数	6
期刊	Tien Tzu Hsueh Pao/Acta Electronica Sinica
卷	36
期	6
出版状态	已出版 - 6月 2008

其它文件与链接

链接到 Scopus 的出版物

引用此

Xie, C. H., Tao, R., Wang, Y., & Li, J. Y. (2008). Primal-dual bases and successive minima. Tien Tzu Hsueh Pao/Acta Electronica Sinica, 36(6), 1124-1129.

@article{dadad0aa1e0543e0bfb646f90c852af3,

title = "Primal-dual bases and successive minima",

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.",

keywords = "Lattice, Length defect, Reduced bases, Successive minima, The closest vector problem (CVP)",

author = "Xie, {Chao Hai} and Ran Tao and Yue Wang and Li, {Ji Yong}",

year = "2008",

month = jun,

language = "English",

volume = "36",

pages = "1124--1129",

journal = "Tien Tzu Hsueh Pao/Acta Electronica Sinica",

issn = "0372-2112",

publisher = "Chinese Institute of Electronics",

number = "6",

}

TY - JOUR

T1 - Primal-dual bases and successive minima

AU - Xie, Chao Hai

AU - Tao, Ran

AU - Wang, Yue

AU - Li, Ji Yong

PY - 2008/6

Y1 - 2008/6

N2 - 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.

AB - 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.

KW - Lattice

KW - Length defect

KW - Reduced bases

KW - Successive minima

KW - The closest vector problem (CVP)

UR - http://www.scopus.com/inward/record.url?scp=47549102757&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:47549102757

SN - 0372-2112

VL - 36

SP - 1124

EP - 1129

JO - Tien Tzu Hsueh Pao/Acta Electronica Sinica

JF - Tien Tzu Hsueh Pao/Acta Electronica Sinica

IS - 6

ER -

Primal-dual bases and successive minima

摘要

其它文件与链接

指纹

引用此