多元多项式布尔函数的链表表示及实现  

The Linked List Representation and Realization of Multivariate Polynomial Boolean Function

作　　者：陈逢林 胡永模 Chen Fenglin;Hu Yongmo(School of Mathematics and Computational Science,Anqing Normal University,Anqing,Anhui 246133)

机构地区：[1]安庆师范大学数理学院,安徽安庆246133

出　　处：《池州学院学报》2020年第6期33-39,共7页Journal of Chizhou University

基　　金：安徽省高校自然科学重点研究项目(KJ2019A0580);安庆师范大学教学研究项目(2018aqnuxfsyxmx003)。

摘　　要：分组加密算法的密文可以看作输入的多项式布尔函数值,研究多项式布尔函数表达式对加密算法的代数分析具有重要意义。提出一种新的多项式布尔函数表示法,首先把单项式映射为一种简单的数据类型,使用单链线性表组结构表示多项式,在此结构上实现单项式的插入、删除、查找等操作。基于多项式的这种表示,给出了多项式的加法、乘法以及求多项式值的算法。通过无密钥的Simon-V算法实验进一步验证了我们提出的多项式表示法的理论正确性和实现可行性。最后,在空间、时间和实现复杂度方面,与经典的BDD和系数矩阵表示法进行了比较,分析了这种新的多项式表示法在某些方面的优势。The cipher-text of block encryption algorithm can be regarded as the polynomial Boolean function value of input. It is very important to study the representation of polynomial Boolean function for algebraic analysis of encryption algorithm. A new polynomial representation of Boolean functions is proposed. Firstly, monomial is mapped to a simple data type. A linear single linked list structure is used to represent polynomial. The inserting,deletion, search and other operations of monomial can be done on this structure. Based on this new representation,these algorithms are given for the addition and multiplication of polynomials and the calculation of the polynomial value. The experiment of no-key Simon-V algorithm proves the correctness and feasibility of the proposed polynomial representation. Finally, we compare this new representation with classical BDD and coefficient matrix representation from space, time and implementation complexity, and analyze its comparative advantages in some aspects.

关 键 词：积分攻击 布尔函数 单链线性表 二元决策图 系数矩阵表示法 

分 类 号：O174[理学—数学]