資源描述：
《布爾函數(shù)的代數(shù)厚度》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在工程資料-天天文庫。
1、第7期電子學報Vol.37No.72009年7月ACTAELECTRONICASINICAJuly2009布爾函數(shù)的代數(shù)厚度1121周宇,汪小芬,羅彥鋒,肖國鎮(zhèn)(1.西安電子科技大學綜合業(yè)務網(wǎng)理論及關鍵技術國家重點實驗室,陜西西安710071;2.蘭州大學數(shù)學與統(tǒng)計學院,甘肅蘭州730000)摘要:基于布爾函數(shù)的代數(shù)次數(shù)和代數(shù)厚度,給出了布爾函數(shù)和其分解函數(shù)的代數(shù)厚度的關系,利用遞歸和反證法導出了n元布爾函數(shù)代數(shù)厚度的上界是233(n-1),這個上界回答了“是否存在代數(shù)厚度大于233(n-1)的n元布爾函數(shù)”這個公開問題.在此基礎上改進了n元k(2≤k≤(n-1)/2)次基本對稱
2、布爾函數(shù)的代數(shù)厚度的上界,同時也得到了布爾函數(shù)的代數(shù)厚度的一些性質.關鍵詞:布爾函數(shù);代數(shù)正規(guī)型;代數(shù)厚度;基本對稱布爾函數(shù)中圖分類號: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)概念,用來衡量一個布爾函數(shù)在仿射變換
6、下1引言其代數(shù)正規(guī)型中單項式的個數(shù)多少,在利用組合理論的布爾函數(shù)在科學技術的許多領域有重要的應用,如基礎上研究了代數(shù)厚度滿足一定條件的布爾函數(shù)的個通信和密碼學等方面.在流密碼和分組密碼中除了研究數(shù)界,提出了關于任意元布爾函數(shù)代數(shù)厚度的公開問布爾函數(shù)的非線性度外,還得考慮另外的兩個指標:代題,但并未對一般布爾函數(shù)的代數(shù)厚度進行討論.數(shù)次數(shù)和代數(shù)正規(guī)型中單項式(非零的系數(shù))的個數(shù),本文中針對一般布爾函數(shù),研究了代數(shù)厚度的一些Knudsen和Lai分別提出針對分組密碼的高階差分攻性質,給出了布爾函數(shù)與其分解函數(shù)的代數(shù)厚度之間的[1,2]擊依靠的就是布爾函數(shù)的最大代數(shù)次數(shù).而由非線關系,
7、由此解決了Carlet提出的對于任意布爾函數(shù)代數(shù)性布爾函數(shù)組合的多個線性反饋移位寄存器(LFSR)生厚度的公開問題,進而改進了基本對稱布爾函數(shù)給的代成的序列中,其線性復雜度是由這個布爾函數(shù)代數(shù)正規(guī)數(shù)厚度上界,同時得到布爾函數(shù)的代數(shù)厚度的一些性質.型中單項式的個數(shù)和代數(shù)次數(shù)來決定的,所以文獻[3]2預備知識指出在線性反饋移位寄存器(LFSR)的非線性布爾函數(shù)n選取中,必須考慮高的代數(shù)次數(shù)和多的單項式.在密碼一個n元布爾函數(shù)f(x)=f(x1,x2,?,xn)是指F2攻擊中使用的布爾
