Determinant modulo m

Question

What are the known efficient algorithms for computing a determinant of an integer matrix with coefficients in $\mathbb{Z}_m$, the ring of residues modulo $m$. The number $m$ may not be prime but composite (so computations are performed in ring, not a field).

As far as I know (read below), most algorithms are modifications of Gaussian elimination. The question is about the computational efficiency of these procedures.

If it happened that there is some different approach, I also curious about it.

Thanks in advance.

Update:

Let me explain the source of this question. Assume, $m$ is a prime number. So $\mathbb{Z}_m$ is a field. And in this case we can perform all computations using numbers less than $m$, so we have some nice upper bound on all operations on numbers: addition, multiplication and inversion --- all needed operations to run Gaussian elimination.

On the other hand we can not perform inversion for some numbers in case $m$ not a prime. So we need some tricks to compute determinant.

And now I am curious what are the known tricks to do the job and whether such tricks could be found in and papers of books.

Answer 1

If you know the factorization of $m = p_1^{e_1} \cdots p_n^{e_n}$ you can compute modulo each $p_i^{e_i}$ separately and then combine the results using Chinese remaindering. If $e_i = 1$, then computing modulo $p_i^{e_i}$ is easy, since this is a field. For larger $e_i$, you can use Hensel lifting.

Answer 2

There is a combinatorial algorithm by Mahajan and Vinay that works over commutative rings: http://cjtcs.cs.uchicago.edu/articles/1997/5/contents.html

Answer 3

To solve this problem there is a fast deterministic algorithm based on Smith normal forms whose worst-case complexity is upper-bounded by the cost of matrix-multiplication over the integers modulo $m$. For any matrix $A$, the algorithm outputs its Smith normal form, from where $\text{det}(A)$ can be easily computed.

More concretely, define $\omega$ so that two $n \times n$ matrices with coefficients taken from $\mathbb{Z}_m$ can be multiplied using $O(n^{\omega})$ basic arithmetic operations on $\mathbb{Z}_m$ (integer addition, multiplication, exponentiation, etc). Then,

Given a matrix $A\in \mathbb{Z}_m^{n \times n}$, there exists a deterministic algorithm that computes $\text{det}(A)$ using $O(n^{\omega})$ basic arithmetical operations over $\mathbb{Z}_m$ [1].

When this was written in 1996 there was no asymptotically faster alternative (the paper mentions the prior existence of algorithms with the same bound but I do not know which ones, or whether they are probabilistic).

Update (July 17, 2013): a nice bonus feature of this algorithm is that it runs in polynomial time for arbitrary composite $m$ without knowing a prime-nuber factorization of $m$! This is good since there are no known efficient (classical) algorithms for factoring (of course, if you had a quantum computer, then you could apply Shor's algorithm). If you do have the factorization then the algorithm Markus suggested seems way simpler to implement.

Notes: in the paper, the complexity of "basic arithmetical operations" is $O(\log^2 m)$ if you use standard integer arithmetic, but you can achieve $O(M(\log m)\log \log m)$ with faster techniques. $M(t)$ bounds the cost of multiplying two $t$-bit integers. The current record for $\omega$ is 2.3727.