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

1

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.

  • 0
    Yes, thank you! It looks very simple for consistency.2011-12-10