Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR04-113 | 19th November 2004 00:00

#### Lattices with Many Cycles Are Dense

TR04-113
Authors: Mårten Trolin
Publication: 1st December 2004 22:45
Keywords:

Abstract:

We give a method for approximating any \$n\$-dimensional
lattice with a lattice \$\Lambda\$ whose factor group
\$\mathbb{Z}^n / \Lambda\$ has \$n-1\$ cycles of equal length
with arbitrary precision. We also show that a direct
consequence of this is that the Shortest Vector Problem and the Closest
Vector Problem cannot be easier for this type of lattices than
for general lattices.

ISSN 1433-8092 | Imprint