Factorization properties of lattices over the integers Original Research Article

Let A be a nonsingular n × n matrix over the integers. L = L(A) denotes 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 = (xi) : ∑aixi ≡ 0 (mod d)} where the aiʹs and d are integers and 0 ≤ ai < d, Let L, L1, L2(B) be lattices over the integers. L = L1L2 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 L1, and B is a nonsingular n × n matrix. The following results are proved: 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 a finite modular lattice, given in modular form.