Technical Report CS0676

Authors: A. Paz and M. Lempel
PDF - RevisedCS0676.revised.pdf
Abstract: Let $A$ be a nonsingular $n \times n$ matrix over the integers $L = L(A)$ denoting the lattice whose elements are combinations with integer coefficients of the rows of $A$. $L$ is cyclic if it can be defined in the modular form $L = \{x = (x_{i}) : \sum a_{i} x_{i} \equiv 0\ (\mbox{mod\ d}) \}$ where the $a_{i}$'s and $d$ are integers and $0 \leq a_{i} < d$. Let $L, L_{1}, L_{2} (B)$ be lattices over the integers $L = L_{1} L_{2}$ is a factorization of $L$ if every element of $L$ is a combination of the rows of $B$ such that the vector of combination coefficients is in $L_{1}$, and $B$ is a nonsingular $n \times n$ matrix. The following results are proved in this paper: Every lattice can be expressed as a product of cyclic factors in polynomial time; Every cyclic lattice can be factored into `simple' (term explained in the text) factors in polynomial time; Every simple lattice can be factored into `prime' factors in polynomial time if a prime factorization of the determinant of its basis is given. In addition, we provide polynomial algorithms for the following problems: Transform a cyclic lattice given by a basis into a modular form and vice versa; find a basis of finite modular lattice, given in modular form.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1991
To the main CS technical reports page

Computer science department, Technion