A hybrid CPU-MIC parallel Gaussian elimination algorithm for solving Gr?bner bases in binary field

摘要

Gr?bner bases method is a classic method for solving polynomial system. Currently, F4 algorithm is one of the fastest algorithms for computing Grobner bases, and the main computational cost in F4 is Gaussian elimination of F4 matrix. We first analyze the characteristics of Gaussian elimination algorithm proposed by Lachartre especially for computing F4 matrix in binary fields, then present a CPU+MIC heterogeneous parallel algorithm for pivot row reduction, which is one of the most time-consuming steps, and utilize a series of performance optimization techniques, such as OpenMP multi-thread organization, SIMD vectorization, memory access optimization, to improve the efficiency of the algorithm. The efficiency of the algorithm is demonstrated by the experiments about well-known HFE cryptosystem. For instance, for a medium size problem such as HFE80, the performance of optimized heterogeneous parallel program is about 1.732 times than that of multi-thread program implemented on CPU.