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

• Main Author: Ng, Chih Qing
• Other Authors: Thomas Peyrin
• Format: Final Year Project
• Language: English
• Published: Nanyang Technological University 2020
• Subjects: Science::Mathematics
• Online Access: https://hdl.handle.net/10356/139161
• Institution: Nanyang Technological University

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.