资源描述：
《弹性函数的计数.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、2OO2年12月北京邮电大学学报Dec.2OO2第25卷第4期JOurnalOfBeijingUniversityOfPOstsandTelecOmmunicatiOnsVOl.25NO.4文章编号:1OO7-5321(2OO2)O4-OO21-O5弹性函数的计数温巧燕1,杨义先2(1-北京邮电大学理学院,北京1OO876;2-北京邮电大学信息工程学院,北京1OO876)摘要:通过构造性的方法讨论弹性函数的计数,给出了弹性性最佳时的精确计数.关键词:弹性函数;正交矩阵;相关免疫函数;计数中图分类号:TN911
2、.22文献标识码:AEnumerationofResilientFunctions12WENOiaO-yan,YANGYi-xian(1-SchOOlOfScience,BeijingUniversityOfPOstsandTelecOmmunicatiOns,Beijng1OO876,China;2-InfOrmatiOnEngineeringSchOOl,BeijingUniversityOfPOstsandTelecOmmunicatrOns,Beijing1OO876,China)Abstract:E
3、numeratiOnOfresilientfunctiOnsisdiscussedinthispaper.ByapplyingOrthOgOnalarray,theexactnumberOfitisfOundfOrsOmespecialcases.Keywords:resilientfunctiOns;OrthOgOnalarray;cOrrelatiOn-immunefunctiOns;numeratiOn1若干定义与预备定理弹性函数的引入是为了抗信息泄露[1,2],文献[3~8]对弹性性能界和弹性函数的构
4、造进行了研究,文献[9]用矩阵方法给出一种递归构造法,本文将通过构造性的方法讨论弹性函数的计数.定义1设F(I)=(fnnm的1(I),~,fm(I)),mn,IEGF(2),F(I)是GF(2)-GF(2)多输出布尔函数,1tn,若V{ztm1,~,zt};{1,2,~,n},c=(c1,~,ct)EGF(2),6EGF(2)p(F(I)=6)=p(F(I)=6IIz=c1,~,Iz=ct),则称F(I)是t阶相关免疫函数.m=1时,简称1t为相关免疫函数.定义2设A是GF(2)上的t>n矩阵,1tn,若A
5、的行互不相同,由A的任t列组成的t>t矩阵的行中,GF(2)t中的向量均出现且出现的次数相同,则称A是GF(2)上的t-正交矩阵,记为0A这里,t=/2t/(t,n,2),.收稿日期:2OO1-1O-12基金项目:国家重点基础研究发展规划资助项目(G1999O358O5);国家杰出青年基金资助项目(69425OO1);国家自然科学基金资助项目(69882OO2,6OO73O49);国家高等学校骨干教授资助计划资助项目.作者简介:温巧燕(1959),女,北京邮电大学教授,博士生导师.22北京邮电大学学报第25卷
6、设A是GF(2)上的Z>n矩阵即A的行是GF(2)n上的向量若A的行互不相同为了方便在不引起混淆的情况下将A的行向量的集合仍用A记这时将GF(2)上的Z>n矩阵n的子集A(即A;GF(2)nA和GF(2))等同看等.定义3设A均是GF(2)上的Z>nt-正交矩阵若GF(2)n的每个向量必且只在10Akk一个A行中出现即A互不相交且GF(2)nz(1{z{k)z(1{z{k)=UAz则称A10Ak是1n的一个t-正交分划这里k=2mnn-mtGF(2)Z=2/k=22IZ.定义4设F(I)是GF(2)nm的函数
7、若对任意的BEGF(2)m-1-GF(2)F(B)={IIn-mF(I)=B}有相同个数的元素即i{IIF(I)=B}=2(i表示集合的基数)则称F(I)是无偏的.定义5设F(I)是GF(2)nm的函数t20若V=(t-GF(2)10t)EGF(2){z10n-tm的无偏函数则称F(I)是t-zt};{120n}F(IIIz=10Iz=t)是GF(2)-GF(2)1t弹性函数记为(nmt)-F.预备定理1设F(I)是GF(2)nm的函数F(I)是无偏的t阶相关免疫函数@-GF(2)F(I)是t-弹性函数.无偏
8、函数就是0-弹性函数所以预备定理1中t可以是0.预备定理2设F(I)是GF(2)nm的函数F(I)是无偏的t阶相关免疫函数@-GF(2)是GF(2)n的一个t-正交分划其中AB0ABm12mmAB={IIF(I)=Bz}BzEGF(2)1{z{2z关于这些结论的证明可从定义直接推导或在相关文献[89]中查到.2弹性函数的计数根据预备定理1和2构造t-弹性函数等价于构造于GF(2)n的一个t-正交分划
