@misc{10481/99214,
year = {2023},
url = {https://hdl.handle.net/10481/99214},
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.},
keywords = {Linear code},
keywords = {Minimum distance},
keywords = {Genetic algorithm},
keywords = {Parallel genetic algorithm},
keywords = {GPU-based parallel model},
keywords = {Post-quantum cryptography},
title = {Fast parallel computation of reduced row echelon form to find the minimum distance of linear codes},
doi = {10.1016/j.eswa.2023.119955},
author = {Pegalajar Cuéllar, Manuel and Lobillo Borrero, Francisco Javier and Navarro Garulo, Gabriel},
}