Cryptology ePrint Archive: Report 2009/539

Covering Radius of Two-dimensional Lattices

Yupeng Jiang and Yingpu Deng and Yanbin Pan

Abstract: The covering radius problem in any dimension is not known to be solvable in nondeterministic polynomial time, but when in dimension two, we give a deterministic polynomial time algorithm by computing a reduced basis using Gauss' algorithm in this paper.

Category / Keywords: foundations /

Date: received 4 Nov 2009

Contact author: dengyp at amss ac cn

Available format(s): PDF | BibTeX Citation

Version: 20091108:041519 (All versions of this report)

Short URL: ia.cr/2009/539

Discussion forum: Show discussion | Start new discussion