2
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It's always O(n^3) field operations, but the complexity of those operations has to vary with q, doesn't it? $\endgroup$ – bmm6o Sep 1 '20 at 16:05
  • $\begingroup$ Is it true that the cost is O(q^2 n^3) or O(q^2 n^2/log_q (n)) ? $\endgroup$ – Kunal Sep 1 '20 at 18:50
  • $\begingroup$ @bmm6o the complexity of those field operations does vary with $q$. See crypto.stackexchange.com/questions/2068/… $\endgroup$ – Tom Ridley Sep 1 '20 at 23:09
  • $\begingroup$ @Kunal can you clarify where the $q^2$ term is coming from? $\endgroup$ – Tom Ridley Sep 1 '20 at 23:09
  • $\begingroup$ @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! $\endgroup$ – Kunal Sep 2 '20 at 0:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.