Solving sparse linear systems of equations over finite fields using bit-flipping algorithm

Let _Fq${\mathbb{F}}_q$ be the finite field with q   elements. We give an algorithm for solving sparse linear systems of equations over _Fq${\mathbb{F}}_q$ when the coefficient matrix of the system has a specific structure, here called relatively connected. This algorithm is based on a well-known decoding algorithm for low-density parity-check codes called bit-flipping algorithm. We modify and extend this hard decision decoding algorithm. The complexity of this algorithm is linear in terms of the number of columns n and the number of nonzero coefficients ω of the matrix per iteration. The maximum number of iterations is bounded above by m, the number of equations.