An Approximate Deep Hole Algorithm Based on Dual HKZ-Bases of Lattices

DOI

10.2991/eeeis-16.2017.2How to use a DOI?

Keywords

lattice; Covering Radius; dual HKZ-bases; successive minima.

Abstract

We present a deterministic algorithm in time on input a dual HKZ-basis of a lattice of rank n to nd a point whose distance from at least , where is an integer, , is the input size, and is covering radius of . This provides a method to approximately nd a deep hole. Furthermore, we study the relation between the covering radius and successive minima in any norms which extends Haviv's result to.

Copyright

© 2017, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Wen-Wen Wang
AU  - Ke-Wei Lv
PY  - 2016/12
DA  - 2016/12
TI  - An Approximate Deep Hole Algorithm Based on Dual HKZ-Bases of Lattices
BT  - Proceedings of the 2nd Annual International Conference on Electronics, Electrical Engineering and Information Science (EEEIS 2016)
PB  - Atlantis Press
SP  - 6
EP  - 11
SN  - 2352-5401
UR  - https://doi.org/10.2991/eeeis-16.2017.2
DO  - 10.2991/eeeis-16.2017.2
ID  - Wang2016/12
ER  -