# Complexity of Gaussian Elimination over a Finite Field

I read somewhere that the complexity of solving a Linear $$n\times n$$ system over a Finite Field $$\Bbb F_q$$ using Gaussian Elimination is $$\mathcal{O}(n^3)$$ operations in $$\Bbb F_q$$.

What's the role of $$\Bbb F_q$$ here in the complexity?

Also, what's the cost of this algorithm in terms of $$q$$ and $$n$$?

## 1 Answer

The classic Gaussian Elimination algorithm is $$O(n^3)$$ runtime regardless of specific field and the Matrix, so in this case a finite field $$F_q$$ of order $$q$$ doesn't play a role in the complexity. This runtime is due to the fact that you are zeroing out entries in columns column-by-column to get into row reduced echelon form.

For matrices in $$GL(n, q)$$, the set of $$n\times n$$ invertible matrices in the finite field of $$q$$ elements, Andrén et al. in 2007, demostrated a striped Gaussian elimination in

which can shave off a $$\log_q n$$ factor by attempting to pick row operations that simultaneously zero out entries in multiple columns by using the finite field structure.

They proved that up to a constant factor this algorithm is best possible as almost all matrices in $$GL(n, q)$$ need asymptotically at least $$\frac{n^2}{2 \log_q n}$$ operations.

Demetres, in 2014 showed that the striped elimination algorithm is asymptotically optimal by proving that almost all matrices in $$GL(n, q)$$ need asymptotically at least $$\frac{n^2}{\log_q n}$$ operations.

• It's always O(n^3) field operations, but the complexity of those operations has to vary with q, doesn't it? – bmm6o Sep 1 '20 at 16:05
• Is it true that the cost is O(q^2 n^3) or O(q^2 n^2/log_q (n)) ? – Kunal Sep 1 '20 at 18:50
• @bmm6o the complexity of those field operations does vary with $q$. See crypto.stackexchange.com/questions/2068/… – Tom Ridley Sep 1 '20 at 23:09
• @Kunal can you clarify where the $q^2$ term is coming from? – Tom Ridley Sep 1 '20 at 23:09
• @TomRidley Let k be the binary length of q. Since above algorithm requires $O(n^3)$ operations in $F_q$, and as one q-modular multiplication time cost is $O(k^2)$, therefore the total time cost is $O(k^2 \cdot n^3)$. I could be wrong on that, please correct me if its not making sense somewhere. Thanks! – Kunal Sep 2 '20 at 0:50