（基础数学专业论文）对称布尔函数代数免役的研究.pdf

张红艳对称布尔函数代数免疫的硼f 究 摘要 为了抵制代数攻击，布尔函数应当具有较高的代数免疫。在向尔函数中，对 称佰尔函数义是其中重要的- 类。一个 元布尔函数可以转化为一个长为2 ”的向 量，而对于对称布尔函数，重量相等的向量，其函数值相等。任意个n z z - 。亘i 6x 其重量满足：0 w f ( j ) n 。这样，就可以把一个h7 己对称布尔嘲数转化为一个n + l 维向量v ，= ( v ，( 0 ) ，v ，( 1 ) ，v ，( m ) ) ，其中”，( f ) 表示重量为i 的函数值，0 ，”，此向 量v ，称为对称晒数厂的向量值( v v ) ，极大地减少了对存储窄间的需求，并且在 软什应用中发挥着重要作用。而每个对称函数都可弓成齐次对称函数j ，( 0 i h ) 为基的线降组合、( ；) = 鱼- ( f ) q ，其中乃( j ) 5 雹v ，( ) ，o f ， 其中向量 丑，：( 2 ，( o ) ，a ，( 1 ) 旯，( n ) ) 称为简化的a n f 向量。本文主要的工作都是基f ”，( f ) 进 行构造。 第一章介绍了布尔函数的基本知识，对其中的一些性质进行了简单的推广。 第二章从代数免疫的定义出发，通过零化子的性质，得到代数免疫的一些结论， 并且给出了一些例子和推论。一个对称布尔函数在仿剁变换r 不一定映成一个刈 称布尔函数，第三章研究r 对称布尔函数在哪些仿射变换下是保对称，得到了两 个定理。 定理3 设t ：；- 一x e o 石，- ，( ；) 为m 元对称句尔函数，则。f ( x e ”0 6 ) 为行元对称布尔 函数的允要条件6 l ，0 定理4 设? ：x 一，x f ( xj ，屯，_ ) - ( x 2 + x j + + _ ，x l + 而+ + ，。，z l + z i + + 一1 ) 其中h 为偶数则厂( ；) 为”元对称布尔函数营厂( 订) 为”元对称布尔函数， 扬州大学硕l 学位论文 n i 布尔函数的代数免疫的卜界是f j 。当达到这个界时，我们称布尔函数具 有最大的代数免疫。从而最大代数免疫布尔函数的构造就更为重要了，在第四= i 章 中，我们分n 是奇数，偶数的情况，构造m 了一系列具有最大代数免疫的布尔函 数。 构造1 1 】设，是n 元对称布尔函数，当”是奇数时，其向量值为v ，( f ) = ；筝! ；兰 则a i ( ) = 半 引理7 1 1 1 】_ 蹬f 为一元对称布尔函数，令h = 2 k + 1 ，且厂为平凡的平衡函数， 则a i ( f ) ：+ 1 v r ( j ) ： 三 c 出1 o f 鲰，其中c f ( 2 ) k i 咒 构造2 1 设厂是。，二对称布尔函数，当”是偶数时，其向量值为v ，( f ) = f ? ：i ；! ： 则a l ( f ) = ； 构造3 定理5 设厂是n 元对称布尔函数，”为偶数，其向量值v = _ ，o “一其中 0 ， 号，定义j 为满足2 7 r 2 川的整数，任意j s l t 三s ，2 s 2 + l ，若 j ；s t o o d 2 ”1 ，则a l ( f ) = 号 等价命题：设是肝元对称布尔函数，h 为偶数，其向量值v ，= ”，o “- r ，其中0 r 号， 若；三；，则爿( 厂) = j 构造4 定理6 设厂是n 元对称稚尔函数，其向量值0 = ”，05 ，其中o f 号， 若 = 2 5 + 2 t ，其中s 为正整数，则a l ( f ) = ： 关键词：布尔函数，代数攻击，代数免疫，零化了，平衡的，平凡平衡的， 扬州大学硕士学位论文 a b s t r a c t 2 t or e s i s ta l g e b r a i ca t t a c k s ，b o o l e a nf u n c t i o n ss h o u l dh a v eh i 曲a l g e b r a i ci m m u n i t y s y m m e t r i cb o o l e a nf u n c t i o n sa r ea l li m p o r t a n tc l a s so fb o o l e a nf u n c t i o n s a n de a c h s y m m e t r i cf u n c t i o nc a r lb ew r i t t e ni n t oal i n e a rc o m b i n a t i o no f h o m o g e n e o u ss y m m e t r i c f u n c t i o n s i nc h a p t e r1 ，w ei n t r o d u c et h eb a s i cc o n c e p t sa b o u tb o o l e a nf u n c t i o n s ，a n d g e ts o m ee a s yg e n e r i z a t i o n so fs o m ep r o p e r t i e s i nc h a p t e r2 ，f r o mt h ed e f i n i t i o no f b o o l e a nf u n c t i o na n dt h ep r o p e r t i e so fz e r of a c t o r s ，w eg e ts o m er e s u l t so nt h ea l g e b r a i c i m m u n i t yo fs y m m e t r i cb o o l e a nf u n c t i o n s ，s o m ee x a m p l e sa n dc o r o l l a r i e sa r eg i v e n u n d e ra f f i n et r a n s f o r m a t i o n s ，as y m m e t r i cb o o l e a nf i m c t i o nn e e dn o tm a pi n t oa n o t h e r , i nc h a p t e r3 ，w es t u d yt h ea t t m et r a n s f o r m a t i o n su n d e rw h i c hs y m m e t r i cb o o l e a n f u n c t i o n sp r e s e r v et h es y m m e t r i cc h a r a c t e lg i v et w ot h e o r e m s ，a n dc o n s t r u c ts o m e e x a m p l e s ，o nt h es t u d yo ft h ea l g e b r a i ci m m u n i t yo fb o o l e a nf i m c t i o n s ，w eh a v eg r e a t i n t e r e s t so nt h ep r o b l e mt og e tm a x i m u ma l g e b r a i ci m m u n i t y , i nc h a p t e r4 ，o nt h eo d d a n de v e nc o n d i t i o n s ，w ec o n s t r u c tas e r i e so fb o o l e a nf u n c t i o n sh a v i n gm a x i m u m a l g e b r a i ci m m u n i t y 张红艳对称布尔函数代数免役的研究 0 引言 在当今的网络信息时代，信息的安全保密致关重要，而这些保密的实施大多 是通过函数来实现的。在这些函数中，布尔函数又是一类比较重要的函数，而对 称的布尔函数又是布尔函数的一种特殊情况。 一个玎元布尔函数可以转化为一个长为2 ”的向量，而对于对称布尔函数，重 量相等的向量，其函数值相等。一个刀维向量x 其重量满足：0 w t ( x ) 玎。这样， 就可以把一个胛元对称布尔函数转化为一个n + l 维向量，极大地减少了对存储空间 的需求，并且在软件应用中发挥着重要作用。很多研究者对对称布尔函数的密码 性质做出了重要贡献。在【7 】中，m a r i o n v i d e a n 给出了对称布尔函数的一些性质。 最近，在流密码中，代数攻击已经成为一个重要的工具，为了抵制这种攻击， m e i e r 在 2 l q 】提出了代数免疫的概念。2 0 0 3 年，在【3 】中，c o u r t i o i s 和m e i e r 证明 了拧元布尔函数的代数免疫的上界是胡。当达到这个界时，我们称布尔函数具有 最大的代数免役。从而最大代数免疫布尔函数的构造就更为重要了。2 0 0 6 年，在 【1 1 中，d a l a i , m a i t r a 和s a r k a r , 给出了两类具有最大免役的布尔函数的构造，并且提 供了一种证明方法。在【4 】中，d a l a i 证明了当n 为奇数时，刀元具有最大免疫的布 尔函数厂必须满足，为平衡的这一结论。在【5 】中，s a r k c r 与m a i t r a 研究了 s 1 6 的 奇数，他们发现具有最大代数免役的函数除了一= 1 3 外，都是平凡平衡的。并研究 了 = 1 3 时的布尔函数，其代数免役小于等于3 。在【6 】中，g a t h e n 与r o c h e 研究了 珂1 2 8 的所有奇数，发现除了一 1 3 ，2 9 ，3 1 ，3 3 ，3 5 ，4 1 , 4 7 ，6 1 ，6 3 ，7 3 ，9 3 ，1 0 3 外，其余 所有的1 元布尔函数达到最大免役的都是平凡平衡的。结合【5 】和【6 】的研究，2 0 0 6 年，在 1 1 q a ，n a l i 与w e n f e n g q i 给出了行为奇数时，对称布尔函数具有最大代 数免役的一个充要条件。 本文在第一章中先介绍了布尔函数的基本知识，对其中的一些性质进行了简 扬州大学硕士学位论文 4 单的推广。在第二章中，从代数免役的定义出发，通过零因子的性质，得到代数 免役的一些结论，并从给出了一些例子中得到一些推论结果。在第三章中研究了 对称布尔函数在仿射变换下是否保对称的情况，在这里给出了3 个命题和两个定 理，为第四章中的证明服务。在第四章中，分刀是奇数，偶数的情况进行讨论，对 于月为奇数时，具有最大代数免役的函数比较有规则，通过构造1 与引理7 来说明。 对于以为偶数时，具有最大代数免役的函数情况比较复杂，近两年来也有一部分人 对其进行研究，但种类繁多，也不能面面俱到。这一章的主要工作是在构造2 的 基础上，对构造2 中向量值适当的改变一个分量和两个分量得到了一些结论。 张红艳对称布尔函数代数免役的研究 1 布尔函数 1 1 布尔函数的定义及性质 我们先来介绍一下布尔函数的定义 定义1 设函数，：f ”( 2 ) 斗，( 2 ) ，( 而，x ) - o f ( x q ，) ，其中西f ( 2 ) = o ，b ，称 ，为玎元布尔函数，b n x 】为所有万元布尔函数的集合 对于任意一个工= “，) p ( 2 ) ，通过一一映射：x - - ) x 1 2 - 4 ，都可以与 j i 【0 ，2 “】区间上的整数一一对应不管是f ”( 2 ) 上的向量还是【o ，2 “】区间上的整数， 在文章中所指的意义一样，只是不同时候文章对它的需要不一样而已但为了区分 起见，我们下面记；= “，) e ( 2 ) ，记z 为与；对应得在【o ，2 ”1 】区间的整数 任何一个，b n f x ，都可表示为在最k 9o 9 x j ( x ；一五，一) 上的多项式， 熊，矗) - ( 。摹( 2 ) 而( ”) 砰矸， 1 其中厅( q ，靠) = 厂“，o * o9 ) ，v _ = ( q ，a ) ef ”( 2 ) 巧4 这里琏口表示对所有1 f 刀，而q “三”读作“先于” 称( 1 ) 式这样的表示为，的代数标准形式( a n f ) 这种表示形式是唯一存在的 其中在右式多项式的各非零项中，交元个数的最大值称为函数的代数次数，记为 d e g ( 力 注：这里的加法都是在m o d ( 2 ) 的情况下，所以有时就用。表示 设函数厂为一元布尔函数，定义勺= ( ，( o ) ，厂( 1 ) 9 - * - 9 f ( 2 ”一1 ) ) ，其码长为2 ”，称吩 为厂的真值表( 7 t ) 扬州大学硕士学位论文 例1 布尔函数，= 五+ x n x 2 x 3 ， d e g = 3 ，a f = ( o ，o ，0 ，0 , 1 , 1 ，1 ，o ) 计算如下表 x x = “，毛，屯) 厂“，而，而) o ( 0 ，0 ，0 ) o 1 ( 0 ，0 ，1 ) 0 2 ( 0 ，l ，o ) 0 3 ( o ，1 ，1 ) 0 4 ( 1 ，0 ，0 ) 1 5 ( 1 ，0 ，1 ) 1 6 ( 1 ，1 ，0 ) 1 7 ( 1 ，1 ，1 ) 0 6 接下来回顾一下对于任意一个向量，其支集的概念：任意工= ( 西，) f ”( 2 ) ， 定义并的支集为s u p p ( x ) = i l x , o ，瓴，) f 4 ( 2 ) ，1 f 刀 定义x 的重量为w t ( x ) ： s u p p ( x ) i 显然有0 州( z ) 甩 那么对于一个布尔函数，它的支集定义如下： 定义2 设，b n x ，定义的支集s u p p ( f ) = “，) f “( 2 ) l f ( x a ，) = 1 ) 定义，的重量w t ( f ) 刊s u p p ( f ) 1 显然0 w t ( d 2 ” 下面看布尔函数的一种特殊情况 定义3 设f e o n x 】，若在真值表口，中1 的个数和0 的个数相等，则称布尔函数厂是 平衡的( b a l a n c e d ) 1 2 对称布尔函数的定义及性质 由1 1 中布尔函数的定义知，就算布尔函数的变元一确定了，其种类也千态万 象，这给我们的研究带来了很大的困难，但对于一些特殊的布尔函数，我们就可以进 行研究，并得到一些好性质下面就具体的介绍一下对称布尔函数 定义4 设厂酬工】，如果有，瓴，毛) = 厂( ( 。) ，( 町) ，其中f 为 1 ，啦上的置 张红艳对称布尔函数代数免役的研究 7 换，则称为竹元对称的布尔函数 例2 设b n x ，厂“，而，而) = 五+ 而+ 毛+ x _ l x 2 x 3 ，则显然厂为3 元对称布尔函数 在介绍性质之前我们先来看一个例子 例3 ，如例2 定义， w t ( o ，0 ，o ) = 0 ，f ( o , o ，o ) = 0 w t ( 1 ，0 ，o ) = w t ( o ，1 ，0 ) = w t ( o ，0 ，1 ) = 1 ，则有f ( 1 ，0 , 0 ) = f ( o ，l ，o ) = f ( o ，0 ，1 ) = 1 w t ( 1 ，l ，o ) = w t ( 1 ，0 ，1 ) = w t ( o ，1 ，1 ) = 2 ，则有f ( 1 ，1 ，o ) = f ( 1 ，0 ，1 ) = f ( o ，l ，1 ) = 0 w t ( 1 ，l ，1 ，) = 3 ，f ( 1 ，1 ，1 ) = 0 由于对称布尔函数的对称性，各变元在函数中所起的作用是一样的，则可得下 面性质 性质1 若厂为押元对称的布尔函数，则重量相同的向量具有相同的函数值 因为在f ”( 2 ) 中，向量x 有0 w t ( x ) s ，l ，根据性质1 ，则可把真值表( t t ) 简化 为长为n + l 的向量吁= ( v ，( o ) ，v f ( 1 ) ，v ，( 刀) ) ，其中v ，( d 表示重量为i 的函数值， o i n ，此向量_ 称为对称函数，的向量值( w ) 有时也称其为简化的向量值 显然( d f ( 2 ) 下面记刃为刀个变量的齐次对称布尔函数，它包含了所有的f 次的项，有时在不 引起混淆的情况下，简记为吼 如 q = 五+ 屯+ + ， d l = 鼍屯+ 五为+ + 而+ 屯毛+ + 毛- 1 矗， 吒2 x l x 2 扬州大学硕士学位论文 3 特别a o = 1 由此也可以简化函数，的代数标准形式( a n f ) ，对于任意的对称布尔函数， 它都可以表示为以仉( o f s 以) 为基的线性组合 f ( 7 0 = 盆nt ( 。q ，其中力( d = 雹v ，( t ) ，o f 捍， ( 2 ) 其中向量一= ( 0 ( o ) 一( 1 ) ，以( ，坊称为简化的刎v f 向量( s a n f v e c t o r ) ( 可 参【9 】性质2 ) 注：| 型即指西 如右表2 - 3 ，1 - 3 ，但l 蜇不成立 七 七 0 ( 0 ，0 ，0 ) 1 ( 0 ，0 ，1 ) 2 ( 0 ，1 ，0 ) 3 ( o ，1 ，1 ) 例4 厂如例2 定义，v ，= ( v ，( o ) v ( 1 ) ，v i ( 2 ) ，v ，( 3 ) ) 2 ( o 100 ) ， 则乃( o ) = v ，( o ) = o ；t ( 1 ) = v ，( o ) o v ，( 1 ) = 1 ；乃( 2 ) = v ( o ) e v f ( 2 ) 2 0 ； 0 ( 3 ) = v ，( o ) o ( 1 ) o v ，( 2 ) = 1 故乃= ( o ，i ，0 ，1 ) 另一方面，f ( x a ，x 2 ，而) = 五+ 恐+ 而+ x l x 2 x 3 = q o 码，得力( 1 ) = ( 3 ) = 1 乃( 0 ) = 一( 2 ) = o ，与上面计算的结果是一致的另外可以观察到，v ，。兽乃( 七) 性质2 1 9 设厂为万元对称布尔函数，则吩与力之间有下列关系： v ，( 力。雹( 七) ，力( 力2 雹v ，( 七) 由定义3 及性质1 可得下面引理 引理1 设厂为刀元对称的布尔函数，则厂是平衡的在吩中0 与l 的个数相等，都 为孚 说明：由引理1 知在v ，中o 与1 的个数相等，v ，的长度疗+ 1 为偶数，则撑为奇数 下面介绍一种特殊的对称布尔函数 张红艳对称布尔函数代数免役的研究 9 定义5 1 9 设行为奇数，厂为力元对称布尔函数，如果v ，( o = v ，一0 ( 9 1 ，( o f 叻， 则称，为平凡的平衡函数( r , h , i a a yb a l a n c e df u n c t i o n ) 显然，是平凡的平衡函数j 厂是平衡的 1 3 齐次对称布尔函数的性质 由( 2 ) 式，任意一个对称布尔函数都可以表示为齐次对称布尔函数的线性组 合，下面就具体的介绍一下齐次对称布尔函数的性质定理 性质3 设吒，吒分别表示次数为a 与6 的齐次对称布尔函数，则吒仍是齐次对称 布尔函数。且次数为二v 否 其中a v b = ( t 1 ，乞，) ，= 1 当q = 1 或岛= 1 ，否则，= o i = 1 ，2 ，r t 证明令厂= 呱自【1 0 】h 雄理，v l 姚刀 v ，( 渊铮盛嘶v 硒， 由珀q 任意性，故 = k 例5q 旺= o - f i o l 瓯= 乃；q 旺= 吒；q 瓯= 吒； c r 2 呸= 吒；吒瓯= 乃；c r 2 瓯= 气； 吒喝= 巳；巳眈= q ； o p = o 矗 定理1 设二= ( q ，吼) f 4 ( 2 ) ，则在f ( 2 ) 上的齐次对称布尔函数吒可分解因式为 o a2 气吒o 吒妒 证明q 2 “= ( q ，o ，o ) ； a 2 2 , , - 2 = ( o ，d 2 ，o ) ； 扬州大学硕士学位论文 a , 2 0 = ( o ，o ，q ) 由性质3 结论显然成立 例6 取疗= 3 ， c r 7 = c r 4 畋吼； a r 6 = 吼眈；乃= 吒旺； 吼= q ；吧= c r 2 旺； c r 2 2c r 2 ；q2 q ； 口 ( q ，a 2 ，吩) d ( q ，a z ，a d o ( 0 ，0 ，0 ) 4 ( 1 ，0 ，0 ) 1 ( 0 。0 ，1 ) 5 ( 1 ，0 ，1 ) 2 ( 0 ，1 ，0 ) 6 ( 1 ，1 ，0 ) 3 ( 0 ，1 ，1 ) 7 ( 1 ，1 ，1 ) 推论1 o a ，分别表示次数为a 与b 的齐次对称布尔函数，则吒气为t 次齐次对 称布尔函数吒2 气吒一凸吒毋， 其中= 凯翥咐乒啦，棚胁= 耖。 推论1 设吒，吒，吼分别表示次数为口，b , c 的齐次对称布尔函数，则吒吒为f 次齐 次对称布尔函数吒吒= 气一吒：一d 眈一， 姚= g 凯2 霜一序啦，棚胁= 妒 推论l 。 设巳，q 分别表示次数为岛6 ，l 的齐次对称布尔函数，则吒q 为f 次齐次对称布尔函数吒q = 气：“吒d 。吱2 ， 撕= g 凯呐藉仁咐扣l 2 ，棚且f = 喜 张红艳 对称布尔函数代数免役的研究 2 布尔函数的代数免疫 2 1 代数免疫的基本概念及性质 这一节我们将介绍代数免役的知识。先给出几个定义 定义6 设f ，g b n x 】，g o ，如果詹= 0 ，则称g 是，的零化子，记作 a n n ( f ) = 塘b n x l 启= o ，g o 定义7 2 】布尔函数，的代数免疫( a ) ：指，与f + l 零化子的最低次数，即： a t ( f ) = m i n d i d = d e g ( g ) ，g a n n ( 力u a n n ( f + 1 ) 定义8 设变换r ：；斗一x a o 石，其中a 是月竹阶非退化矩阵，五f ”( 2 ) ，则称r 为仿射 变换从而称厂( 妇o - ) 与，( - ) 是仿射等价的 代数免役的定义直接与零化子联系，下面就从零化子的性质出发，得到代数免 役的一些性质推论 性质4 设_ ，( _ ) 是一元布尔函数，g ( - ) 为，( _ ) 的零化子，则g ( - 4 0 i ) y a f ( 一x 4 0 - ) 的 零化子，其中a 是刀刀阶非退化矩阵，石f 。( 2 ) 证明由于g ( - ) 为，( - ) 的零化子，则，( - ) g ( - ) = o ，i 故f ( 一x a o b ) g ( 一x a o b ) = 0 口 由性质4 零化子之间的关系，可得代数免疫之间的关系： 推论2 设窃是一元布尔函数，则a i ( f ( 一x a ( 3 劲= 小( 厂( - ) ) ，其中a 是刀x 疗阶非退 化矩阵，5 f ”( 2 ) 性质5 设，( - ) 是一元布尔函数，g ( - ) 为厂( ；) 的零化子，则g ( 一x x c ；0 1 ) 为 h ，( _ ) o ：；的零化子，其中：f 4 ( 2 ) ( 注：；= ) 扬州大学硕士学位论文 证明i 由t - g ( x ) 茭t j f ( x ) 的零化子，贝l j f ( 一x ) g ( 一x ) = o ，显然；一x ( 一e ；0 1 ) = ；o ；一x = o 1 2 则u ( _ ) o ：一x ) g ( 一x x e ；0 1 ) = ，( _ ) g ( _ ) ( - x f f t l ) o c 一x ( 一c ；0 1 ) g ( - ) = 0 口 t t f i 仑3 设，( _ ) 是以元布尔函数，则彳，( ，( - ) o ；为与小( ，( 动最大相差1 ，其中 c e f ”( 2 ) 引理2 1 3 设，b , i x ，则有小( 力s 胡 显然，由定义7 和引理2 有o 6 ，6 = 2 2 + 2 , 贝t j a 6 = 吩= 吼c r 2 ，j = 3 ，i = 2 故_ ，一i = 1 ，小( c r 6 ) 2 ，又由a 的定义知m ( a d 1 ，又找不到c r 6 一次的零化子， 所以朋( c r 6 ) = 2 ，c r 2 0 1 为其二次零化子 口 由例7 ，例8 及引理3 我们得到下面的推论 推论4 设吒为在( 2 ) i - _ l 鬟j 齐次对称布尔函数， 当口为奇数时，且o a b ，则a ( 吒) = 1 ，q ( 3 1 为其一次零化予； 当a = 4 k + 2 时，且o 口 栉，则刖( 吒) = 2 ，c r 2 0 l 为其二次零化子 证明：令a = 2 k + 1 ，由定理2 知，一f = o ，小( 吒) 1 ，又由a 的定义知御( 吒) 1 ， 所以a i ( a o ) = ，o - t o l 为其一次零化子 令口= 4 k + 2 ，由定理2 知_ ，一f = 1 ，御( 吒) 2 ，又由4 的定义知御( 吒) 1 ，又找不 到吒一次的零化子，所以射( 吒) = 2 ，c r 2 0 1 为其二次零化子 口 引理3 在p ( 2 ) 上的齐次对称布尔函数以。其中2 一刀 2 7 1 ， 则c 7 加= 吁( 巳( 2 h - 1 ) 0 l x c 7 0 2 h 一2 ) e 1 ) ( 巳h 1 e 1 ) 证明当o s 七 2 ，_ 1 时，( 七) = 0 ，此时等式显然成立 当2 卜1 七栉时，对所有一一2 7 。+ 1 c 2 7 。1 1 ，有k ( 七) = o 此时等式显然成立口 扬州大学硕士学位论文 例9 取_ ，= 3 ，则4 n 2 ，4 = 刀一4 ，贝御( 吒) 5 ， 证明疗= 2 。+ 2 ，a l l n 一2 = 2 i , 由引理3 得勺= 巳( 吒o l x q e l ) ( 勺一1 0 1 ) ， 因为吒( c r 3 0 1 ) = 0 故吗= o ，即玛为的零化子，所以御( ) 3 ，即a t ( o o ) 3 ，证明类似 口 由此可以看出吒要达到最大免疫，这行可取值的集合也很小 引理5 当珂= 2 ，2 。一1 , 2 一2 时，唯一具有最大代数免疫的齐次对称布尔函数为o ； 当挖为其他值时，不存在这样具有最大代数免疫的齐次对称布尔函数 证明由定n 2 与引理4 得：以元齐次对称函数盯，。在2 h 拧2 7 时是唯一具有最大 代数免役的函数因为其它齐次对称函数都可分解为次数更小的齐次对称函数的乘 积，但由引理3 ，当月= 2 7 3 有= 魄3 ：0 1 ) ( 嘞。e 1 ) 因2 ( 2 7 2 h 一2 ) 2 - 3 ，所以。如零化子次数严格小于f 纠， 同理，2 + l 栉2 - 3 时，d 如零化子次数严格小于纠 口 张红艳对称布尔函数代数免役的研究 3 在仿射变换下的对称布尔函数 下面我们来观察在仿射变换下，是否能将一个对称函数映成一个新的对称函数 呢? 主要分两部分： 扎工_ x e 饪) b ，其中b f 4 ( 2 ) t ：j 专州，其中彳为 x n 阶非退化矩阵 看看它们是否在仿射变换下保持对称性? 1 特殊记法 先对下文常出现的一些符号进行说明写下，规定： l = ( 1 ，1 ，1 ) ，0 1 = ( 0 ，l ，0 ，1 ，0 ，1 ) ，0 = ( 0 ，o ，o ) ，e 为n x n 阶单位阵 刁：广鬲一广 e 。为e 的任意行列重排。即每行每列都只出现一个1 的肛行阶的矩阵 f = 0l l0 ： l1 ll f “为每列和每列中都只出现一个0 的n x 刀阶的矩阵 e j = ( o ，0l ，o ，o ) ，其中岛的向量长度为挖，只有第i 个位置是l ，其余位置都为0 工。= ( 五，而，) 7 = 瓴，屯，置) ， 2 彳取单位阵e 命题1 设r ：石一姬o l ，“，x 2 ，矗) _ 瓴0 1 ，x 2 0 1 ，0 1 ) ，则f ( x ) 为拧元对 称布尔函数厂( 魍0 1 ) 为栉元对称布尔函数，且k 殛而= ( - ) o 1 ) f = l ，2 ，刀 ；i o 1 1 ；o l 扬州大学硕士学位论文竖 证明显然r 是仿射变换，由于e 是可逆矩阵，因此r 显然是同构变换 根据向量值( n 7 ) 的定义，v ，= ( 吁( o ) ，v ，( 1 ) ，v ，( 砌，v ，( o 表示重量为f 的函数值 而丁的结构是把向量中分量为i 的变为0 ，即把重量为i 的向量变为一一i 的向量，故 v ，国面( 0 2 v ，( - ) 0 一d ，i = l ，2 ，一- 贝l j f ( x ) 为栉元对称布尔函数营f ( x e 0 1 ) 为甩元对称布尔函数 口 命题2 设r ：工专旭n ( 而，而，) 斗( ，气) ，其中( ，毛，) 为( 1 ，2 ，帕 的一个重新排列，则f ( x ) 为行元对称布尔函数，( 加 为行元对称布尔函数，且 v ，( 动，( f ) 2 1 0 ( ) ( 力f = l ，2 ，玎 证明显然，为同构 由r 变换的结构看，它只是把一个向量变成为它的倒序向量，向量的重量不便，所以 ，( d 2 ( 0 ，i 2 l ，2 ，刀 所以厂o ) 为疗元对称布尔函数八翘勺为i 1 元对称布尔函数 口 命题3 设r ：善斗橱峋1 ，“，屯，) 专( + l ，屯+ 1 ，气+ 1 ) ，其中( ，岛，) 为 ( 1 ，2 ，功的一个重新排列，贝l j f ( x ) 为刀元对称布尔函数，( 动一o ) 为刀元对称布 尔函数，1 j _ ，国面( d = v ，( - ) o 一0 上面3 种情况中取6 1 ，0 ，下面看看6 f “( 2 ) 、 1 ，0 ) 的情况，先举个例子 例l o 当i 1 = 4 k 时， 设t ：x 寸茹o o l ，“，而，轴，) 斗瓴，而0 l ，铀，矗0 1 ) ， 若厂 ) 为万元对称布尔函数，则无法得到厂 0 0 1 ) 为万元对称布尔函数 证明取x = ( 1 ，0 , 1 ，0 ，l ，o ) ，j = ( o ，l ，0 , 1 ，o 1 ) ，显然w t ( x ) = w t ( x = 2 k 而r ( 力= ( 1 ，1 ，1 ) = 1 ，r ( x ) = ( o ，0 ，0 ) = o ，有w t ( t ( x ) ) = 4 k = 以，w t ( t ( x g ) = 0 ， 则无法使的具有相同重量的向量在r 下的像的重量也相等 张红艳对称布尔函数代数免役的研究 1 7 下面看一个例子，由于，( - ) 都可以表示为qo = 1 ，2 ，力的线性组合，所以只 要研究q 在r 下是否还是对称函数取，( - ) = q = 毛+ x 2 + + g l l j f ( t ( x ) ) ：q + 羔恐。，显然它已不是一个对称函数了 由上面的3 个命题可得下面定理 口 定理3 设，：；_ 殛一。石，( _ ) 为厅元对称布尔函数，贝1 f ( x e 。o _ ) 为行元对称布尔 一 = 一 函数的充要条件b l ，0 证明充分性显然。 必要性：利用反证法，任意取b f ”( 2 ) 、 1 ，o ) ， 则存在x ，工f “( 2 ) ，且w t ( x ) = w t ( x 9 ，使w t ( x e o b ) w t ( x 匹眄， 所以，( x e 恃6 ) 就不是对称布尔函数，与条件矛盾故6 1 ，0 1 3a 取f 定理4 设r ：；一妇 ( 而，毛”，) - - ( x 2 + 为+ + ，为+ 而+ + ，而+ 而+ + 铀) 其中行为偶数，则雨为，l 元对称布尔函数营( _ f ) 为刀元对称布尔函数， 注若力为奇数，丁( _ ) = 一0 ，r ( - ) = 一0 ，则r 不是单射 对定理4 中的f 换成f 。命题仍然成立 证明记们q ) = f ，当f 为偶数时，v x f “( 2 ) ，设x = “，而，矗) ， x f = 也+ 毛+ + 毛，而+ 毛+ + 矗，毛+ 恐+ + 吒一1 ) = ( t - x i ，t 一而，t - x ) = “，而，) ，可以看出w t ( x f ) = f 当f 为奇数时，驴= ( t - x 1 ，r 一恐，t - x ) = ( 1 + 五，l + x 2 ，1 + ) 可以看出w t ( x f ) = n t 因此r 为同构变换故结论成立 口 口 扬州大学硕士学位论文 4 具有最大免疫的对称布尔函数 下面我们构造具有最大免疫的几类对称布尔函数 由于御( 力f 胡，当等式成立对，就称布尔函数，具有最大免疫为f 胡下面分别从 撑为奇数和偶数的情况来探讨 t i4 1 当甩为奇数时具有最大免疫的对称布尔函数 构造1 【1 】设厂是厩对称布尔函数，当行是奇数时，其向量值为调= g 墨竺， 则( 力= 譬 证明v ，2 l ! ：! ：! ：! ! ，其中。和l 的个数都等于孚，且第一个出现1 是f = 孚， y f e - 2 l ! ：! ：! ：虫，其中。和1 的个数都等于孚， 由零化子的知识知，在1 ，阳，的分量为1 的地方，0 1 的零化予g 的向量值分量必须为 o ，所以厂0 1 的零化子的次数大于等于孚， 由命题1 得，与，o l 仿射等价， 故由性质4 ，对于，与 1 固定次数的零化子的个数相同 故，的零化子的次数大于等于孚， 由引理2 ，舡学所以彳，= 学 口 构造l ，设厂是甩元对称布尔函数，当n 是奇数时，其向量值为删= 器娑竺， 则a = 孚 证明仿照构造1 ，换成f l 即可 口 张红艳对称布尔函数代数免役的研究 引理6 对任意一个整数i ，至少存在一个非零的2 i + 1 元的对称布尔函数g ，满足： ( i ) d e g ( g ) i ； ( i i ) ( o ) = o = o ，v i + i ， 2 i 证明由( i ) 知：以u ) = o ，i + l i 2 i + 1 ( 3 ) 令g = 以( o ) o 以( 1 ) q 2 o o 以q 2 k ( o ) ，v g ( i + 1 ) , v g ( i + 2 ) ，v g ( f + 力均可表示为以( o ) ，以( 1 ) ，以( o 的线性组合 由( i i ) 得一个含i + 1 个变元，i + 1 个方程的方程组： v g ( o ) 2 思以( 七) = o k ( f + 1 ) 2 t 宝；以( 七) = ( 4 ) ( 2 0 。恩，以( 七) 2 0 若( 4 ) 有非零解，可得2 i + 1 元的布尔函数g 满足( i ) ，( i i ) 令i = 2 + j ，其中t 0 ，0 j 2 ， 由引理1 得k ( 2 “) 2 。翕以( 七) = 2 s ( o ) 。2 9 ( 2 “) 2 以( o ) 2 k ( o ) ( 。以( 2 “1 ) = o ) ( 5 ) 因为f + l 2 “ 2 i ，所以( 4 ) 式可略去方程心( 2 “1 ) = o 得到由f 个方程组成，含f + 1 个变元的方程组，故有非零解 口 引理7 1 1 1 】设厂为栉元对称布尔函数，令栉= 2 k + l ，且，为平凡的平衡函数， 则朋讲营螂= 埝：襄：，其帐，( 2 ) 证明由构造1 和构造1 7 ”仁”显然 下面证”j ”，通过逆否命题来证 假设帅不具有后面结 句：帅= 芝其中御( 2 ) ) 扬州大学硕士学位论文 记f 为在满足v ，( 七一o v ，( 七) 的最小的整数，( o f 的， 由i 的定义及，为平凡的平衡函数知： v ，( 后一f + 1 ) = l o v ：( k o = v ，( 七+ f + 1 ) ( 6 ) 由上面引理6 ，则可构造出关于变量置，x 2 ，而。的非零对称布尔函数g ，其中g 的 最大次数为f ，它的支集由在f 2 “( 2 ) 中重量为l ，2 ，i 和2 i + i 的向量所组成 令h c x ：“2 ，毛) = ( 屯j + 2 0 而，+ 3 ) ( 稚l o ) 显然只有在，柚“1 ( 2 ) 中，重量为( 力一2 i 一1 ) 2 = 七一珀q 向量；，才有 ( 为= 1 h 的次数 为( n - 2 i 一1 ) 2 = k - i ， 因此，h 个变元的布尔函数g 。 的支集包含于在，”( 2 ) 中重量为k - i + l ，j j 和 k + i + l 的向量的集合中 由( 6 ) 式与i 的定义知： ，( 七一f + 1 ) = = v ，( 七) = v y ( k + i + 1 ) = 0 或v ，( | j 一f + 1 ) 一一v ，( 七) = v ，( 七+ f + 1 ) = 1 对于前面这个等式，g 。厅为，的零化子， 7 而对后面的这个等式，g 。 为厂0 l 的零化子 这样g o h 的代数次数最大为k - i + i = k 。与a t ( y ) = 七+ l 矛盾 口 4 2 当n 为偶数时具有最大免疫的对称布尔函数 构造2 【l 】设厂是行元对称布尔函数，当甩是偶数时，其向量值为v ，( o = g ；i ；i ：， 贝i j a t ( f ) = 号 证明当n 为偶数时， 张红艳对称布尔函数代数免役的研究 一方面，吁2 q ：骘：! ：1 2 ，其中。的个数为号，l 的个数为号+ 1 n + l 1 ，。- 2 ! ：! ：! ：! ! ：虫，其中。的个数为号+ l ，1 的个数为号 m - i 所以0 1 的零化子的次数大于等于暑， 2 1 另一方面，令h 为命题1 中与，仿射等价的对称布尔函数， 即有。g ：! ：! ：! ：竺，其中。的个数为号，1 的个数为苎+ 1 故厅的零化子的次数大于等于量+ 1 ，从而，的零化子的次数大于等于暑+ 1 由代数免疫的定义及引理2 ，知a = 暑 口 构造2 设厂是万元对称布尔函数，当打是偶数时，其向量值为 v f ( o = ：；i ；：，贝u 4 ，c 力2 暑 设，是栉元对称布尔函数，当 是偶数时，其向量值为 蚺= o 嚣细盼号 设厂是珂元对称布尔函数，当，l 是偶数时，其向量值为