原-对偶规约基与连续最小元  

Primal-Dual Bases and Successive Minima

作　　者：谢朝海[1] 陶然[1] 王越[1] 李继勇[1] 

机构地区：[1]北京理工大学信息科学技术学院

出　　处：《电子学报》2008年第6期1124-1129,共6页Acta Electronica Sinica

基　　金：国家863高技术研究发展计划(No.2006AA01Z450);国防基础科研项目(No.C1120060497)

摘　　要：最近Koy提出一种质量优于LLL规约基的原-对偶规约基,但没有给出该规约基与最小元比值因子的上界和下界.本文首先分析了原-对偶规约基的性质,然后给出并证明了原-对偶规约基与连续最小元比值因子的上界和下界,最后用原-对偶规约基改进Babai的近似CVP算法——舍入算法,提高了其近似因子.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.

关 键 词：格 规约基 连续最小元 长度亏损 最近向量问题 

分 类 号：TP393[自动化与计算机技术—计算机应用技术] O15[自动化与计算机技术—计算机科学与技术]