互补对称布尔函数的非线性度  

The Nonlinearity of Complementary Symmetric Boolean Functions

作　　者：陈银冬[1] 陆佩忠[2] 

机构地区：[1]汕头大学工学院计算机系,广东汕头515063 [2]复旦大学计算机科学技术学院,上海200433

出　　处：《计算机工程与科学》2011年第10期51-56,共6页Computer Engineering & Science

基　　金：国家自然科学基金资助项目(60673082);教育部全国优秀博士学位论文作者专项基金资助项目(200084);汕头大学科研启动基金资助项目(NTF10018)

摘　　要：互补对称布尔函数是一类特殊的对称布尔函数。在所有代数免疫最优的对称布尔函数中,有相当的比例均属此类函数。特别是当变元数量为2m元时,有2/3比例的代数免疫最优对称布尔函数都是互补对称布尔函数。通过布尔函数非线性度、Walsh谱和Krawtchouk多项式间的关系,计算出互补对称布尔函数的非线性度。结果表明,任意n元互补对称布尔函数的非线性度为2n-1-1/2[nn/2]Complementary symmetric Boolean functions are a special class of symmetric Boolean functions. A high proportion of symmetric Boolean functions with optimum algebraic immunity are complementary symmetric Boolean functions. Especially for the case of 2m variables, it reaches a high proportion of 2/3. By the relationship between the nonlinearity and the Walsh spectrum of the Boolean functions, and that between the Walsh spectrum of the Boolean functions and the Krawtchouk polynomial, the nonlinearity of complementary symmetric Boolean functions is determined. As a result, the nonlinearity of all complementary symmetric Boolean functions with n variables is 2^n-1-1/2（n/2^n）.

关 键 词：非线性度 代数免疫度 互补对称布尔函数 对称布尔函数 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]