On the SVP for low-dimensional circulant lattices

Gengran Hu (), Yanbin Pan and Renzhang Liu
Additional contact information
Gengran Hu: Hangzhou Dianzi University
Yanbin Pan: Chinese Academy of Sciences
Renzhang Liu: Chinese Academy of Sciences

Journal of Combinatorial Optimization, 2024, vol. 47, issue 5, No 11, 21 pages

Abstract: Abstract Lattice is the main research subject in the geometry of numbers. SVP refers to finding a shortest nonzero lattice vector in a given lattice, which is thought to be a difficult optimization problem. For general lattice, the integer coefficients of a shortest nonzero vector under a lattice basis might be exponentially large, thus making the simple integer coefficient searching approach impractical. In this paper, we find that for low-dimensional circulant lattices(dimension $$n \in \{2,3,4,6\}$$ n ∈ { 2 , 3 , 4 , 6 } ), the integer coefficients of a shortest lattice vector under its circulant basis are actually in a small set $$S=\{-1,0,1\}$$ S = { - 1 , 0 , 1 } , which makes it easy to find the shortest vector in these cases. Moreover, we present the specific forms of the SVP solutions for low-dimensional circulant lattices.

Keywords: SVP; Shortest lattice vector; Low-dimensional; Circulant lattices; 11H06; 11H50; 90C27 (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01183-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:47:y:2024:i:5:d:10.1007_s10878-024-01183-1

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-024-01183-1

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().