基于Groebner基方法的布尔多项式方程组求解算法的研究与实现

Solving systems of polynomial equations is a fundamental problem in algebra, in which solving systems of Boolean polynomial equations is a very important sub-problem. Studies on solving systems of Boolean polynomial equations have extensive significances and applications, particularly in cryptanalysis. Groebner basis method is one of major methods for solving systems of Boolean polynomial equations at present, but unfortunately, there is no available and efficient implementations based on Groebner basis and related algorithms in China now, which means domestic researchers have to use released softwares and hardly make any changes or integrate new ideas to these complied programs. This project will focus on studying algorithms for solving systems of Boolean polynomial equations based on Groebner basis methods in theory, and will also present efficient implementations both on personal computers and parallel machines. The project includes the following three stages. Firstly, existing Groebner basis algorithms will be studied further, including settling unsolved mathematical problems and optimizing or improving existing Groebner basis algorithms in theory. Secondly, based on Groebner basis methods, algorithms for solving systems of Boolean polynomial equations will be seriously studied and efficiently implemented on personal computers. Finally, parallel algorithms will be studied and efficiently implemented on parallel machines, such that many practical problems can be solved and effective analysis of cryptosystems becomes available.

多项式方程组求解问题是代数学的核心问题之一，布尔多项式方程组求解问题是其中一类非常重要的子问题。研究布尔多项式方程组的求解算法具有广泛的现实意义和应用，特别是在密码分析领域。Groebner基方法是求解布尔多项式方程组的最主要方法之一，然而国内还没有基于Groebner基及其相关算法的高效率实现的程序。本项目将主要从理论和实现两个方面研究基于Groebner基方法的布尔多项式方程组求解算法，具体将完成以下三方面的工作：首先，研究和改进现有Groebner基算法的理论，解决现有算法中遗留的数学问题并尝试从理论上对这些算法进行优化和改进；其次，研究基于Groebner基方法的布尔多项式方程组求解算法，并在PC机上高效率地实现；最后，研究并在并行平台上实现基于Groebner基方法的布尔多项式方程组的并行求解算法，利用高性能并行计算机切实解决实际问题并行之有效地对大规模密码系统进行分析和攻击。

多项式方程组求解问题是代数学的核心问题之一，布尔多项式方程组求解问题是其中一类非常重要的问题。研究布尔多项式方程组的求解算法具有广泛的现实意义和应用，特别是在密码分析领域。Groebner基方法是求解布尔多项式方程组的最主要方法之一，然而本项目立项时国内尚没有基于Groebner基及其相关算法的高效率实现的程序。本项目按照研究计划，从理论和实现两个方面研究了基于Groebner基方法的布尔多项式方程组求解算法，具体来说完成了以下三方面的工作：首先，提出了新型的Groebner基算法实现框架，并给出了算法中“符号处理”函数的一种高效率实现，显著提高了算法在实现层面的效率；其次，在理论上发现了Groebner基算法——GVW算法在计算非齐次系统Groebner基时效率较低的原因，并给出了改进算法M-GVW，改进算法在HFE系统的计算中体现出了显著的效率优势；第三，针对签名Groebner基算法中所涉及的单向消去算法，提出了一种新型的轮换技术，使得通用线性代数程序包经过简单修改后便可以完成签名Greobner基所需的单向消去过程。基于以上的成果，本项目给出了Greobner基算法在布尔多项式环上的高效率实现，算法程序集成了本项目所研究的所有新理论新技术，同时融合了多线程并行加速技术。算法在大多数密码问题的计算效率都超过了目前公开领域公认最快的闭源商业软件Magma，本项目研究中实现的Groebner基算法，使我们在密码分析方面的能力得到了显著提升，从而可以挑战一些之前难以企及的难题。