Решите набор модульных уравнений в C++

Question

Я работаю над алгоритмом квадратичного сита в C++. И после исключения Гаусса мне нужно решить множество модульных уравнений, таких как, например:

(1) b + c = 0 mod 2 
(2) a + c = 0 mod 2 

Здесь символ = используется для обозначения «конгруэнтно». Я обрабатываю матрицу, как показано здесь: https://math.stackexchange.com/questions/289348/matrix-processing-in-the-quadratic-sieve?rq=1. Если у кого-нибудь есть идеи, как реализовать такую ​​функцию, которая решит эти уравнения, я был бы признателен.

Answer 1

Вы можете переписать эту систему в матричной форме:

M . X = S 

|0 1 1|.|a| = |0| 
|1 0 1| |b| |0| 
     |c| 

Затем решить, как обычно, с помощью метода исключения Гаусса. Небольшая разница заключается в том, что вы работаете только со значениями 0 и 1 и что вычитание строки такое же, как добавление строки (в Z/2Z, -a = a)