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

摘要

分组加密算法的密文可以看作输入的多项式布尔函数值,研究多项式布尔函数表达式对加密算法的代数分析具有重要意义.提出一种新的多项式布尔函数表示法,首先把单项式映射为一种简单的数据类型,使用单链线性表组结构表示多项式,在此结构上实现单项式的插入、删除、查找等操作.基于多项式的这种表示,给出了多项式的加法、乘法以及求多项式值的算法.通过无密钥的Simon-V算法实验进一步验证了我们提出的多项式表示法的理论正确性和实现可行性.最后,在空间、时间和实现复杂度方面,与经典的BDD和系数矩阵表示法进行了比较,分析了这种新的多项式表示法在某些方面的优势.