Fast Algorithms for Linear Algebra Modulo N

Many linear algebra problems over the ring ℤ _N of integers modulo N can be solved by transforming via elementary row operations an n × m input matrix A to Howell form H. The nonzero rows of H give a canonical set of generators for the submodule of (ℤ _N )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ω−1) operations with integers bounded in magnitude by N. This leads directly to fast algorithms for tasks involving ℤ _N -modules, including an O(nmω−1) algorithm for computing the general solution over ℤ _N of the system of linear equations xA = b, where b ∈ (ℤ _N )m.