Solving Sparse Mrhs Systems With Genetic Algorithms

Abstract Multiple Right-Hand Sides (MRHS) equations represent a mathematical formalism with applications in algebraic cryptanalysis. Solving MRHS equation systems is in general a difficult problem. In this article, we investigate the efficient use of genetic algorithms for solving random sparse MRHS systems. Our experiments suggest that the steady-state selection method with low elitism and mutation rate gives the best results. If the systems are sparse, the system size does not have a significant impact on the success of the algorithm. On the other hand, the method is very sensitive to the system density, with the success rate rapidly declining with increased system density.