Решение систем уравнений XOR
Я должен решить систему, которая состоит из 32 уравнений xor, каждое из которых включает 15 из 32 переменных.
Один будет выглядеть так:
i[0] = p[0] ^ p[4] ^ p[5] ^ p[10] ^ p[11] ^ p[20] ^ p[21] ^ p[22] ^ p[23] ^ p[25] ^ p[26] ^ p[27] ^ p[28] ^ p[30] ^ p[31]
i [n] и p [n] — 16-битные целые числа.
Так что, как я понимаю, я получу матрицу 32х32 (содержащую только 1 и 0) и вектор результата 32.
Очевидно, что мне нужно устранение по Гауссу, но я не могу сосредоточиться на проблеме, может кто-нибудь дать мне некоторое представление о том, как решить такую проблему?
РЕДАКТИРОВАТЬ: Вот решение в C ++
void SolveLinearSystem(u8 A[32][32], u8 B[32])
{
int N = 32;
for (int K = 0; K < N; ++K)
{
if( A[K][K] == 0 )
{
for(int i = K + 1; i<N ; ++i )
{
if(A[i][K] != 0)
{
for( int L = 0; L < N; ++L )
{
int s = A[K][L];
A[K][L] = A[i][L];
A[i][L] = s;
}
int s = B[i];
B[i] = B[K];
B[K] = s;
break;
}
}
}
for( int I = 0; I<N; ++I)
{
if( I!=K )
{
if( A[I][K] )
{
int M = 0;
for( M=K; M<N; ++M )
{
A[I][M] = A[I][M] ^ A[K][M];
}
B[I] = B[I] ^ B[K];
}
}
}
}
}
Решение
Да, вы можете использовать гауссово исключение, чтобы решить эту проблему. Ключ должен признать, что операция XOR эквивалентна сложению по модулю 2. Таким образом, уравнение, которое вы написали, эквивалентно
i[0] = (p[0] + p[4] + ... ) mod 2
Затем вы можете настроить всю систему в виде матричного уравнения
M*p=i mod 2
Вы можете решить эту проблему, как обычно, используя метод исключения Гаусса, за исключением того, что все ваши операции будут выполняться по модулю 2. Поскольку ваша матрица содержит много нулей, вам придется использовать поворот, но кроме этого, алгоритм является так же.
Другие решения
Если вы знакомы с решением регулярных систем уравнений, это не основной шаг вперед Используя действительные числа в системе уравнений, вы делаете исключение следующим образом:
[a b; c d] -> [a b; 0 d-(b*c/a)] -> [a 0; 0 d-(b*c/a)] -> [1 0; 0 1]
Замечания: здесь я использую матричную нотацию MATLAB для простоты ввода.
Важно понять, что все эти матричные операции (то есть деление, умножение, сложение и вычитание) существуют для любой поле, а не только реальные цифры. Если вы не знакомы с термином поле, это просто означает группу значений, которые допускают умножение, отрицание, инверсию, сложение и т. д.
Это приводит нас к решению систем уравнений xor. В настоящее время вы описываете свои системы как набор 16-битных значений, xor’d вместе. Тем не менее, я выбрал бы способ представления его в виде набора битов xor’d вместе, например, если бы ваше первое уравнение было:
p[0] = a[1] ^ a[2]
Я бы представлял это как:
p[0][0] = a[1][0] ^ a[2][0]
p[0][1] = a[1][1] ^ a[2][1]
…
Где второй набор скобок обозначает bit смещение в 16-битном значении. Итак, каждое из ваших маленьких уравнений будет эквивалентно 16 уравнениям.
Однобитовые операции xor над логическими значениями образуют поле. В этом поле мы делаем оператор «сложения» эквивалентным xor. Мы можем определить таблицы сложения и умножения следующим образом:
1 + 0 = 0 + 1 = 1; 1 + 1 = 0 + 0 = 0
1 * 0 = 0 * 1 = 0 * 0 = 0; 1 * 1 = 1
Деление возможно только на 1 (потому что вы не можете делить на ноль), и поэтому оператор деления оставляет элемент без изменений.
Благодаря этому вы сможете сформировать матрицу для своей системы уравнений xor. Эта матрица будет полностью состоять из 1 и 0. Затем используйте алгоритм исключения Гаусса-Джордана (его на самом деле не так уж сложно реализовать) так же, как и для обычных действительных чисел. Это позволит вам инвертировать матрицу и найти решение.
Лично я был настолько заинтригован этим вопросом, что написал небольшую реализацию матрицы C ++, которая позволяет вам предоставлять любое поле, которое вам нравится. Это может быть хорошей отправной точкой, или вы можете вообще захотеть использовать мой код! Вот исходный код на Github: XorSystem. Я специально предлагаю посмотреть на метод invert () в ANMatrix.