Mithilesh, Kumar and Raddum, Havard and Varadharajan, Srimathi (2019) Reducing Lattice Enumeration Search Trees. INFOCOMMUNICATIONS JOURNAL, 11 (4). pp. 8-16. ISSN 2061-2079
|
Text
InfocomJ_2019_4_2_Kumar.pdf Download (1MB) | Preview |
Abstract
We revisit the standard enumeration algorithm for finding the shortest vectors in a lattice, and study how the number of nodes in the associated search tree can be reduced. Two approaches for reducing the number of nodes are suggested. First we show that different permutations of the basis vectors have a big effect on the running time of standard enumeration, and give a class of permutations that give relatively few nodes in the search tree. This leads to an algorithm called hybrid enumeration that has a better running time than standard enumeration when the lattice is large. Next we show that it is possible to estimate the signs of the coefficients yielding a shortest vector, and that a pruning strategy can be based on this fact. Sign-based pruning gives fewer nodes in the search tree, and never missed the shortest vector in the experiments we did.
Item Type: | Article |
---|---|
Subjects: | H Social Sciences / társadalomtudományok > HE Transportation and Communications > HE2 Communications / hírközlés Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány |
Depositing User: | Andrea Tankó |
Date Deposited: | 28 Sep 2021 12:37 |
Last Modified: | 28 Sep 2021 12:37 |
URI: | http://real.mtak.hu/id/eprint/131188 |
Actions (login required)
Edit Item |