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

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

项目编号： No.11301523

项目类型： 青年科学基金项目

立项/批准年度： 2014

项目学科： 数理科学和化学

项目作者： 孙瑶

作者单位： 中国科学院信息工程研究所

项目金额： 22万元

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

中文关键词： 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

英文关键词： Groebner basis；systems of Boolean polynomial equations；algorithm；implementation；