Paper 2009/539 Original: eprint.iacr.org/2009/539 ↗
Covering Radius of Two-dimensional Lattices
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
- Preprint.
- History
- 2009-11-08: last updated
- 2009-11-08: published
- Short URL
- https://ia.cr/2009/539
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}