Fast parallel computation of reduced row echelon form to find the minimum distance of linear codes

Abstract

Finding the distance of linear codes is a key aspect to build error correcting codes, and also to design attacks in code-based post-quantum cryptography; however, it is a NP-hard problem difficult to be addressed. Metaheuristics, and more specifically genetic algorithms, have proven to be a promising tool to improve the search of an upper bound for the distance of a given linear code. In a previous work, it was demonstrated that the there exists a column permutation of a code matrix whose Reduced Row Echelon Form (RREF) contains a row of minimum weight, i.e. the code distance, although calculating RREF during fitness evaluation increases the time complexity of the algorithm substantially. In this work, we propose parallelization of multiple calculations of Reduced Row Echelon Forms simultaneously, and its integration into a fully parallelized design of a CHC evolutionary algorithm to overcome this limitation. Moreover, we demonstrate empirically a substantial improvement in time complexity for the approach in practical case studies to find the distance of linear codes over different finite fields.