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

• 主要作者: Ng, Chih Qing
• 其他作者: Thomas Peyrin
• 格式: Final Year Project
• 語言: English
• 出版: Nanyang Technological University 2020
• 主題: Science::Mathematics
• 在線閱讀: https://hdl.handle.net/10356/139161
• 機構: 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.