在 C++ 中求解一组模方程

Question

我正在研究 C++ 中的二次筛算法。在高斯消元法之后，我需要求解一组模方程，例如：

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

这里的符号=用来表示"is congruent to"。我正在处理矩阵，如下所示：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)

Solve set of modular equations in C++