алгоритм — Решить множество модульных уравнений в переполнении стека
Я работаю над алгоритмом Quadratic Sieve в 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. Если у кого-то есть идеи, как реализовать такую функцию, которая будет решать эти уравнения, я был бы признателен.
Решение
Вы можете переписать эту систему в матричной записи:
M . X = S
|0 1 1|.|a| = |0|
|1 0 1| |b| |0|
|c|
Затем вы решаете это, как обычно, используя гауссово исключение. Небольшая разница в том, что вы работаете только со значениями 0 а также 1 и что вычитание строки аналогично добавлению строки (в Z / 2Z -a = a)
Другие решения
Других решений пока нет …
detector