Rozwiązywanie układów równań XOR
Muszę rozwiązać system składający się z 32 równań xor, z których każdy zawiera 15 z 32 zmiennych. Jeden wyglądałby tak:
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] i p [n] to 16-bitowe liczby całkowite.
Tak jak rozumiem, skończyłbym z macierzą 32x32 (zawierającą tylko 1s i 0s) i wektorem wyniku 32.
Wydaje mi się, że eliminacja Gaussa jest tym, czego potrzebuję, ale nie mogę oprzeć się na tym problemie, czy ktoś może dać mi wgląd w rozwiązanie tego problemu?
EDYCJA: Oto rozwiązanie w 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];
}
}
}
}
}