高次非正规布尔函数的存在性  

The existence of nonnormal Boolean functions with high algebraic degrees

作　　者：王维琼[1] 

机构地区：[1]长安大学理学院,陕西西安710064

出　　处：《西北大学学报（自然科学版）》2013年第4期527-529,共3页Journal of Northwest University（Natural Science Edition）

基　　金：国家自然科学基金青年基金资助项目(61202437);中央高校基本科研业务基金资助项目(CHD2010JC101)

摘　　要：基于布尔函数代数正规型及正规性的定义和性质,通过计数的方法,研究了非正规且具有较高代数次数的布尔函数的存在性。结论表明,随着变元个数的不断增大,高次非正规布尔函数在整个函数空间中的比率越来越大,当变元个数趋于无穷时比率趋近于1。该结论为对称密码中密码函数的选取提供了支持。特别地,指出了四次非正规布尔函数变元个数的下界。Based on the definition and properties of the algebraic normal form and normality of Boolean functions, the existence of nonnormal Boolean functions with high algebraic degrees was proved. By counting, it was shown that the ration of the nonnormal Boolean functions with high degress grows with the number of variables, and tends to 1 when it becomes infinite. Especially, the minimum bound of the number of variables of nonnormal Boolean functions with algebraic degree 4 was provided.

关 键 词：非正规 代数次数 布尔函数 仿射子空间 代数正规型 

分 类 号：TN918.1[电子电信—通信与信息系统]