Solving a Modified Syndrome Decoding Problem using Integer Programming
Vlad Drăgoi, Pierre-Louis Cayrel, Brice Colombier, Dominic Bucerzan, Sorin Hoară · International Journal of Computers Communications & Control · 2020
In this article, we model a variant of the well-known syndrome decoding problem as a linear optimization problem. Most common algorithms used for solving optimization problems, e.g. the simplex algorithm, fail to find a valid solution for the syndrome decoding problem over a finite field. However, our simulations prove that a slightly modified version of the syndrome decoding problem can be solved by the simplex algorithm. More precisely, the algorithm returns a valid error vector when the syndrome vector is an integer vector, i.e.,the matrix-vector multiplication, is realized over Z, instead of Fq.