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$?
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

On the complexity of matrix reduction over finite fields

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.

The Asymptotic Complexity Of Matrix reduction Over Finite Fields