New heuristics for the shortest linear program (SLP) problem for large matrices
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 n...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Final Year Project (FYP) |
| Language: | English |
| Published: |
Nanyang Technological University
2020
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/139161 |
| _version_ | 1811685828324229120 |
|---|---|
| author | Ng, Chih Qing |
| author2 | Thomas Peyrin |
| author_facet | Thomas Peyrin Ng, Chih Qing |
| author_sort | Ng, Chih Qing |
| collection | NTU |
| description | 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. |
| first_indexed | 2024-10-01T04:50:43Z |
| format | Final Year Project (FYP) |
| id | ntu-10356/139161 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T04:50:43Z |
| publishDate | 2020 |
| publisher | Nanyang Technological University |
| record_format | dspace |
| spelling | ntu-10356/1391612023-02-28T23:14:11Z New heuristics for the shortest linear program (SLP) problem for large matrices Ng, Chih Qing Thomas Peyrin School of Physical and Mathematical Sciences thomas.peyrin@ntu.edu.sg Science::Mathematics 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. Bachelor of Science in Mathematical Sciences 2020-05-16T12:09:55Z 2020-05-16T12:09:55Z 2020 Final Year Project (FYP) https://hdl.handle.net/10356/139161 en application/pdf Nanyang Technological University |
| spellingShingle | Science::Mathematics Ng, Chih Qing New heuristics for the shortest linear program (SLP) problem for large matrices |
| title | New heuristics for the shortest linear program (SLP) problem for large matrices |
| title_full | New heuristics for the shortest linear program (SLP) problem for large matrices |
| title_fullStr | New heuristics for the shortest linear program (SLP) problem for large matrices |
| title_full_unstemmed | New heuristics for the shortest linear program (SLP) problem for large matrices |
| title_short | New heuristics for the shortest linear program (SLP) problem for large matrices |
| title_sort | new heuristics for the shortest linear program slp problem for large matrices |
| topic | Science::Mathematics |
| url | https://hdl.handle.net/10356/139161 |
| work_keys_str_mv | AT ngchihqing newheuristicsfortheshortestlinearprogramslpproblemforlargematrices |