（基础数学专业论文）某些密码函数的研究.pdf

摘要 v 7 1 6425 论文研究厂两个方面的内容：相关免疫函数和b e n t 函数。论文 从一个新角度( n 个元素的满足某种条件的分组) 对两类函数做了研 究 论文分为四章：布尔函数的基础知识；相关免疫函数；b e n t 函数； 一种用b e n t 函数构造相关免疫函数的方法 第一章是预备知识，介绍了密码学中的组合函数的一些基本概 念，详细介绍了组合函数的w a l s h 谱表示及其基本性质。这是本文通 篇都会削到的研究方法的基础。 论文第二章论述相关免疫函数。简要的介绍了相关免疫函数的研 究背景、当前对相关免疫函数的研究状况。然后作者给出了相关免疫 函数的一种新的描述，把相关免疫函数的构成归结为满足一定要求的 一些集合的选择( 这些集合必须都是n 个元素构成的集合的子集) 。 然后从这种描述方法入手讨论r 相关免疫函数的计数问题，将相关免 疫函数的计数问题归结为n 个元素的满足一定要求的分组方法的数 目，然后从这种描述方法入手计算了重量1 i 大于六的相关免疫函数的 个数。 论文第三章论述b e n t 函数。介绍了b e n t 函数的研究背景及b e n t 函数的两个主要性质( 差分分布均匀性和最大非线性性) 后，作者给 出了一种对b e n t 函数的新的描述，将b e n t 函数的构成问题归结为满 足一定要求的一些集合的选择( 这些集合必须都是n 个元素构成的集 合的子集) 。最后从这种描述入手给出了b e n t 函数与著集的关系的一 种证明 论文第四章应用b e n t 函数的差分分布均匀性，构造了一个正交 矩阵，从而给出了一种构造相关免疫函数的方法。 关键词 相关免疫，非线性性，差集 a b s t r a c t t h i sp a p e rd e a l sw i t ht w ok i n d so f p r o b l e m s ：c o r r e l a t i o n 。i m m u n e f u n c t i o na n db e n t f u n c t i o n an e wd e s c r i p t i o n o ft h et w ok i n d so f c r y p t o g r a p h i c f u n c t i o n si s p r e s e n t e d i n t h i s p a p e r w h i c ht a k et h e i r c o n s t r u c t i o na sac o m b i n e d d e s i g n t h e p a p e r c o n t a i n so ff o u r p a r t s t h ef i r s t p a r tp r e s e n t s t h eb a s i c k n o w l e d g e f o rt h er e s e a r c ho f c r y p t o g r a p h i c f u n c t i o n sw h e r ew a l s ht r a n s f o r m a t i o ni s i n t r o d u c e di n d e t a i l i nt h es e c o n dp a r tc o r r e l a t i o n i m m u n ef u n c t i o ni s d i s c u s s e d a f t e r i n t r o d u c i n gt h eb a c k g r o u n db r i e f l ya n dp r e s e n t i n gt h em a i nr e s u l t so ft h e r e s e a r c ho fc o r r e l a t i o n 。i m m u n ef u n c t i o n ，t h e p a p e rg i v e an e w d e s c r i p t i o n o fc o r r e l a t i o n i m m u n ef u n c t i o nw h i c h t a k e st h ec o n s t r u c t i o no f c o r r e l a t i o n _ i m m u n ef u n c t i o na sac e r t a i n g r o u p i n gd e s i g n o fn e l e m e n t s t h e nt h ec o u n to fc o r r e l a t i o n i m m u n ef u n c t i o n si s d i s c u s s e d t h e p a p e rp r e s e n t t h ec o u n to fc o r r e l a t i o n i m m u n ef u n c t i o n sw h o s e h a m m i n gw e i g h t s a r er e s p e c t i v e l y4a n d6 i nt h et h i r dp a r tb e n t f u n c t i o ni sd i s c u s s e d a f t e r b r i e f l yi n t r o d u c i n g t h eb a c k g r o u n do fb e n t - f u n c t i o n r e s e a r c ha n d p r e s e n t i n gi t st w o m a i n p r o p e r t i e s ，t h ep a p e rg i v ean e wd e s c r i p t i o no fb e n t f u n c t i o nw h i c ht a k e s t h ec o n s t r u c t i o no f b e n t f u n c t i o na sac e r t a i n g r o u p i n gd e s i g n o fne l e m e n t s a n dt h e n ，u s i n gt h i s d e s c r i p t i o n t h e p a p e rp r o b e 3 i n t ot h er e l a t i o nb e t w e e no fb e n t f u n c t i o na n dd i f f e f e n c es e t i nt h ef o r t h p a r t am e t h o di s p r e s e n t e d w h e r eo n ep r o p e r t yo f b e n t f u n c t i o ni su s e dt oc o n s t r u c tc o r r e l a t i o n i m m u n ef u n c t i o n so ft w o o r d e r k e y w o r d sc o r r e l a t i o n i m m u n e ，n o n l i n e a r , d i f f e r e n c es e t 4 刖罱 密码函数在现代密码学中有广泛的应用。设计分组密码s p n 网络( 代换置 换网络) 的s 盒时需要考虑高度非线性性的函数。具有完美的非线性性的函数称 为b e n t 函数。为了抵抗针对流密码的相关分析，要求使用相关免疫函数。这两 种函数构成了本文讨论的主题。 作者最初试图寻找两种函数的相通之处，从中找出些深层的联系。从函数 的差分分布均匀性入手，得到一些序列，它们相互之间逐位作模二加之后重量平 衡，由此构造出了二阶相关免疫函数，这构成了本文的第四章。 作者考虑2 ”元对称性变换群对长为2 ”的序列的变换作用，试图从中找出一 个相关免疫函数的不变子群来，以考察满足什么样的对称性的函数才是具有相关 免疫性的。这一目标还没能达到，一些初步的结果构成了论文的第二章。 作者从第二章的角度来考虑b e n t 函数，得到了本文的第三章。 然而实际上，虽然可以从同一个角度来描述来考虑相关免疫函数和b e n t 函 数，这两个问题依旧是不相关的。至于两类函数之间更深层的联系，还有待深入 的研究。本文仅是作者得出的一些初步结果的总结。 6 第一章布尔函数的基本概念 布尔函数是定义域为二元域e 上的h 维空间”、取值于二元域疋的函数。 现代密码学中广泛应用这种函数。本节先对柿尔函数做一个简要地介绍，作为进 一步研究的预备知识。 一、布尔函数的几种表示法 布尔函数也叫组合函数，可以用下列几种方法来表示： 1 函数表达式 ，：e ”斗，2 是二元域吒上的n 维空间e ”上的函数，取值于二元域e 任意这 样的函数都可以用一个n 元多项式来表示【1 2 函数真值表 设厂：”斗e ，定义c ( 厂) = p 五”i f ( c ) = 1 ) ，为函数i 厂的支撑点集取e ”中 在函数f 作用下值为l 的所有向量排成的矩阵，称为函数，的特征矩阵或，的真 值表，仍记作c ( ，) ，或简记为c 记( ) = j c ( ) j 称为函数，的重量 3 小项表示 在二元域只中定义指数运算： 矿= 1 当且仅当口= z ，其中z ，口e 对应真值表c 的每一行，有函数，的小项表示法： ，( x ) = = z i q x ：“x 。“，其中c = ( c l ，c ：，。) ，x = ( 五，x ：，。) c e f 、 ( c 1 ，r 2 c 。冲 4w a l s h 谱表示 定义函数绒：f 2 ”， 见( x ) = ( 一1 ) ”“”“， 其中x = ( x l ，x 2 ，x 。) ，w = ( w 。，w 2 ，) 都是e ”中的向量 q w f 2 ”，q ( o ) = l ，瓯 + y ) = 瓯( x ) 姨( y ) 吼是群同态， 如果z = ( 工1 ，x 2 ，x 。) ，w = ( w i ，w 2 ，) f 2 ，记w = w i 五+ w 2 x 2 + + w n x n 定义1 1 称s ( w ) = 彤，( x ) 绒( x ) = 。( x ) ( 一1 ) “为函数厂关于 j e ，e 十， w 的第一类w a l s h 谱，集合 ( w w ” 称为函数厂的第一类w a l s h 谱集，称s ， 为函数的第一类w a l s h 变换 称s ( ，) = 。( 一1 ) 九“q 。( x ) = 。( 一1 ) m 为函数f 关于w 的第二 j ，1 类w a l s h 谱，相应地，集合 s ，) ( w ) 1 w 疋”) 称为函数，的第二类w a l s h 谱集，s 门称 作函数的第二类w a l s h 变换 两种w a l s h 变换都存在逆变换： 厂( x ) = s ，( w ) q 。( 工) w f 2 ” = 一s ( ，) ( w ) q 。( x ) 由此知一旦函数的任意一种w a l s h 谱集确定，函数也 可以随之确定故布尔函数可以用它的w a l s h 谱集来表示 二、 布尔函数的w a i s h 谱的一些性质m 1 1 两类w a l s h 谱之间的关系 根据定义直接验证可以得到 s ( ，】( w ) = 一2 s ，( w ) 当w 0 ， 而对于w = 0 有& 小o ) = 2 墨( o ) 2 p l a n c h e r a l 公式 譬m 2 必n w ) = s l ( o ) ， 其中w ( f ) y 揪f 的重量 3 能量守恒公式 s ( 小w ) 2 = 1 w e ” 4 卷积公式 & 门( w ) s 门( w + n ) = o ，其中：x 0 5 循环w a l s h 反变换的存在性 如果函数s ( w ) 满足2 ”s ( w ) 是整数，并满足能量守恒和卷积公式，则s ( w ) 的循 环反变换是一个布尔函数 有些资料中对w a l s h 谱的定义可能与本文不同，他们定义 s ，( w ) = f ( x ) q 。( x ) = ，( x ) ( 一1 ) “为函数厂关于w 的第一类w a l s h 谱，定义 j “t e “ s 1 = ( 一1 ) m q 。( x ) = ( 一1 ) m 卜“为函数，关于w 的第二类w a l s h 谱。相应 x e f 2 ”j b ” 的反变换也作了变化。这样定义的w a l s h 谱就是整数函数。但本质上这两种定义 并没有差别。可以很容易的推得，对于这种不同定义也有相应地能量守恒公式和 卷积公式和其他的与w a l s h 谱相关的性质 第二章相关免疫函数 相关免疫函数的概念是t s i e g e n t h a l e r 于1 9 8 4 年针对对流密码的“分而治之” 攻击提出的 2 】之后人们对之作了大量的研究，研究的中心问题主要集中在这类 函数的构造和计数以及这种函数的性质我国著名密码学家肖国镇曾在这个方 面得出出色的研究结果【3 1 他发现了这类函数的一个重要性质：函数的非线性次 数与相关免疫阶之间互相矛盾，二者互为消长此后人们提出了广义相关免疫函 数【”的概念，这一概念克服了函数的非线性次数与相关免疫阶之间的矛盾，牺牲 了一定的相关免疫性，但突破了对非线性次数的限制后来人们发现即使函数具 有相关免疫性也很难抵挡相关攻击1 3 l 。但这种函数的性质依旧引起人们的注意 曾经有文献从置换多项式的角度来研究相关免疫函数1 9 1 ，试图对此类函数作出数 学上的彻底的解释在文献【lo l 中也提到了这种思想但从目前取得的结果来看， 研究主要是从三个角度进行【7 】的：函数重量分布的特征，函数的特征矩阵，函数的 w a l s h 谱对它的研究已经从最初的二元域上的函数推广到一般素数阶域上的函 数，近年来关于多元输出的函数的相关免疫性( 弹性函数) 也作了研究，并 得出很多成果本章从一个新角度着手研究相关免疫函数：从相关免疫函数的支 集入手，研究使相关免疫函数取值为1 的那些向量的特点，最终给出相关免疫函 数的一个等价描述，将其归结为满足某种关系的一些集合并从这种观点出发对 最简单的一些相关免疫函数( 重量为4 和6 的函数) 的计数作了研究 一、相关免疫函数的研究背景 在传统的流密码体制设计中，人们想方设法构造能满足必要伪随机特性的组 合函数在这些特性中，除了生成的序列要有很长的周期、在一个周期中游程分布 均匀、线性复杂度高等要求外，抗线性等价功绩是一项很重要的评价指标，为此密 码学中通常先用线性的方法产生有限个具有好的伪随机特性的序列，再将这些序 列通过非线性变换来产生密钥数据流例如用s 个线性反馈移位寄存器l f s r 序列 爿。，x ：，x 。与一个布尔函数f ( x ) 相结合的方式产生密钥数据流序列z * ，如下 图所示： 1 0 何x ) 图2 1 流密码示意图 其中x ，。是由第f 个线性反馈移位寄存器l f s r i 产生的m 序列，它是以有限域 五上的不可约多项式镌( x ) 作反馈多项是产生的线性序列； ) 是明文序列； c 。 是密文序列，满足c 。= z 。+ k 这里儿涉及到的运算都是在域疋上进行的设k 是 序列x 。的线性复杂度，k ，= 是生成z 。的移位寄存器的级数，即多项式聊，( x ) 的 次数d e g ( m , ( x ) ) 下面分析一下这种密码体制并介绍“分而治之”攻击 1 、密码分析者掌握的已知条件 通常假设密码分析者能掌握以下的内容： ( a ) 足够长的密文序列慨，c ：，h ，c 。) ，即足够大； ( b ) 布尔函数f ( x i ，x 2 ，x 。) ； ( c ) 所有的l f s r i 的级数t 甚至多项式m ，( x ) ，f - 1 , 2 ，s ； ( d ) 明文语言编码的部分统计特性，主要表现为o ，1 分布不均衡 p 。= p ( 匕= o ) = 1 2 + 民，磊 0 2 、理论密钥量 理论密钥量k = l 。：- i r , ( u - 1 ) ，其中墨2 巧r ( 2 - 1 ) 是域最上的次本原多 项式的数目，2 。一1 是l f s r i 可能的初始状态的数目当磅( x ) 已知 吃k = n ( 2 一1 ) 3 、对体制的“分而治之”攻击 d i v i d ea n dc o n q u e r ：“分而治之”，取名于一种图论算法，意为将一个待求解问 题分解成许多子问题，先对每个子问题求解，再综合求解这种攻击方法是 s i e g e n t h a l e r 于19 8 4 年提出的口1 具体如下： 首先，经分析测试，一旦发现某个，使得 p ( i 厂( 一n ，x 2 n , , x s n ) = x ；n ) = 必+ t ，则我们有如下引理： 引理i 川密文c 。与产生密钥序列的函数厂( x ，x ：，) 的第个输入分量x ，。 的相合概率见= p ( 巳+ = o ) = + 哦哆 必 由引理1 可以看出，用密文序列 q ) 来估计 x 。) 是可行的事实上，对由任意 本原多项式作联结多项式产生的序列x o = x 。) ，j ，0 是伪随机序列且与密文序列 q 是相互独立的，这必然有p ( 。= 吒) = ，而如果甄是以本原多项式( x ) 作联结多项式产生的序列，一有p ( x o 。= 。) = 必+ 坑t 因此对足够大的n 作统计，得到的相合概率大过某一阈值时，就认为该序列是以这个多项式作连接 多项式生成的逐个对所有的本原多项式及其初态做试错，就可以找出生成缸。) 的本原多项式及其初态这样找出子密钥需要足( 2 。一1 ) 次试错( 最坏情况) 各个 子密钥是相互独立的，逐个攻破，攻击该密码体制所需的计算量就降为 r ，( 2 一1 ) 密钥空间大大减小，这对密码体制来说是不安全的关于这种攻击的 ，= i 详细论证参考s i e g e n t h a l e r 的文章哆 针对这种攻击，s i e g e n t h a l e r 提出了相关免疫函数的概念，要求引理1 中的 6 ，= 0 ，满足这个条件的函数至少对上面描述的这种简单攻击是有抵抗力的 二、 相关免疫函数的基本性质 1 基本定义 z = f ( x ，x ：，_ ) 是一个布尔函数，x 1 ，x 2 ，x 。是独立同分布随机变量，下面对相 关免疫函数的定义是t s i e g e n t h a l e r 最早提出的： 定义2 1 【2 】称z = ，( _ ，x ：，矗) 是m 阶相关免疫函数，如果对 v 昧i 2 ，i m ) c 1 , 2 ，n ) ，v ( a l ，a 2 ，d 。) g 五”， 有p ( f ( x l ，x 2 ，_ ) = 1 ) = p ( f ( x l ，x 2 ，并。) = 1 ( _ ，x j 2 ，x k ) = ( 盯l ，口2 ，盯。) ) ， 其中0 m 玎 如果z = f ( x 。，x ：，_ ) 是m 阶相关免疫函数而不是m 十1 阶相关免疫函数，则 称函数的相关免疫阶为拼 相关免疫函数经提出，人们作了大量的研究。给出了许多种等价的刻画 2w a l s h 谱刻画 定理2 1 【3 1 ( x i a o - m a s s e y ) 域疋上的函数，( 一，x 2 ，x 。) 是m 阶相关免疫函 数当且仅当1 ( w ) s m 时必有s r ( w ) = o ，其中( 忉是w 的汉明重量 由函数的w a l s h 谱集于与函数代数表达式中各项系数的关系，结合定理2 1 可以求出，1 7 1 阶相关免疫函数的代数表达式中，所有次数高于n m 的项的系数 都是o 这就得到： 定理2 2 f 3 1m 阶相关免疫函数的代数表达式代数次数不高于胆一朋 定理2 2 蕴含着布尔函数代数次数与相关免疫阶之间的矛盾而代数次数不高 的函数往往较容易用线性函数来逼近 3 真值表刻画 设，：e ”一r ，定义c ( ，) = 扣1 ：2 ”i f ( c ) = 1 ) 为函数f 的支撑点集，记 ( 力= l c ( 力j ，称为函数f 的重量，取最”中在函数f 作用下值为l 的所有向量排 成的矩阵，称为函数f 的特征矩阵或厂的真值表，仍记作c ( j ) ，或简记为c 对相关免疫函数，有如下的特征矩阵刻画； 命题2 1p 1 ( j c a m i o n ) f 是所阶相关免疫函数当且仅当矿( ) = 2 ”k ，1 且对于任意m 元集合 ，j 。，。 ( 为 1 ，_ ，2 ，”) 子集) ，取矩阵的 ，：，j ，列得 到子矩阵，该子矩阵中v “= ( “，”：，) e ”都出现k 次 显然，具有相关免疫性的函数重量必是偶数 三、一阶相关免疫函数的一种等价描述 1 用以函数值为分量的向量表示b o o l e a n 函数 任意函数由其在空间所有点处的函数值决定故可以用2 ”维向量 k ( o ，o ，o ) ，f ( 0 0 ，1 ) ，厂( 1 1 ，1 ) 】表示b 0 0 1 e a n 函数，( x ) 以p ，p ：，p ：。分别表 示向量【1 ，0 0 ，o l o ，1 0 ，o l ，【o ，0 0 ，1 】这样，任意一个布尔函数，可以由若干个 p 之和表示 2 一阶相关免疫函数的构造 将，( x ) 在( 0 0 ，0 ) ，( o 0 ，1 ) 到( 1 ，1 ，1 ) 的函数值排成列向量，分别记为 ，( o ) ，( 1 ) ，f ( 2 ”一1 ) ，构成一个序列假如函数为一阶相关免疫，则由定义易知，对 于所有的( 薯，x 2 ，x ，) ，将f ( x l ，x 2 ，x ，x 。) 与f ( x 1 ，l + x ，x 。) 互换 位置，序列依旧表示一个相关免疫函数，即分别对应x = l 和x ，= 0 的两部分组成 的两个子序列，其重量是相同的 定义映射盯，： n 元布尔函数 斗 t , 元布尔函数) ，( i = 1 , 2 ，丹) 盯，：f ( x i ，x 2 ，x 。) 卜_ f ( x l ，z 2 ，一x 卜l ，x ，+ l ，工，+ i ，x 。) 二映射的乘法定义成对布尔函数的相继作用，易验证 1 i ，茎n ，q 仃j ( ，) = q 仃。( ，) = f ( x 1 ，x 2 ，x i _ ix 。+ l ，工，+ l ，工，一】，x + 1 ，x ，+ i ，x 。) 1 i ”，仃，2 = d ，其中尉表示恒同映射 定义群g ，由映射盯，生成( i = 1 , 2 ，胛) 该群是交换群，每个元素都是二阶元 群g 同构于z ：z ：z ：，z ：表示二元群群g 对任意e ，的作用轨道就是集合 q ，p ：，p ， ，即群g 中2 ”个元素各自对e ，作用产生的2 ”个结果均不相同，即任意 e ，可以由任意e 经g 中某个元素作用得到 设函数厂( x ) 重为2 f ，即r ”中使，( x ) 为l 的向量有2 f 个将，( z ) 表示成2 tp 。 的形式，o i u 为g 中把p 。映为口，。的变换因为g 包含2 ”个元素，丽g 可以把t 映 为任意p ，因此，o i u 。是g 中唯一把p 。映为8 的元素o j 可以表示成若干个吒 的乘积记仃儿一= i - i q ，因为盯，都是二阶元素，仃n ，。也把p ，映为p 。对任意 p 一，( z ) 可以表示成盯帆，。( p ，。) 的形式将每个q 。表示成f i 仃，得到2 ，个集 h = f ，n 定理2 3 阶相关免疫函数对应于上面讨论的2 t 个集合，对于任意 i 1 , 2 ，n ) ，满足i 属于且只属于其中f 个集合 证明：函数厂具有一阶相关免疫性 铮p ( f = 1 ) = p ( f = 1 ix ，= 1 ) = p ( f = 1 ix ，= 0 ) ，1 i 车i ( x l ，x 2 ，x 。) 疋”：f ( x 1 ，x 2 ，x 。) = 1 ，x 。= 1 ( 1 ) ( 2 ) = f ( z l ，工2 ，x 。) 咒”：，( x i ，石2 ，) = l ，x ，= 0 ( 3 ) 下面考察盯，对函数p 。，e ，p ：。会产生什么样的作用 e o = ( x 1 + 1 ) ( x 2 + 1 ) ( x 。+ 1 ) 盯，。口o = ( x l + 0 ( x 2 + 1 ) ( x 。) ( x 。+ 1 ) 即e o 经仃，作用后从集台 f ：f ( x ，。，0 ，z 。，。) = 1 ) 变换到集合 厂：( x l ，x h ，1 ，x ，x 。) = 1 中，同样把 f ：f ( x ，_ h ，0 ，x ，x 。) = 0 ) 变换到集 合 ，：，( x ”。“，1 ，x 。，x 。) = 0 中对q ，p ：，p 2 - 1 的作用可依此得出 假如对某个，在多于，个集合中出现，仃，对e o 作用多于f 次，则必有 ( z 【，x 2 ，工。) 五”：f ( x l ，x 2 ，z 。) = 1 ，x ，= 1 l ( x i ，x 2 ，x 。) r ”：f ( x 1 ，x 2 ，z 。) = l ，x ，= 0 同理，如果某个j 在少于f 个集合中出现，上面不等式也成立结论得证 2 t 个集合“，：，：，都是 i ，2 ，” 的子集对任意p 。( 兀盯，) ( e ，。) 表示 个重为2 ，的函数，如果这些集合满足定理2 3 中的条件，则由定理2 3 的证明可 知该函数是一+ 阶相关免疫函数这样我们得到了本文的第一个结论： 一阶相关免疫函数的构成可以归结为寻找 1 , 2 ， ) 的2 f 个子集，：， 满足：对任意j 1 , 2 ，一 ，j 属于且只属于其中f 个集合 四、一阶相关免疫函数的计数 下面考虑一阶相关免疫函数的计数问题我么有下面命题： 命题2 2 重量为2 r 的”元阶相关免疫函数共有n ( n ，2 t ) 个r 其中n ( n ，2 t ) 表 示满足定理2 3 中条件的包含2 f 个集合的集合类的个数 证明：用上面的方法构造相关免疫函数，任意给定一个初始序列e 。和2 ，个满 足上面定理条件的集合，就可以确定一个一阶相关免疫函数，记为e ，。；o ，：，：， 满足定理条件的集合类有n ( n ，2 t ) 个，则对应不同的初始序列有2 ”n ( n ，2 t ) 种搭配 前面讨论过，任意8 ，可以由任意e ，经g 中某个元素作用得到，所以， f f z , 意e ，搭配适 当的集合都可以生成特定的函数。因此，每个一阶相关免疫函数对应2 ”中搭配方 式，得到结论：重量为2 f 的n 元一阶相关免疫函数共有n ( n ，2 t ) 个 计算n ( n ，2 t ) 是一个很复杂的问题，下面仅对最简单的几种情况作一下计算 1 重量为2 和4 的一阶相关免疫函数 定义2 2 布尔函数厂：e “斗疋，4 中使，为l 的所有向量作为行向量组成 的矩阵成为，的特征矩阵 e “中的一对向量称为共轭向量，如果它们做二进制加法得到( 1 ，l ，1 ) 在某些向量处取值为1 其余取值为0 的函数称为这些向量组成的集合的特征 函数 6 每个向量的特征函数对应一个在定理2 _ 3 中讨论过的集合，此集合对应g 中将 矗映成浚向量的变换一对共轭向量对应的两个集合是互补的 重量为2 的一阶相关免疫函数结构最简单根据定理2 3 ，这类函数对应两个 集合，。，：正 1 ，2 ， ，满足任意i 1 ，2 ，h 属于且只属于上述两个集合中的一 个其对应的特征矩阵必然是由两个共轭的向量组成的即重量为2 的相关免疫函 数有c 个 对重量为4 的一阶相关免疫函数我们有如下命题： 命题2 3 重量为4 的一元一阶相关免疫函数有c + c 2 4 m ( n 一1 ，4 ) + 2 c 2 ：。 个，其中m ( n ，4 ) = c 2 4 m ( n 一1 ，4 ) + 2 c ，m ( 3 ，4 ) = 2 证明：重量为4 的一阶相关免疫函数有两种情况： ( 1 ) 其特征矩阵由两对共轭向量组成； ( 2 ) 如果其特征矩阵特中有一个向量，其共轭向量不在矩阵中，则这四个向量互 不共轭，对应的四个集合中不存在互补的集合对 事实上，如果其特征矩阵特中有某一个向量，其麸轭向量不在矩阵中，则必有 第二个向量的共轭向量也不在矩阵中这两对向量不共轭，其对应的集合必不互补 如果另外两对集合互补，所有的 1 2 ，n 中的元素都在这两个集合中出现一次，则 这四个集合必不满足定理2 3 的条件 情况( 1 ) 的构成比较简单从2 ”1 对共轭向量中选取2 对，就得到所有的这种 函数，共有c 1 个 对情况( 2 ) ，任意i 1 , 2 ，, ) ，四个集合呵以表示为 i ) u ， f ) u j ，j ，其中 ，c ( 1 , 2 ，n j f 假如存在某个i 1 , 2 ，n ，使得 i u ， 西u j ，t ，这四 个集合中，= ，则：n j o j3 i 。 1 , 2 ， ) 在 i u ， i u a ，至少三个集合 中出现，不符合定理2 3 的条件；i u j 1 , 2 ，胛 i j j f 0 1 , 2 ，r ) f 最多只 在j 1 中出现，不符合定理2 3 中的条件由此必有，u ，= 1 , 2 ，n ) f ，n ，= o 于 是 f ) u ，u j = 1 , 2 ，h ，这四个集合是两对互补的集合这由于这种情况的假设 1 7 条件矛盾 因此，对情况( 2 ) ，从四个集合中除去任意元素i 1 , 2 ，” 后得到的四个集合 必然依旧是互不相等的且余下的四个集合是 l 2 ，”) i ) 的子集且满足 l 2 ，, i ) 中每个元素都属于且仅属于其中两个集合，即余下的四个集合可以 构造一个, 一1 元相关免疫函数 任意一个”一1 元相关免疫函数对应序列岛( 一1 元向量( 0 0 ，0 ) 的特征函数) 和四个集合，四个集合满足定理2 3 中的条件在四个集合中的任意两个之中加入 元素n ，得到的四个集合依然满足定理2 3 的条件，这样加上e 。( n 元向量( 0 , 0 ，0 ) 的特征函数) 就可以构造一个疗元相关免疫函数进一步，如果h 一1 元相关免疫函 数对应的4 个集合是情况( 2 ) 的，则在其中选两个加入元素胛得到的n 元相关免疫 函数也是情况( 2 ) 的 如果除去元素 后得到的是两对共轭向量，可以用如下方法构造：选两对 一1 元向量，每一对都是共轭的，则对应得到两对互补的集合，在某一对互补集合中加 入元素门，另一对中不加入，得到一个4 个 元集合，对应一个n 元相关免疫函数， 也是属于情况( 2 ) 的显然这两种方法下构造的n 元相关免疫函数不会重复 综上所述，所有重量为4 的”元一阶相关免疫函数在情况( 2 ) 时，可以用如下两 种方法构造： ( a ) 对情况( 2 ) 时重量为4 的 一1 元一阶相关免疫函数，从它对应的集合中任 意选两个加入”，假设对应”一1 元相关免疫函数在情况( 2 ) 时的函数有m ( n 一1 ，4 ) 个，则 元这种函数有c ：扣一1 ，4 ) 个 ( b ) 选两对互补的甩一l 元集合，在某一对互补集合中加入元素n ； 一1 维空间 中有2 ”2 对共轭向量，这种情况对应的函数有2 c 4 - ( a ) 与( b ) 两种情况相加得d m ( n 一1 ，4 ) + 2 c 个 将情况( 1 ) 和( 2 ) 对应的所有可能的函数个数相加就得到结论 2 重量为6 的阶相关免疫函数 命题2 4 重量为6 的阶相关免疫函数的个数为： 8 n ( n ，6 ) = m ( n ，6 ) + c l + m ( ，4 ) c _ 一。 ， m ( n ，6 ) = 2 m ( n l ，4 ，。2 i 。- 2 - 4 c t 4 + m ( n 一1 ，6 ) c 6 3 + 2 ”c 2 4 t ( n 一1 ) 其中n ( n ，6 ) 表 示重量为6 的”元一阶相关免疫函数的个数，m ( n ，) 的意义和命题2 2 中同，r ( n ) 表示将n 个元素分成四个非空集合的所有不同分配方法的数目， m ( 5 ，6 ) = 2 4 c 2 4 + 2 m ( 4 ，4 ) c ：c ： 证明：重量为6 的一阶相关免疫函数包含以下几种情况： ( 1 ) 函数由3 对共轭对构成； ( 2 ) 函数的特征矩阵中包含1 对共轭对，其余4 个互不共轭； ( 3 ) 函数特征矩阵的六个向量互不共轭 第一种情况对应的函数结构简单，从2 ”1 对共轭向量中选取3 对就得到全部 这样的函数共c 1 种 第二种情况对应的函数可以由重量为4 的一阶相关免疫函数添加适当共轭 向量对构成要求这里的一阶相关免疫函数对应的特征矩阵中的向量互不共轭这 种函数共m ( 4 ) c - 一。个，其中m ( n ，4 ) 表示重量为4 并且特征矩阵中不包含共轭 向量对的n 元一阶相关免疫函数的个数，c l 。表示除去四个互不共轭的向量后 任选一对共轭向量 下面主要讨论第三种情况考虑这类函数的特征矩阵，其中包含6 个向量，并且 互不共轭每个向量对应一个若干个盯，的下标构成的集合，由上面的讨论知，这六 个集合相互之间不互补设函数是n 元函数，则六个集合中，有三个包含”把这六 个集合中的h 都去掉，则可能产生以下几种情况： ( a ) 得到六个h l 元集合，互不相同； ( b ) 得到的六个”一1 元集合中洧两个相同： ( c ) 得到的六个n 一1 元集合中有两对相等的集合对； ( d ) 得到的六个”一1 元集合是三对相等的集合对 对情形( c ) 假设六个集合为 ) u 1 ， h ) u ，j ， h u k ，k f 陧如i n j = 庐 而八j i ， 1 , 2 ，n 一1 ) ，则 1 2 ，h 一1 中的元素最多只在k 和k 中出现，则最多属 f 两个集合；假如i a j 庐，则其交集中的元素在 h u ， n u j ，j 四个集合中 出现，这两种情况都弓该函数的一阶相关免疫性矛盾，故，n j = 庐且 八j j = 1 ，2 ， 1 ) 因此i u j u n = 1 ，2 ，竹一1 ， 而刚才的论述说明六个集合 中不存在一对互补集合，与i u j u n ) = 1 , 2 ，n 一1 ，月) 矛盾故此，这种情况是不会 产生的 对情形( d ) ，假设六个集合为 n ) u ， ”) u j ，j ，伽 u k ，k ，同样，假如 i a j 驴，则其交集中的元素在 u ， h u ，j 四个集合中出现，故，j ，k 互 不相交；则 1 2 ，”一1 ) 中的任意元素最多属于两个集合，这也与该函数的一阶相 关免疫性矛盾这种情况也不可能出现 因此，重量为六的一阶相关免疫函数只对应四种情形：三对共轭向量；一对 共轭向量；不包含共轭向量，且除去”后得到一个”一l 元一阶相关免疫函数，即 情形( a ) ；不包含共轭向量，除去n 后得到的六个集合中，其中有一对是相等的，即情 形( b ) 考察情形( a ) 中的六个 一1 元集合， 1 2 ， 一1 ) 中的元素，每个都属于且仅 属于这六个集合中的三个，即这六个集合可以构成一个h 一1 元的一阶相关免疫函 数 这些n l 元函数对应三种情况：l 、三个共轭对；2 、一对共轭对另外四个互 不共轭：3 、六个向量互不共轭1 、如果是三个共轭对，对应三个互补集合，这样无 论如何加入n 都不可能产生六个互不互补的集合，这种情况不可能出现：2 、这种 情况可能出现，需要在互补集合中加入n ，在四个互不：互补的集合中选一加入n ，或 在四个互不互补的集合中选三加入n ；3 、六个集合中选三加入n 对情形( a ) ，也只用2 、3 两种情况出现 考察2 ，m ( 一l ，4 ，。：1 。一。个n 一1 元相关免疫函数，他们由一对共轭对和四个互 不共轭的向量组成在共轭对中加入n ，再四选一加入n ，共m ( n 一1 ，4 ) c 0 一。c ：在 共轭对中不加入n ，再四选一不加入n ，共m ( n 一1 ，4 ) c 一。c ：总计 2 m ( n - 1 ，4 ) c 0 一。c ： 2 0 考察3 ，设n 1 元互不共轭的向量六个组成的相关免疫函数有m ( n 一1 ，6 ) 个这 i j m ( n 一1 ，6 ) c 3 6 对于四元函数，由互不共轭的6 个向量组成的共轭函数对应 6 个集合，已证明从这些集合中除去n ，得到的如果必然是6 个不同的向量，他们是 三维向量，这些三维向量各不相同而且不可能是三对共轭向量，它们构成了三元的 相关免疫函数三元重量为六的函数只有一种可能，三对共轭对，这产生矛盾可知， 四元函数中不可能有这种函数：重量为六，且六个向量互不共轭对五元函数，如果 去掉n ，依然得到六个不同的向量，必然是由一对共轭向量另外四个互不共轭的向 量组成的这样对与如下这类：重量为六的五元相关免疫函数所对应的六个集合 互不互补且出去n 得到一个四元相关免疫函数，它对应的四元相关免疫函数必然 是由一对共轭对另外四个互不共轭的向量组成的这类函数共有 2 m ( 5 1 ，4 ) c 1 2 s - 2 - 4 c ：= 2 m ( 4 ，4 ) c 。1c ：个重量为六的五元相关免疫函数所对应 的六个集合互不互补且出去r l 后得到的六个集合中有一对是相同的，这种情况有： 2 4 r ：个这样，五元重量为六的函数其对应的集合互不互补，这种函数共有 2 4c ：4 + 2 m ( 4 ，4 ) c 。ic ：个即m ( 5 ，6 ) = 2 4 c 2 4 + 2 m ( 4 ，4 ) c ：c ： 现在考察情形( b ) ，假设六个集合为伽 u ， 拧) u j ， 一 u k ，k 考察这 类函数的特征矩阵c ，c 由6 个向量组成，其中的一对可假设为q ，口：，+ l 和 q ，口：，h h ，0 ，其中的a ，( i = 1 , 2 ，# - 一1 ) 取值为l 或0 当a 。= l 时，表示i 属于该向 量对应的集合，否则不属于该向量对应的集合把六个向量排列得到矩阵如下： a n 1 1 a n 1 0 b 。1b 。 c n 1c n d 。】d 。 e n 1e n 考察上面的矩阵的前玎一1 列，后面四行中有一个与前两行在对应列列的分量相同 其余三个与该分量不同第n 列的b n , c 。，d n ，e 。中有两个为0 两个为1 现在增加一个 条件：要求矩阵中任意两行不共轭 一 一 舢却m西山钆 a叭仇“凼氏 首先我们可以证明，除去第 列后得到的矩阵中不存在共轭向量事实上，除 去n ，得到的n 一1 元向量组成的矩阵中，如果有和那对相等向量共轭的向量，这 时矩阵如下： a f a ， a 1 + 1 b 1 c 1 d 1 0 a n b 。 c n d 。 则a 。或为0 或为1 ，对应其特征矩阵中必有共轭对； 如果有两个向量共轭，且其中任何个都不属于那对相等的向量，这时矩阵 如下： 除去这对得到 a l a i b l + 1 b 1 c 】 d 1 a l a 2 a 1a 2 c ic 2 d 】d 2 1 0 b 。 b 。 c n d 。 a 。1 1 a 。1 0 c n ic n d 。id 。 四个向量中有一对相等，任意一个元素在四个向量对应的集合中出现两次 这必然可以推断出，d ，= c ，i = 1 , 2 ，r t 一1 前面已经论述过，这种情况是不可能出 现的 我们先对4 元函数考虑，我们给矩阵的分量分配适当值，首先确保后面四行与 前面两行都不共轭不妨假设b 4 和c 4 为l ，其余两个为0 _ = _ = j j 舭 i舢籼“o“ 要在b l ，。l ，d l ，e l 中选一个为a l ，另外三个为8 1 + 1 若令b l 为a 1 ，在第一和第四列的分 量处，第一行和第三行相等：若令d 。为a l ，则在该两列处，第一行和第五行相等不 妨假设b 1 为a i ，则c l = d 1 = e 1 - a i + 1 ，这时矩阵变为 a 3 1 8 3 0 b