关键词: F4算法, 二元域, 布尔矩阵乘, 分布式异构并行

Abstract:

The Boolean polynomial solution is a key step in the analysis of cryptographic algebra, and the F4 algorithm is an efficient algorithm for Boolean polynomial solution. We analyze the Gaussian elimination algorithm designed by Lachartre for F4 matrix, then design and implement the distributed heterogeneous (CPU + MIC) parallel algorithm for the time consumption calculation of Boolean matrix multiplication. The Boolean matrix differs from ordinary matrixes mainly in the valuetaking intervals of matrix elements. The optimization method of the general matrix multiplication cannot satisfy the Boolean matrix multiplication because the Boolean matrix element (0,1) leads to the particularity of the matrix multiplication operation. We realize the distributed heterogeneous parallel algorithms of Boolean matrix multiplication by optimizing its performance respectively on binary domain matrix storage, OpenMP multithreading organization, fetch, task partition and scheduling, etc. By randomly generating the Boolean matrix tests, the optimized distributed heterogeneous parallel program achieves an acceleration ratio of 2.45 compared with the distributed isomorphism parallel program, which shows a good performance improvement.

Key words: F4 algorithm, binary domain, Boolean matrix multiplication, distributed heterogeneous parallel