二维格的覆盖半径  

COVERING RADIUS OF TWO-DIMENSIONAL LATTICES

作　　者：姜宇鹏[1] 邓映蒲[1] 潘彦斌[1] 

机构地区：[1]中国科学院数学与系统科学研究院数学机械化重点实验室,北京100190

出　　处：《系统科学与数学》2012年第7期908-914,共7页Journal of Systems Science and Mathematical Sciences

基　　金：国家自然科学基金(11071285;61121062);973计划(2011CB302401)资助项目

摘　　要：求格的覆盖半径是一个经典的困难问题,当格的维数不固定时,这个问题还没有非确定性的多项式时间的算法.已知的算法都是通过求Voronoi cell来计算覆盖半径,对于二维格,文章利用高斯算法给出了一个确定性的多项式时间的算法来求覆盖半径以及deepholes.The covering radius problem of lattice in any dimension is classical and difficult in nondeterministic polynomial time. In this paper, in the case of dimension two, a deterministic polynomial time algorithm is given by computing a reduced basis by using Gauss＇ algorithm, and this algorithm needs not to compute the Voronoi cells of the lattice, which is different from all existing algorithms for computing the covering radius of a lattice with fixed dimension.

关 键 词：基于格的密码 DEEP HOLE 覆盖半径 高斯算法 

分 类 号：O153.1[理学—数学]