Covering Radius of Two-dimensional Lattices

Yupeng Jiang; Yingpu Deng; Yanbin Pan

Paper 2009/539

Covering Radius of Two-dimensional Lattices

Yupeng Jiang, 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.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. Unknown where it was published
Contact author(s): dengyp @ amss ac cn
History: 2009-11-08: received
Short URL: https://ia.cr/2009/539
License: CC BY

BibTeX

@misc{cryptoeprint:2009/539,
      author = {Yupeng Jiang and Yingpu Deng and Yanbin Pan},
      title = {Covering Radius of Two-dimensional Lattices},
      howpublished = {Cryptology {ePrint} Archive, Paper 2009/539},
      year = {2009},
      url = {https://eprint.iacr.org/2009/539}
}