Summary Many cyber‐attach schemes and coding models established by algebra tools are build to address the problem of security of cyber‐pysical systems (CPS). As an important field of algebra computing, Boolean Polynomial System Solving (PoSSo) problem plays a very important role in many algebra applications. In this article, we propose an efficient Parallel Boolean Characteristic Set method (PBCS) under the high‐performance computing environment to improve the efficiency of solving Boolean polynomial systems. The PBCS is implemented based on the state‐of‐the‐art Boolean Characteristic Set method (BCS). It adopts a master‐slave parallel pattern, and distributes tasks based on the polynomial sets after initial zero decomposition. We design a strategy of dynamically reallocating tasks to ameliorate load imbalance, which is caused by dynamical zero decomposition of polynomials. Furthermore, we improve its performance by optimizing the parameter settings of PBCS, including the maximum number of polynomial branches that trigger the dynamic allocation policy and the scheduling time. Experimental results with solving several Boolean polynomial systems confirm that PBCS is efficient and scalable, especially for the equations generating from stream ciphers that have block triangular structure. Moreover, the method also has good scalability. It shows a stable speedup as well even extending to the size of thousands of CPU cores.

Solving Boolean polynomial systems as an important aspect of symbolic computation, plays a fundamental role in various real applications. Although there exist many efficient sequential algorithms for solving Boolean polynomial systems, they are inefficient or even unavailable when the problem scale becomes large, due to the computational complexity of the problem and the limited processing capability of a single node. In this paper we propose an efficient parallel characteristic set method called PBCS for solving Boolean polynomial systems under the high-performance computing environment. Specifically, PBCS takes full advantage of the state-of-the-art characteristic set method and achieves load balancing by dynamically reallocating tasks. Moreover, the performance is further improved by optimizing the parameter setting. Extensive experiments are conducted to demonstrate that PBCS is efficient and scalable for solving Boolean equations, especially for the equations rasing from stream ciphers that have block triangular structure. In addition, the algorithm has good scalability and can be extended to the size of thousands CPU cores with a stable speedup.