资源描述：
《布尔函数的代数厚度》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第7期电子学报Vol.37No.72009年7月ACTAELECTRONICASINICAJuly2009布尔函数的代数厚度1121周宇,汪小芬,罗彦锋,肖国镇(1.西安电子科技大学综合业务网理论及关键技术国家重点实验室,陕西西安710071;2.兰州大学数学与统计学院,甘肃兰州730000)摘要:基于布尔函数的代数次数和代数厚度,给出了布尔函数和其分解函数的代数厚度的关系,利用递归和反证法导出了n元布尔函数代数厚度的上界是233(n-1),这个上界回答了“是否存在代数厚度大于233(n-1)的n元布尔函数”这个公开问题.在此基础上改进了n元k(2≤k≤(n-1)/2)次基本对称
2、布尔函数的代数厚度的上界,同时也得到了布尔函数的代数厚度的一些性质.关键词:布尔函数;代数正规型;代数厚度;基本对称布尔函数中图分类号:TN91811文献标识码:A文章编号:037222112(2009)0721412204AlgebraicThicknessofBooleanFunctions1121ZHOUYu,WANGXiao2fen,LUOYan2feng,XIAOGuo2zhen(1.StateKeyLaboratoryofIntegratedServiceNeworks,XidianUniversity,Xi’an,Shaanxi7100711,China;2.Sch
3、oolofMathematicsandStatistics,LanzhouUniversity,Lanzhou,Gansu730000,China)Abstract:BasedonthealgebraicdegreeandthealgebraicthicknessofBooleanfunctions,therelationshipofalgebraicthick2nessbetweenaBooleanfunctionandtheirdecomposingBooleanfunctionsisgiven,andtheupperboundonthealgebraicthicknesso
4、fBooleanfunctionswithnvariablesis233(n-1)bytherecurrencemethodandthereductiontoabsurdity.Theupperboundanswerstheopenproblem“:whetherthereexistsaBooleanfunctionwithnvariableswhosealgebraicthicknessisstrictlygreaterthan233(n-1)”.Attheendofthispaper,accordingtothisfactanupperboundonalgebraicthic
5、knessofelementarysymmetricBooleanfunctionsofnvariableswithalgebraicdegreek(2≤k≤(n-1)/2)isimproved,andsomepropertiesonalgebraicthick2nessofBooleanfunctionsarederived.Keywords:Booleanfunctions;algebraicnormalform;algebraicthickness;elementarysymmetricBooleanfunctionsThickness)概念,用来衡量一个布尔函数在仿射变换
6、下1引言其代数正规型中单项式的个数多少,在利用组合理论的布尔函数在科学技术的许多领域有重要的应用,如基础上研究了代数厚度满足一定条件的布尔函数的个通信和密码学等方面.在流密码和分组密码中除了研究数界,提出了关于任意元布尔函数代数厚度的公开问布尔函数的非线性度外,还得考虑另外的两个指标:代题,但并未对一般布尔函数的代数厚度进行讨论.数次数和代数正规型中单项式(非零的系数)的个数,本文中针对一般布尔函数,研究了代数厚度的一些Knudsen和Lai分别提出针对分组密码的高阶差分攻性质,给出了布尔函数与其分解函数的代数厚度之间的[1,2]击依靠的就是布尔函数的最大代数次数.而由非线关系,
7、由此解决了Carlet提出的对于任意布尔函数代数性布尔函数组合的多个线性反馈移位寄存器(LFSR)生厚度的公开问题,进而改进了基本对称布尔函数给的代成的序列中,其线性复杂度是由这个布尔函数代数正规数厚度上界,同时得到布尔函数的代数厚度的一些性质.型中单项式的个数和代数次数来决定的,所以文献[3]2预备知识指出在线性反馈移位寄存器(LFSR)的非线性布尔函数n选取中,必须考虑高的代数次数和多的单项式.在密码一个n元布尔函数f(x)=f(x1,x2,⋯,xn)是指F2攻击中使用的布尔
