A linear system is given, for instance:

.

And there're additional restrictions: . It is just an example, systems have hundreds equations and twice more variables. This system has an only solution though a number of equations is less than number of variables. Note the variables are binary but it is not suitable to solve the system by using modular arithmetic because in this case it has a few solutions. I see a few ways: 1) to use Gauss' method, then search for rest of solutions exhaustively; 2) to introduce new equations such as . The former is evidently bad. The latter is awkward and I'm not sure it will actually work. What is a better approach for this problem?