Factorization properties of lattices over the integers (Q1345515)

Let \(L\), \(L_ 1\), \(L_ 2\) denote \(n\)-dimensional lattices over the integers. Then \(L\) can be factored as \(L= L_ 1 L_ 2\) if every vector of \(L\) is a combination of basis vectors of \(L_ 2\), where the combination coefficients form a vector of \(L_ 1\). In this paper, three polynomial time algorithms are given to factor a lattice \(L\). The first algorithm factors a lattice \(L\) into cyclic lattices. The second factors cyclic lattices into simple lattices. (Cyclic and simple are defined in the paper.) The third factors simple lattices into prime lattices, which are lattices where the basis matrix has prime determinant. Several other algorithms for lattices are also given. In the appendix, the authors also present an extended GCD algorithm in the style of \textit{W. A. Blankinship} [Am. Math. Mon. 70, 742-745 (1963; Zbl 0116.268)].