A Genetic Algorithm for Searching Shortest Lattice Vector of SVP Challenge
Ding, Dan, Guizhen Zhu, Xiao-Yun Wang · 2014
In this paper, we propose a genetic algorithm for solving the shortest vector problem (SVP) based on sparse integer representations of short vectors in lattices as chromesomes, which, we prove, can guarantee finding the shortest lattice vector under a Markov chain analysis. Moreover, we also suggest some improvements by introducing heuristic techniques: local search and heuristic pruning. The experimental results show that the genetic algorithm runs rather good on the SVP challenge benchmarks[32], and performs much faster than other practical algorithms: the Kannan-Helfrich enumeration and enumeration with conservative pruning.