|
Abstract : |
Many linear algebra problems over the ring ZN of integers modulo N can be solved by transforming via elementary row operations an n \Theta m input matrix A to Howell form H. The nonzero rows of H give a canonical set of generators for the submodule of (ZN) m generated by the rows of A. In this paper we present an algorithm to recover H together with an invertible transformation matrix P which satisfies PA = H. The cost of the algorithm is O(nm!\Gamma1) operations with integers bounded in magnitude by N. This leads directly to fast algorithms for tasks involving ZN--modules, including an O(nm!\Gamma1) algorithm for computing the general solution over ZN of the system of linear equations xA = b, where b 2 (ZN), |
