I am working on Quadratic Sieve algorithm in c++. And after Gaussian elimination I need to solve set of modular equations such as, for example :
(1) b + c = 0 mod 2
(2) a + c = 0 mod 2
Here the symbol = is used to mean "is congruent to". I am processing matrix as shown here:https://math.stackexchange.com/questions/289348/matrix-processing-in-the-quadratic-sieve?rq=1. If anyone has any ideas how to implement such a function that will solve these equations I would appreciate it.
You can rewrite this system in matrix notation:
M . X = S
|0 1 1|.|a| = |0|
|1 0 1| |b| |0|
|c|
Then you solve it as usual using Gaussian elimination. The small difference is that you only work with the values 0
and 1
and that substracting a row is the same as adding the row (in Z/2Z, -a = a)