scientific article; zbMATH DE number 4045845

From MaRDI portal
Publication:3784192





[For the entire collection see Zbl 0616.00013.] We reduce in polynomial time various computational problems concerning integer lattices to the case that the lattice L is defined by a single modular (linear, homogeneous) equation, \(L=\{x\in {\mathbb{Z}}^ n: <x,y>=0 mod d)\) where v is a vector in \({\mathbb{Z}}^ n\) and d an integer. An integer lattice \(L\subset {\mathbb{Z}}^ n\) can be written in this form if and only if L has rank n and if the abelian group \({\mathbb{Z}}^ n/L\) is cyclic. The shortest vector problem, the problem to compute the successive minima of a lattice and the problem to reduce (in the sense of Minkowski or in the sense of Korkine-Zolotareff) a lattice basis is transformed in polynomial time to lattices of the above special form. Our method shows that every integer lattice can be approximated efficiently by rational lattices \(L\subset \frac{1}{k}{\mathbb{Z}}^ n\) such that the abelian group \({\mathbb{Z}}^ n/kL\) is cyclic.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3784192)