相关免疫布尔函数的一种构造方法  

A Method for construction of Correlation-Immune Boolean Functions

作　　者：曾本胜[1] 李世取[1] 

机构地区：[1]解放军信息工程学院信息研究系

出　　处：《工程数学学报》1994年第3期65-75,共11页Chinese Journal of Engineering Mathematics

摘　　要：本文证明了布尔函数的谱分解定理，定义了布尔函数的谱（分解）特征向量，给出相应的充要条件，将全部Ｎ元相关免疫布尔函数的构造问题转化为线性方程组的求解问题，为相关免疫布尔函数的构造提供了新的方法。）满足，可求得符合要求的用上述方法我们通过人工计算确定出８６个符合要求的谱特征向量，注意到向量中各分量地位的对称性，并注意到定理４，我们得知全部４无相关免疫的非平凡布尔函数共２×３２４＝６４８个Ｎ＝４，ｍ＝２时，定理６中条件即从后面１１个方程可求得联系（Ⅱ）中的第５～１４个方和即知在（Ⅲ４）下ｂ１、ｂ２、ｂ３、ｂ４全为１（全为０平凡情况），在（Ⅲ４）下ｂ１、ｂ２、ｂ３、ｂ４中有３个取１、１个取０，由此可得全部４元至少２阶相关免疫的非平凡布尔函数所对应的谱特征向量如下：它们所对应的的布尔函数依次是（此结论与［１］ｐ１５５上结论相符），因而４元１阶相关免疫的布尔函数共有６４８－１０＝６３８个。一般情况下，在我们的方法里构造全部Ｎ元相关免疫布尔函数实质上是在定理６中“约束条件”（１）下去求２Ｎ－１个变元、Ｎ个方程的方程组（Ⅱ）所有解，构造全部Ｎ元至少ｍ（≥２）附相关免疫布尔函数实质上是在定理６中“约束条件，（１）下去解２Ｎ－?Abstract This paper gives the proof of the spectrum dccomposition theorm of a Boolean function. the definition of the spectrum characteristic vector of a Boolean function,and a neccssary and sufficient condition of judging whether a vector is a spectrum characteristic vector or not.Consequently the construction problem of all correlation-Immune Boolean functions in x1,…,xN can be reduced to the problem of solving linear equation systems.A new method for the construction of correlation-immune Boolcan functions is proposed.

关 键 词：布尔函数 相关免疫性 谱特征向量 

分 类 号：O153.2[理学—数学]