Solving sparse linear systems of equations over finite fields using bit-flipping algorithm
Let F q be the finite field with q elements. We give an algorithm for solving sparse linear systems of equations over 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.