旋转对称布尔函数线性结构的个公开问题2Twoopenproblemsabout.PDFVIP

第34 卷第3 期 通 信 学 报 Vol.34 No. 3 2013 年3 月 Journa l on Communications March 2013 doi:10.3969/j .issn.1000-436x.2013.03.022 旋转对称布尔函数线性结构的2 个公开问题 1,2 1 赵亚群 ，李旭 （1. 信息工程大学 四院，河南 郑州 450002；2 . 信息工程大学 数学工程与先进计算国家重点实验室，河南 郑州 450002 ） 摘 要：证明了代数次数为n 1 的偶变元平衡旋转对称布尔函数不存在非零线性结构这个公开问题，给出了代 数次数为n 2 的奇变元旋转对称布尔函数不存在非零线性结构这个公开问题成立的充分条件和不成立的必要 条件。 关键词：布尔函数；旋转对称；线性结构；代数次数 中图分类号：TN918.1 文献标识码：A 文章编号：1000-436X (20 13)03-017 1-04 Two open problems about the liner structure of rotation symmetric Boolean functions ZHAO Ya-qun1,2 , LI Xu 1 (1. The Fourth Institute, Information Engineer ing University, Zhengzhou 450002, China ; 2. State K ey Laboratory o f Mathematica l Engineer ing and Advanced Comp uting, Information Engineer ing University, Zhengzhou 450002, China) Abstract: One op en prob lem that the b alanced rotation symm etric Boolean functions with degree n 1 on even numb er of variab les have no non-zero linear structure was proved . A suffic ient and a necessary condition w ere resp ectively given when another op en prob lem that th e rotation symm etric ean functions with degr ee n 2 on odd numb er of va- riab les have no non-zero lin ear structur e succeed or not. Key words: Boolean functions; rotation symmetric ; linear structure; algebraic degree n 1次偶变元平衡 RSBF 和n 2 次奇变元 RSBF 1 引言 均不存在非零线性结构。当n ≤10 时，Elsheh 通过 旋转对称布尔函数(