# Technical Report CS0676

 TR#: CS0676 Class: CS Title: FACTORIZATION PROPERTIES OF LATTICES OVER THE INTEGERS Authors: A. Paz and M. Lempel PDF - Revised CS0676.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. Copyright The 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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1991/CS/CS0676), rather than to the URL of the PDF files directly. The latter URLs may change without notice.