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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\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.

Improve this answer
$\endgroup$
9
  • $\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
    Commented Sep 1, 2020 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
    Commented Sep 1, 2020 at 18:50
  • $\begingroup$ @bmm6o the complexity of those field operations does vary with $q$. See crypto.stackexchange.com/questions/2068/… $\endgroup$
    – Curious Cat
    Commented Sep 1, 2020 at 23:09
  • $\begingroup$ @Kunal can you clarify where the $q^2$ term is coming from? $\endgroup$
    – Curious Cat
    Commented Sep 1, 2020 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
    Commented Sep 2, 2020 at 0:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.