New heuristics for the shortest linear program (SLP) problem for large matrices

Abstract

The aim of this paper is to propose an efficient algorithm (with polynomial or lower time complexity) to minimise the number of XOR gates required to compute a system of linear equations over GF(2) field. Firstly, famous Paar and Boyar-Peralta’s algorithms are reviewed, followed by introducing two new heuristic which incorporate the fundamental concepts of Paar and Boyar-Peralta’s algorithms. The two new method outperform Paar in terms of having lower XOR counts for matrices with high density (ρ = 0.7 to 0.9) and in terms of computational timing, both methods greatly lower the time required as compared to Boyar-Peralta’s algorithm. Therefore, making both methods applicable and efficient in solving large matrices of size greater than 32 × 32, especially if the matrices are of high density.