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?
I don't think you need factorization. To do Gaussian elimination, you may need inverses modulo $n$, but you can get those by the Euclidean algorithm, without factorization, and the Euclidean algorithm is fast.