Is there some polynomial upper-bound for Gauss elimination over ring $Z_n$? I'm interested in polynomial bound depending from size of matrix and $\log n$.
I also have the same question about the consistency of a linear system over ring $Z_n$.
P.S. I think, it's not so hard question if we have factorization of $n$. But what can we do without it?