# What is the bit complexity of Gaussian eliminaton over $\Bbb F_q$?

Given matrix $M\in\Bbb F_q^{n\times n}$ with rank $r$ what is the complexity of converting to row-echelon form?

Is it $O(n^3\log q)$ or $O(n^3q)$ bit operations?

Technically $O(n^3)$ row operations in $O(\log q)$ bit words should be $O(n^3(\log q)(\log\log q)^2)$ bit operations in worst case when $q$ is prime.

What I am confused about is

1. when $q$ is prime power

2. incorporating complexity of modular operations.

• When $q$ is prime, arithmetic in $\mathbb{F}_q$ is the same as arithmetic modulo $q$, and takes polylogarithmic time in $q$ (the exact running time depends on the cost of multiplication, which is $\tilde{O}(\log q)$). – Yuval Filmus Sep 25 '17 at 15:32
• @YuvalFilmus Oh I see. So with Strassen-Schonage-Furer type integer multiplication we get $O(n^3(\log q)(\log\log q)^2)$ in worst case? – Turbo Sep 25 '17 at 18:04

The dependence on the field is via the cost of arithmetic operations over the field. Since numbers in $\mathbb{F}_q$ have bit size $O(\log q)$, the cost of each individual operation is polylogarithmic in $q$.

• Is it t $O(n^3(\log q)(\log\log q)^2)$ in worst case? – Turbo Sep 25 '17 at 18:07
• That's certainly a plausible upper bound. I think now I have given you enough information to solve your question on your own. – Yuval Filmus Sep 25 '17 at 18:08
• $O(n^3)$ row operations in $O(\log q)$ bit words should be $O(n^3(\log q)(\log\log q)^2)$ in worst case. What I am confused about is for the case $q$ is prime power and complexity of modular operations. – Turbo Sep 25 '17 at 18:09