Optimital algorithm for solving XOR equation systems

Question

I am trying to solve the XOR equation system. For example:

A = [[1, 1, 1, 0, 0], [0, 1, 1, 1, 0], [0, 0, 1, 1, 1], [0, 1, 1, 0, 1], [0, 1, 0, 1, 1]]
s = [3, 14, 13, 5, 2]
m = 5 # len(s)
Ax = s => x = [12, 9, 6, 1, 10]

I tried 2 ways:

The first way is Gaussian elimination (~2.5 second) which was showed here
The second way to invert modular matrix A (with modulo 2) and then, XOR multiply with A_invert and s. (~7.5 second)

Could you please show me is there a way or a python library to speed up. Even I tried to use gmpy2 library, but it cannot reduce much. Below I described python code so that you can easily follow.

Using Gaussian elimination:

def SolveLinearSystem (A, B, N):
    for K in range (0, N):
        if (A[K][K] == 0):
            for i in range (K+1, N):
                if (A[i][K]!=0):
                    for L in range (0, N):
                        s = A[K][L]
                        A[K][L] = A[i][L]
                        A[i][L] = s
                    s = B[i]
                    B[i] = B[K]
                    B[K] = s
                    break
        for I in range (0, N):
            if (I!=K):
                if (A[I][K]):
                    #M = 0
                    for M in range (K, N):
                        A[I][M] = A[I][M] ^ A[K][M]
                    B[I] = B[I] ^ B[K]

SolveLinearSystem (A, s, 5)

Using Inversion

def identitymatrix(n):
    return [[long(x == y) for x in range(0, n)] for y in range(0, n)]

def multiply_vector_scalar (vector, scalar, q):
    kq = []
    for i in range (0, len(vector)):
        kq.append (vector[i] * scalar %q)
    return kq

def minus_vector_scalar(vector1, scalar, vector2, q):
    kq = []
    for i in range (0, len(vector1)):
        kq.append ((vector1[i] - scalar * vector2[i]) %q)
    return kq

def inversematrix(matrix, q):
    n = len(matrix)
    A =[]
    for j in range (0, n):
        temp = []
        for i in range (0, n):
            temp.append (matrix[j][i])
        A.append(temp)

    Ainv = identitymatrix(n)

    for i in range(0, n):
        factor = gmpy2.invert(A[i][i], q) #invert mod q
        A[i] = multiply_vector_scalar(A[i],factor,q)
        Ainv[i] = multiply_vector_scalar(Ainv[i],factor,q)
        for j in range(0, n):
            if (i != j):
                factor = A[j][i]
                A[j] = minus_vector_scalar(A[j], factor, A[i], q)
                Ainv[j] = minus_vector_scalar(Ainv[j], factor, Ainv[i], q)
    return Ainv

def solve_equation (A, y):
    result = []
    for i in range (0, m):
        temp = 0
        for j in range (0, m):
            temp = (temp ^ A[i][j]* y[j])
        result.append(temp)
    return result

A_invert = inversematrix(A, 2)
print solve_equation (A_invert, s)

[Block Lanczos](http://link.springer.com/chapter/10.1007%2F3-540-49264-X_9) really flies. — tmyklebu, Jul 14 '14 at 04:10
Numpy arrays of Boolean are going to be 100's of times faster, easily, although you should use vector operations instead of your loops. You can also look in scipy for solvers/optimizers that may fit the bill. — U2EF1, Jul 14 '14 at 05:50

score 1 · Answer 1 · answered Jul 14 '14 at 04:26

Both of the methods you present make you do a cubic number of bit-operations. There are methods that are faster, both asymptotically and in practise.

A first step (that may well be sufficient for you) is to use a 32-bit integer (I believe they're called numpy.int32 in Python) to store 32 consecutive elements of a row. This will speed up row reduction by a factor close to 32 on large enough inputs and probably put a significant dent into your running time on modest inputs.

In your particular code, there are a number of things for you to trivially specialise to the mod-2 case. Search your code for % and inversemodp and handle all of those; the extra, pointless operations are most certainly not helping your runtime.

Optimital algorithm for solving XOR equation systems

1 Answers1