2
$\begingroup$

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?

1 Answers 1