论文部分内容阅读
为了抵制代数攻击，布尔函数应当具有较高的代数免疫。在布尔函数中，对称布尔函数又是其中重要的一类。一个n元布尔函数可以转化为一个长为2的向量，而对于对称布尔函数，重量相等的向量，其函数值相等。任意一个n维向量x其重量满足：0≤wt(x)≤n。这样，就可以把一个n元对称布尔函数转化为一个n+1维向量v<,f>=(v<,f>(0)，v<,f>(1)…v<,f>(n))，其中V<,f>(i)表示重量为i的函数值，0≤i≤n，此向量v<,f>称为对称函数f的向量值(VV)，极大地减少了对存储空间的需求，并且在软件应用中发挥着重要作用。而每个对称函数都可写成齐次对称函数σ<,i>(0≤i≤n)为基的线性组合其中向量λ<,f>=(λ<,f>，(0)，λ<,f>(1)…λ<,f>(n))称为简化的ANF向量。本文主要的工作都是基于V<,f>(i)进行构造。
第一章介绍了布尔函数的基本知识，对其中的一些性质进行了简单的推广。第二章从代数免疫的定义出发，通过零化子的性质，得到代数免疫的一些结论，并且给出了一些例子和推论。一个对称布尔函数在仿射变换下不一定映成一个对称布尔函数，第三章研究了对称布尔函数在哪些仿射变换下是保对称，得到了两个定理。
n元布尔函数的代数免疫的上界是[n/2]。当达到这个界时，我们称布尔函数具有最大的代数免疫。从而最大代数免疫布尔函数的构造就更为重要了，在第四章中，我们分n是奇数，偶数的情况，构造出了一系列具有最大代数免疫的布尔函数。