布尔函数

布尔函数的表示方法非线性度相关免疫性严格雪崩准则和扩散准则.......布尔函数广州大学数学与信息科学学院2007-05-20广州大学数学与信息科学学院裴定一、徐详《信息安全数学基础》布尔函数的表示方法非线性度相关免疫性严格雪崩准则和扩散准则真值表表示法小项表示多项式表示Walsh谱表示.......§11.1布尔函数的表示方法广州大学数学与信息科学学院裴定一、徐详《信息安全数学基础》布尔函数的表示方法非线性度相关免疫性严格雪崩准则和扩散准则真值表表示法小项表示多项式表示Walsh谱表示.定义........以Fn2表示所有n元组(a1,¢¢¢,an),ai2F2构成的集合，f是从Fn2到F2的映射，这里F2表示含有两个元素的有限域，则称f是一个n元布尔函数，记作f(x),x2Fn2。广州大学数学与信息科学学院裴定一、徐详《信息安全数学基础》布尔函数的表示方法非线性度相关免疫性严格雪崩准则和扩散准则真值表表示法小项表示多项式表示Walsh谱表示.......真值表表示广州大学数学与信息科学学院裴定一、徐详《信息安全数学基础》布尔函数的表示方法非线性度相关免疫性严格雪崩准则和扩散准则真值表表示法小项表示多项式表示Walsh谱表示.......由于布尔函数的定义域和值域都是有限集，因此可以把函数的对应关系意义列举出来，这样就得到布尔函数的一种表示方法—真值表表示法。广州大学数学与信息科学学院裴定一、徐详《信息安全数学基础》布尔函数的表示方法非线性度相关免疫性严格雪崩准则和扩散准则真值表表示法小项表示多项式表示Walsh谱表示.Example........从F22到F2的函数f(x)满足f(0,0)=f(1,0)=1,f(0,1)=f(1,1)=0.则函数f(x)可以用真值表表示为x(十进制)x(二进制)f(x)0001101021013110广州大学数学与信息科学学院裴定一、徐详《信息安全数学基础》布尔函数的表示方法非线性度相关免疫性严格雪崩准则和扩散准则真值表表示法小项表示多项式表示Walsh谱表示.......小项表示广州大学数学与信息科学学院裴定一、徐详《信息安全数学基础》布尔函数的表示方法非线性度相关免疫性严格雪崩准则和扩散准则真值表表示法小项表示多项式表示Walsh谱表示.......给定了Fn2到F的函数f(x)，也相当与对任意向量a2Fn2，我们知道其相应的值f(a).是否存在一种类似Lagrange插值之类的方法，可以得到f(x)的表达式呢？.......引人Fn2到F2的函数bc(x)={1x=c;0x6=c.容易验证f(x)=∑c∈Fn2bc(x)f(c).上述表达式就称为小项表示，一般我们把bc(x)记为xc，但其含义并非方幂。广州大学数学与信息科学学院裴定一、徐详《信息安全数学基础》布尔函数的表示方法非线性度相关免疫性严格雪崩准则和扩散准则真值表表示法小项表示多项式表示Walsh谱表示.记号........在小项表示中，设x,c2Fn2，则xc定义为：xc={1x=c;0x6=c.若对xi,ci2F2定义xici={1xi=ci;0xi6=ci.，有xc=xc11xc22¢¢¢xcnn。f(x)的小项表示具有形式f(x)=∑c∈Fn2f(c)xc=∑c∈Fn2f(c)xc11xc22¢¢¢xcnn。广州大学数学与信息科学学院裴定一、徐详《信息安全数学基础》布尔函数的表示方法非线性度相关免疫性严格雪崩准则和扩散准则真值表表示法小项表示多项式表示Walsh谱表示.Example........若布尔函数的真值表为：x00011011f(x)1010写出f(x)的小项表示。.......f(x)=1¢x01x02+0¢x01x12+1¢x11x02+0¢x12x12=x01x02+x11x02。广州大学数学与信息科学学院裴定一、徐详《信息安全数学基础》布尔函数的表示方法非线性度相关免疫性严格雪崩准则和扩散准则真值表表示法小项表示多项式表示Walsh谱表示.......多项式表示广州大学数学与信息科学学院裴定一、徐详《信息安全数学基础》布尔函数的表示方法非线性度相关免疫性严格雪崩准则和扩散准则真值表表示法小项表示多项式表示Walsh谱表示.......在布尔函数的小项表示中，bc(x)=xc起到了基的作用，容易验证其具有多项式表示xc=n∏i=1(xi+ci+1),其中xi是向量xi的第i个分量，ci是c的第i个分量。.......把f(x)=∑cxcf(c)中的xc替换成多项式形式，并展开，化简，我们就能得到f(x)=f(x1,x2,¢¢¢,xn)的多元多项式表示。广州大学数学与信息科学学院裴定一、徐详《信息安全数学基础》布尔函数的表示方法非线性度相关免疫性严格雪崩准则和扩散准则真值表表示法小项表示多项式表示Walsh谱表示.Example........若布尔函数的真值表为：x00011011f(x)1010写出f(x)的多项式表示。.......小项表示为x01x02+x11x02；多项式表示为(x1+0+1)(x2+0+1)+(x1+1+1)(x2+0+1)化简得到f(x)=1+x2。广州大学数学与信息科学学院裴定一、徐详《信息安全数学基础》布尔函数的表示方法非线性度相关免疫性严格雪崩准则和扩散准则真值表表示法小项表示多项式表示Walsh谱表示.定义........布尔函数的多项式表示具有形式f(x)=a0+a1x1+¢¢¢+anxn+a1,2x1x2+¢¢¢+an−1,nxnxn−1+¢¢¢+a1,···,nx1¢¢¢xn.上述形式称为布尔函数的代数标准型。广州大学数学与信息科学学院裴定一、徐详《信息安全数学基础》布尔函数的表示方法非线性度相关免疫性严格雪崩准则和扩散准则真值表表示法小项表示多项式表示Walsh谱表示.定义...........1在f(x)的代数标准型中，非零单项的最大次数称为f(x)的次数，记为degf(x)....2一次布尔函数称为仿射函数;...3常数项为零的仿射函数称为线性函数;...4次数大于1的布尔函数称为非线性函数。广州大学数学与信息科学学院裴定一、徐详《信息安全数学基础》布尔函数的表示方法非线性度相关免疫性严格雪崩准则和扩散准则真值表表示法小项表示多项式表示Walsh谱表示.......Walsh谱表示广州大学数学与信息科学学院裴定一、徐详《信息安全数学基础》布尔函数的表示方法非线性度相关免疫性严格雪崩准则和扩散准则真值表表示法小项表示多项式表示Walsh谱表示.定义........设x=(x1,...,xn),w=(w1,...,wn),x与w的内积定义为x¢w=x1w1+x2w2+¢¢¢+xnwn.广州大学数学与信息科学学院裴定一、徐详《信息安全数学基础》布尔函数的表示方法非线性度相关免疫性严格雪崩准则和扩散准则真值表表示法小项表示多项式表示Walsh谱表示.Example........固定w，让x跑遍Fn2，w¢x中有多少次取1，多少次取0?..........1若w=0，则w¢x总为0；...2当w6=0时，考虑加法群Fn2到F2上的映射f:w!w¢x...3容易验证这是一个群同态，Fn2/(kerf)'Fn2....4Fn2被划分成两个陪集，一个映射为0，另一个映射为1....5这两个陪集的大小是相等的，都是2n/2=2n−1....6所以w¢x在一半情况下为0，一半情况下为1.广州大学数学与信息科学学院裴定一、徐详《信息安全数学基础》布尔函数的表示方法非线性度相关免疫性严格雪崩准则和扩散准则真值表表示法小项表示多项式表示Walsh谱表示.引理........在Fn2上，有：∑x∈Fn2(−1)w·x={0w=02nw6=0由于x,w的对称性，显然也有∑w∈Fn2(−1)w·x={0x=02nx6=0广州大学数学与信息科学学院裴定一、徐详《信息安全数学基础》布尔函数的表示方法非线性度相关免疫性严格雪崩准则和扩散准则真值表表示法小项表示多项式表示Walsh谱表示.定义........n元函数f(x)的布尔函数f(x)的循环Walsh变换定义为Sf(w)=∑x∈Fn2(−1)w·x+f(x).{Sf(w)|w2Fn2}称为f(x)的循环Walsh谱。广州大学数学与信息科学学院裴定一、徐详《信息安全数学基础》布尔函数的表示方法非线性度相关免疫性严格雪崩准则和扩散准则真值表表示法小项表示多项式表示Walsh谱表示..........1(−1)w·x+f(x)的值体现了线性布尔函数L(x)=w¢x与f(x)的关系。...2当L(x0)=f(x0)时，(−1)w·x0+f(x0)为1;...3当L(x0)6=f(x0)时，(−1)w·x0+f(x0)为−1;...4所以当x跑遍Fn2时，我们得到了L(x)与f(x)在Fn2中每一处的关系。...5Sf(w)就是重合点个数减去不重合点的个数。.问题........若知道布尔函数f在每一处的取值，则可以用小项表示求出f的代数表达式。如果知道了f的Walsh谱，是否存在某种形式的反转公式，通过它，能得到f的代数式呢？答案是肯定的。广州大学数学与信息科学学院裴定一、徐详《信息安全数学基础》布尔函数的表示方法非线性度相关免疫性严格雪崩准则和扩散准则真值表表示法小项表示多项式表示Walsh谱表示.定理........设n元布尔函数f(x)的循环Walsh谱为{Sf(w)|w2Fn2}，则(−1)f(x)=2−n∑w∈Fn2Sf(w)(−1)w·x.广州大学数学与信息科学学院裴定一、徐详《信息安全数学基础》布尔函数的表示方法非线性度相关免疫性严格雪崩准则和扩散准则真值表表示法小项表示多项式表示Walsh谱表示.......∑w∈Fn2Sf(w)(−1)w·x=∑w∈Fn2(−1)w·x∑y∈Fn2(−1)w·y+f(y)=∑y∑w(−1)w·(x+y)+f(y)=∑y(−1)y∑w(−1)w·(x+y)=∑y=x(−1)f(y)¢2n=(−1)f(x)¢2n广州大学数学与信息科学学院裴定一、徐详《信息安全数学基础》布尔函数的表示方法非线性度相关免疫性严格雪崩准则和扩散准则真值表表示法小项表示多项式表示Walsh谱表示.定义........设f(x)是n元布尔函数，若f(x)的取值中0的个数和1的个数相等，即¯¯¯{x:f(x)=0,x2Fn2}¯¯¯=¯¯¯{x:f(x)=1,x2Fn2}¯¯¯=2n−1,则称f(x)是平衡的。广州大学数学与信息科学学院裴定一、徐详《信息安全数学基础》布尔函数的表示方法非线性度相关免疫性严格雪崩准则和扩散准则真值表表示法小项表示多项式表示Walsh谱表示.定理........n元布尔函数f(x)是平衡的当且仅当Sf(0)=0...........1Sf(w)表示w¢x与f(x)重合的点的个数减去不重合的点的个数。...2Sf(0)表示0¢x与f(x)的重合点的个数减去不重合点的个数。广州大学数学与信息科学学院裴定一、徐详《信息安全数学基础》布尔函数的表示方法非线性度相关免疫性严格雪崩准则和扩散准则真值表表示法小项表示多项式表示Walsh谱表示.Example........f(x1,¢¢¢,xn)=a0+a1x+¢¢¢+anxn,ai2F2,ai(16i6n)不全为零。f(x1,¢¢¢,xn)是平衡的吗？.......令(a0,a1,¢¢¢,an)=ω,有Sf(0)=∑x∈Fn2(−1)0·x+f(x)=∑x∈Fn2(−1)a0+(a1,···,an)·x=(−1)a0∑x∈Fn2(−1)x·ω=0广州大学数学与信息科学学院裴定一、徐详《信息安全数学基础》布尔函数的表示方法非线性度相关免疫性严格雪崩准则和扩散准则非线性度Bent函数.......§11.2非线性度广州大学数学与信息科学学院裴定一、徐详《信息安全数学基础》布尔函数的表示方法非线性度相关免疫性严格雪崩准则和扩散准则非线性度Bent函数..........1布尔函数可以用线性函数来逼近；...2线性度刻画了布尔函数与线性(仿