（基础数学专业论文）bent函数的构造.pdf

兰州大学硕士学位论文 摘要 b e n t 函数是种特殊的布尔函数，由于它具有很多良好的性质而在很多领域得 到了广泛应用构造和研究多元b e n t 函数一直以来是一个重要课题 本文通过研究b e n t 函数的谱矩阵，得到了b e n t 函数的构造定理 设，( 。1 ，$ 2 ，) 为一个n 元b e n t 函数，记f ( 仳，t ) _ ) = ：三1 ( 一1 ) ，扣) + ”扣，嘶= 【2 2 f ( 珏，口) ) ，则有( 马) 母为一个2 n 铲阶归- - h a d a m a r d 矩阵；( 岛) 毋是 双对称矩阵；( b a ) 2 - g p n 打，是h a d a m a r d 矩_ 阵反之，对于任意的满足条 件( 最) ，( 岛) ，( 岛) 的2 ”2 “阶矩阵，存在唯的b e n t 函数，( 甄，w 2 ，) 使 得日，= h 作为构造定理的应用，我们给出了由犯元b e n t 函数构造竹十2 元b e n t 函 数的方法特别地，我们完全确定了所有四元b e n t 函数，并给出了其计数 关键词：布尔函数；h a d a m a r d 矩阵；归- - h a d a m a r d 矩阵；b e n t 函数；并元运算 兰丛查堂堡主兰垡丝兰 a b s t r a c t b e n tf u n c t i o ni sas p e c i a lb o o l e a nf u n c t i o nw i t hm a n yf i n ep r o p e r t i e s ，i ti sw i d e l y u s e d i n l o t s o f f i e l d s ，s o c o n s t r u c t i n g a n d s t u d y i n g m u l t i - v a r i a b l e b e n t f u n c t i o n h a s a l w a y s b e e na n i m p o r t a n t r e s e a r c hs u b j e c t i n t h i s p a p e r , t h e s p e c t r a l m 枷c e s o f b e n t f u n c t i o n a r e e x p l o r e d , a n d t h e n a c o n s t r u c f i n n t h e x h e m o f b a n t f u n c t i o n a r e g i v e n l e t f ( x l ，z 2 ，o n ) b c a n n - v a r i a b l e b e n t f u n c - f i n n , f ， ) = 删2 n - - 1 ( 一1 ) 7 水鲫) 。，嘶= 【2 ，( 钍， ) j ，t h e n ) ，i s a2 ”2 一 r e g u l a rh a d a m a r dm a t r i x ；( 踢) 珥i s ab i a y - s y m m e t r i cm a t r i x ；( b 3 ) 2 - ；r 研i s ah a d a m a r dm a t r i x c o n v e r s e l y , f o re a c h2 t ix2 “m a t r i xh w h i c hs a t i s f yt h ec o n d i t i o n ( b 1 ) ，( b 2 ) ，( b 3 ) ，t h e nt h e r ee x i s t sa nu n i q u eb e n tf u n c t i o nf ( x l , z 2 ，- - - ，z n ) s u c ht h a t 丑j = h a s a p p l i c a t i o n s ，s o m e m e t h o d s o f c o n s t r u c t i n g t h e ( + 2 ) 一v a r i a b l e b e n t f u n c t i o nb ym e a n so f ( n + 2 ) - v a r i a b l eb e n tf u n c t i o na f eg i v e n i np a r t i c u l a r , a l l4 一v a r i a b l e b e mf u n c t i o n sa r ed e t e r m i n e da n dn u m b e ro f 4 一v a r i a b l eb e n tf u n c t i o n si sg i v e n k e y w o r d s ：b o o l e a nf u n c t i o n ；h a d a m a r dm a t r i x ；r e g u l a rh a d a m a r dm a t r i x ；b e n t f u n c t i o n ；d y a d i co p e r a t i o n i i 原刨性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立进行研究 所取得的成果学位论文中凡引用他人已经发表或未发表的成果、数据、观 点，均已明确注明出处除文中已经注明引用的内容外，不包含任何其他个人 或集体已经发表或撰写过的科研成果对本文的研究成果做出重要贡献的个 人和集体，均已在文中以明确方式标明 本声明的法律责任由本人承担 论文作者签名： 套诘 日期：型：i ： 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归属兰州 大学本人完全了解兰州大学有关保存、使用学位论文的规定，同意学校保 存或向国家有关部门或机构送交论文的纸质版和电子版，允许论文被查阅和 借阅；本人授权兰州大学可以将本学位论文的全部或部分内容编入有关数 据库进行检索，可以采用任何复制手段保存和汇编本学位论文本人离校后发 表、使用学位论文或与该论文直接相关的学术论文或成果时，第一署名单位 仍然为兰州大学 保密论文在解密后应遵守此规定 论文作者签名；监导师签名；避 日期：塑堕! ! ：! 兰州大学硕士学位论文 第1 章引言 随着计算机和通信技术的发展，用户对信息的安全存储，安全处理和安全 传输的需求越来越迫切特别地，随着i n t e r n e g 的广泛应用，以及个人通信，多 媒体通信，办公自动化，电子邮件，电子自动转帐支付系统和自动零售业务网 的建立和实现，信息的安全保护问题自觅显得更加重要丽解决这一问题的有 效手段之一就是使用现代密码技术 “密码学新方向”【2 卿的发表和美国数据加密标准d e s 删的颁布实施标志 着现代密码学的诞生，从此揭开了商用密码研究的序幕此后，实用密码体 制的研究基本上沿着两个方向进行，即以r s a t 3 1 1 为代表的公开密钥密码体 制和以d f s 为代表的秘密密钥分组密码体制当前分组密码受到了广泛的 关注并且成为密码学的研究热点之一【3 2 】在分组密码的实际设计中，多输出 的布尔函数常常扮演重要角色，例如分组密码的典型代表一美国数据加密标 准d e s 算法的核心是8 个s 盒，丽其每一个s 盒都可以看成一个从昭到碍的多 输出布尔函数因此如何构造更多具有良好的密码性质的多输出布尔函数是 值得研究的重要课题 在密码学中，对密码系统的攻击一直伴随着密码学的发展过程，因此密 码的设计与分析始终是两个既互相对立又互相依存的研究方向进入9 0 年 代以后，伴随着对密码系统的线性攻击和差分攻击技术的发展，d e s 已经渐 渐退出了历史舞台而被a e s 取代为了对抗这两种攻击，人们对密码系统的 设计中对布尔函数提出了更加严格的要求其中非线性度就是为了抵抗线 性攻击而提出的性能钷量指标b e n t 函数 2 , 3 1 是由r o t h a u s 于1 9 7 6 年提出的一 类特殊的布尔函数，由于b e n t 函数是具有最高的非线性度的布尔函数。所以 对b e n t , 函数的研究成为一个重要课题利用b e n t 函数可以构造出循环相关 和伪随即性都很好的最佳离散信- 号( b e n t 序列【2 l ”2 4 1 ) 此外，由于b e n g 函数在 编码和密码等各个领域有重要应用f 1 5 1 叼，因此受到人们的关注 b e n t 函数用于多址通信和密码学等许多领域。在码分多址( c d m a ) 通讯 系统中，为了区分不同用户并保持系统的自同步性，需要使用一种具有较小 兰州大学硕士学位论文 自相关和码间互相关的周期序列而由b e n t 函数得到的序列一口e 佗t 序列具 有良好的自相关及互相关性质，从而被广泛应用 5 , 1 7 ”2 0 1 如澳大利亚的加密 标准h a v a l 算法设计中用到的5 个布尔函数无一例外都是由b e n t 函数演化 而来此外，文1 1 1 中的研究结果表明，b e n t 互补函数族在区分初始信号及并元 移位信号方面有很重要的应用，而多维b e n t 函数1 3 j 一每个分量以及各分量的 非零线性组合都是b e n t 函数的多输出爵数，正是特殊的b e n t 互补函数族 在流密码体制中，b e n t 函数用做前馈网络的非线性组合函数可以很好的 抗相关攻击和线性逼近 t 构造全部b e n t 函数并对其进行分类是研究者的梦想这一愿望只对八元 以下的b e n t 函数实现( 计算机搜索) 对于多元b e n t 函数，目前只有零散的构 造办法，其中一些不能给出显式的代数表达式 4 1 本文通过借助并元理论研究了b e n t 函数的谱矩阵，得到了b e n t 函 数的构造定理设y ( x l ，x 2 ，茁。) 为一个n 元b e n t 函数，记f ( “，v ) = 当1 ( 一1 ) 7 扛) + ( 的咖，所= ( 2 一 f ，t ) j 。则有( 聩) 毋为一个2 “2 n 阶归 一日甜n m a r d 矩阵；( b 2 ) 毋是双对称矩阵；( 岛) 2 一g p n h i 是日n 如m n r d 矩 阵反之，对于任意的满足条件( b 1 ) ，( b 2 ) ，( 点b ) 的2 “酽阶矩阵日，存在睢一 的b e n t 函数i ( x 1 ，名2 ，) 使得抒，= 日从而使得构造b e n t 函数的问题转 化为构造文中给出的这类特殊h a d a m a r d 矩阵的问题作为构造定理的应用， 我们给出了由n 元b e n t 函数构造n + 2 f f b e n t 函数的方法特别地，我们完全 确定了所有四元b e n t 函数，并给出了其计数，得到了和文献1 2 5 1 中同样完美的 结果 2 兰州大学硕士学位论文 第2 章预备知识 本章将余绍一些相关的概念和结果第一节给出h a d a m a r d 矩阵的定义 和性质，第二节介绍了布尔函数及其谱表示，第三节给出并元理论和运算性 质。最后是日e 耐函数等价定义和h a d a m a r d 变换 2 1h a d a m a r d 矩阵 首先给出二维h a d a m a r d 矩阵定义 定义2 1 1 设a = 叼】是一个n xn 阶矩阵，是任意自然数如果同时 成立。灯= 士1 ( 1 i ，j ) 和 a t a ；a a t ：n i 那么就称a 是一个h a d a m a r d 矩阵( 或者简称为日矩阵) 【1 0 ”捌 以后我们所提到的h a d a m a r d 矩_ 阵都是二维日矩阵，以便和高维日矩阵区 别开来 定义2 1 3 , 维仇阶矩阵h = 【h ( q ，i 2 ，i 。) 】，( 0 缸m 一1 ) ，称 为r , 维m 阶h a d a m a r d 矩_ 阵，如果 并且 h ( i l ，i 2 ，i n ) = 土1 ，0 冬i k m 一1 h ( 。m i ，i n ) 啉i 2 ，t n ) = 舻。1 ， o ：算2 ，i n _ m - 1 h ( 札n 沌， 0 t l 。i 3 。t n 2 ) ，则n 一定是4 的倍数，即n = 4 k ，k 这一性质说明，对于大于2 不是而4 的倍数阶的二维h a d a m a r d 矩阵是不存 在的因此今后在构造二维h a d a n m d 矩阵时，只需考虑4 的倍数阶的矩阵就可 以了但是反过来对于任意形如礼= 4 k 的正整数是否一定存在竹郴奔二维 的日阵呢? 这一问题至今尚未解决 归- - h a d a m a r d 矩阵 归- - h a d a m a r d 矩阵 s l 是二维日阵的子类，它是由g s z e k e r s 于1 9 6 9 年首先 提出来的。其定义是 定义2 1 6 若a = 【 是一个h a d a l n a 嗣矩阵，并且该矩阵中各行( 各 列) 中的所有元素之和都为一个常数，则称a = l n j 】为归一h a d a m a r d 矩阵 ( 或者简称为归一h 阵) 例如矩阵 4 兰州大学硕士学位论文 ( ；至三 ) 2 2 布尔函数理论 礼个变元的布尔函数， ) 是指从野到屁上的一个映射一般记为，( z ) ： 毋一f 2 ，卫毋它有多种表示形式本节我们主要来介绍布尔函数厂( 。) 的 四种表示形式，即真值表表示，小项表示，多项式表示和谱表示等 布尔函数表示 1 真值表表示 由于布尔函数的定义域和值域都是有限集，故可以用列表法表示 一个n 元的布尔函数( x ) ：曰一乃是否给定，关键在于该函数值是否 对于每一组变量x = 0 l ，现，) 均已确定如果把每一组变量茁= ( 留1 ，$ 2 ，) 与其对应的函数值全部列成表格，这种表格就称之为布尔函 数的真值表习惯上总是按照二进制表示善l ，$ 2 ，z 。之值递增豹顺序自上 而下排列真值表( 视z 。为最低位) 在此约定下，将表中函数值构成的向量称 之为函数值向量 例如下表就是二元布尔函数f ( x ) = f ( x l ，x 2 ) = 1 + 茁l z 2 的种表示 xo 0ll olol “x ) 01lo 兰捌奎主蟹主堂焦笙塞 若将o 到2 ”一l 之间的整数表示成二进制 l ，x 2 ，) ，则可将从。到2 n 一 1 之问的整数和曰上的向量一一对应起来，即 h ( x l ，x 2 ，z n ) 整数从小到大的顺序刚好对应霹中的元素的字典序今后，在不引起混 淆的情况下，我们将二者等同 对于一般的礼元函数f ( x ) ，可将其函数值按照$ 的字典序从小到大排列成 一个向量( ，( o ) ，( 1 ) ，f ( 2 ”一1 ) ) ( 2 1 ) 我们也将上式称为函数，( z ) 的函数值向量或真值表记为7 称一个0 ，1 向量口的h a m m i n g 重量为其1 分量的个数，记为w hb ) 布 尔函数，如) 函数值向量的舶m m l 礼9 重量称为，( z ) 的重量，记为i ( ，( $ ) ) 若n 元布尔函数f ( x ) 的h a m m i n g 重i ) 9 2 ”1 ，则称， ) 为平衡布尔函数 对于戡，c i f 2 ，我们约定$ = 她，茁p = 面= 1 + 戤，于是有 r 茁 ：p 产 【o ，x i q 设整数c = ( c 1 ，c 2 ，) ，。= ( z 1 ，x 2 ，z 。) ，则有 z p z 字。挈： 1 ，( 。h 茹。，z n ) = ( c l c 2 , 。，c n ) ， 10 ，( x l ，x 2 ，$ n ) ( c 1 ，c 2 ，c ，1 ) 由此得到 ，c 。) z i l z 字z 挈( 2 2 ) 称上式( 2 2 ) 为，( z ) 的小项表示，其中是在飓中求和 例如前面表中表示的布尔函数f ( z ) ：曰一玛的小项表示为 f ( t 1 ，x 2 ) = 0 - 茁0 1 珥0 2 + 1 - x o x ；+ 1 - 。 霹+ 0 岳；茁； = z 2 z j + z z 2( 2 3 ) 6 cc ， 咖 | l o ， 兰州大学硕士学位论文 3 多项式表示 将式( 2 3 ) 中的遗= 1 十x l ，胡；1 + x 2 ，代入化简，得，( x ) = f ( x 1 ，。2 ) = ( $ 1 + 1 ) 观+ 叨( 勉+ 1 ) = z l + 茹2 ，此即为，0 ) = ，( 黝，沈) 的多项式表达 显然，任意扎元布尔函数f ( z ) = ，( 茹l ，x 2 ，z 。) 都可以根据( 2 2 ) 化为多项式 表达式 ，( 茹) = a 0 + n i i 2 q ，茁q x i 。趣，( 2 4 ) r 薯11 s 赴 i 2 2 ”2 1 ，同理可知上述四个2 仆- 2 2 n - 2 阶矩阵仍具有引理3 7 中的分头形式，并 且要证码， 为分块取对称矩阵，只需证明t j h 的第一个行块的四个为分块双对称 幅耩这样的过程可以持续到第一个块的四个矩阵为2 2 2 2 矩阵为止，于是要证 明乃( j = 0 ，2 n ，2 2 “，3 2 ”) 为分块双对称的，只需证明这四个矩阵为双对称矩阵 即可，容易看至4 这四个4 阶矩阵具有如下形式 h ( o ，t ) f 日( 1 ，t ) 1 日( 2 ，t ) 日( 3 ，t ) n ( o ，t + 4 ) l 嚣( 1 ，t + 4 ) 1 日( 2 ，t + 4 ) n ( a ，t + 4 ) h ( 0 ，t + 8 ) 1 日( 1 ，t + 8 ) l 口( 2 ，t + 8 ) n ( 3 ，t + 8 ) ，h ( 0 ，t + 1 2 ) f 盯( 1 ，1 2 ) 1 日( 2 ，t + 1 2 ) h ( 3 ，t + 1 2 ) h ( o ，t + 1 ) h ( 1 ，t + 1 ) h ( 2 ，t + 1 ) h ( 3 ，t + 1 ) h ( 0 ，t + 5 ) h ( 1 ，t + 5 ) h ( 2 ，t + 5 ) n ( 3 ，t + 5 ) h ( o ， h ( 1 ， n ( 2 ， h ( 3 ， h ( 0 ， h ( 1 ， n ( 2 ， h ( 3 ， + 9 ) + 趴 + 9 ) + 9 ) + 1 3 ) + 1 3 1 + 1 3 1 + 1 3 ) h ( 0 ， h ( 1 ， h ( 2 ， h ( 3 ， + + + + h ( 0 ， h 0 ， h ( 2 ， h ( 3 ， 4 ) 4 ) 4 ) 4 ) + 3 ) 十3 ) + 3 ) + 3 1 n ( 0 ， h ( 1 ， h ( 2 ， h ( 3 ， 日( o ， h ( 1 ， h ( 2 ， h ( 3 ， 日 h 日 h 0 ， 1 ， 2 ， 3 ， 其中铲+ 2 t 0 ，t = m 2 4 m = o ，1 ，2 ，3 ，( 2 n 一1 ) ) 注意到 2 4 ：两丽万确而0 ，0 ，0 ，o ) ， n - - 2 2 n - 2 ：( o ，0 ，0 ，1 ，币翱， n - 2 扛m 2 4 = ( 再x 譬再x 0 ，0 ，0 ，0 ) 通过验证，我们有 2 1 + + + + 5 5 5 5 、lli d d 一 一 铲 2 2 ，l 一一 + 0 0 十 + + d 了j 一 扣0 盘 日日 扩h 2 2 2 2 + + + + ! 佃0 犯 口日日 ，一、_、i、j 、；、j 1 1 1 1 1 ，7 7 7 l 1 l 1 + + + + + + + + 回动砷钟 + + + + i q 0 日日日盯 1 l 1 l + + + + tb t n 0 犯 日日日日 兰州大学硕士学位论文 日( o ，t ) = h ( 1 ，t + 1 ) = h ( 2 ，t + 2 ) = h ( 3 ，t + 3 ) ， 4 ( 0 ，t + 3 ) = h ( 1 ，+ 2 ) = h ( 2 ，t + 1 ) = h ( 3 ，t ) ， ( 0 ，t + 1 ) = h ( 1 ，t ) = h ( 2 ，t + 3 ) = h ( 3 ，t + 2 ) ， 日( o ，t + 2 ) = h ( 1 ，t + 3 ) = h ( 2 ，t ) = h ( 3 , t + 1 ) ； h ( o ，t + 4 ) h ( 0 ，+ 7 ) 日( 0 ，t + 5 ) h ( 0 ，t + 6 ) 日( o ，t + 8 ) = h ( 1 ，t + 9 ) = h ( 2 ，t + 1 0 ) = h ( 3 ，t - f 1 1 ) h ( o ，t + 1 1 ) = 4 ( 1 ，t + 1 0 ) = ( 2 ，t + 9 ) 一h ( a ，t + 8 ) h ( 0 ，t + 9 ) = h ( 1 ，t + 8 ) = h ( 2 ，t + 1 1 ) = 日( 3 ，t 十1 0 ) h ( o ，t + l o ) = j 亨( 1 ，t + 1 1 ) = h ( 2 ，t + 8 ) = h ( 3 ，t + 9 ) h ( 0 ，t + 1 2 ) h ( 0 ，t + 1 5 ) 日( o ，t + 1 3 ) 日( 0 ，t + 1 4 ) 这样我们就证明了王k + 2 是妒+ 2 2 n + 2 阶分块双对称矩阵 由上述证明过程我们立即可以褥到 推论3 1 2 一个2 “扩阶的分块双对称矩阵由它的第一行( 列) 完全确定 关于b e n t 函数的谱矩阵，我们有 引理3 1 3 设，( o ) 是一个 元b e 耐函数研为，( 。) 的谱矩阵。n 2 一；r 日，是 个h a d a m a r d 矩阵 证明由于r ，所均为h a d a m a r d 矩阵，因此( 2 一；r h i ) ( 2 2 p n 正0 ) = 2 n ， 下面我们证明2 一；r 日，是一个士1 矩阵因为 计q 回动 十+ + + t t f 0 t 0 0 0 p 日h 日口 | l | | = = 砷砷计q + + + + t i 但0 0 0 h 日日日 | | = | | = 砷砷q 砷 + + + + t f t t 0 o o 0 胃日日日 印砷 l l l l + + 十+ t 4 b t t 3 3 3 3 ，l，l 日日日日 = | l i i = 曲勘句 1 1 1 1+ + + + t 0 0 日盯日日 = f | = = 砷砷动砷 l l l 1+ + + + t t f b t q o o o 日日日日 d c b n c d n 6 6 o d c 0 6 c d 式， 形f如有具都阵矩类 四述 上以所 兰州大学硕士学位论文 ( 一1 ) o o i ( 一r 耻l ( _ ( 一1 ) ( 2 n 叫。 f ( o oo ) 2 嘶：l州1 。0 ) i ： f ( ( 2 “一1 ) oo ) f ( 0 0 j ) f ( 1 0 j ) f ( 0 0 ( 2 “一1 ) ) f ( 1 0 ( 2 ”一1 ) ) f ( ( 2 ”一1 ) o j ) f ( ( 2 - 一1 ) o ( 2 “一1 ) ) 所以2 r 嘶的第t 行第j 列元素等于 2 “一12 ”一1 = ( 一1 ) 佑知心卿* 。 k = 0 x = 0 = ( 一1 ) 。( 一1 ) 7 惭十”。+ 8 予“+ 。 k = 0 $ = o 2 “一12 “一l = ( 一1 ) 蚶( 一1 ) m h 8 。l 。- $ j 七= oz = 0 2 ”一12 ”一l = ( 一1 ) 埘( 一1 ) 7 却。 t = 0y = 0 因为，( 。) 是一个b e n t i 函数，f l t b e n t i 磊数性质知，国o ) 也是一个b e n t l 函数 又因为b e n t n 数的谱矩阵是归一的，所以2 r 毋的第i 行第j 列元素等 于( 一1 ) 哪 4 - ( ! ! 一2 ：芋) 】2 9 = 4 - 2 n 于是2 2 玮日，是士1 矩阵 现在我们就可以给出b e n t 函数的结构性定理 定理3 1 4 设，( 茹) 是一个礼元b 肌t 函数，则毋满足下列条件 ( b 1 ) h ，是归一胁如m o r d 矩阵 ( 岛) 毋是分块双对称的且主次对角线相等的 ( b 3 ) 2 一gr 毋：是4 - 1 矩阵 反之，对于任意满足( b 1 ) ，( b 2 ) ，( b 3 ) 的与妒2 n 阶矩阵g ，存在唯一 的啦船赢t 函数，( # ) ，使得h s = g q ” o q 蕃! l 扎 牡 忡 咿申 ；咿 ；叫 1 1 l 忙 卜卜 卜 ”卜 h 严尸 r q l l；l；0 卜卜 卜 ” 耐恼 q 一 脚 d 一 脚 n 脚 l | 兰州大学硕士学位论文 证明定理的前半部分由引理3 3 ，3 1 1 ，3 1 3 立即可得 反之，设g 为一个满足( 曰1 ) ，( b 2 ) ，( b 3 ) 的2 ”2 “矩阵，并设 ， 9 0 0 g ：i 夕1 0 i ! 乳n 一1 ，o 勘= ( 鲫，g l o ，9 2 n - 1 ，o ) 7 ，解线性方程组 r x = 2 2 6 ， 扫于r 可逆，则方程组存在唯一解d = ( d o ，d t ，一，d 2 - - 1 ) t ，即 p d = 2 2 6 由于r 为2 n 阶h a d a n m r d 矩阵，因此 d = 2 一“r ( 2 ) = 2 一r 6 于是d 为矩阵2 1 r 的第一列，由( b 3 ) 知d 的所有分量均为土1 令( - - 1 ) c ；= 咄，i o ，l ，2 ”一t ，并设( t l ，如， 2 。一1 ) 为t 的二进制表示 令 2 “一1 f ( x 。，石l ，- 一，x 2 n - 1 ) = q ( 。l + i 1 + 1 ) ( 写2 + i 2 + 1 ) - ( z 。+ t 。+ 1 ) = 0 很显然，( 茹) 为n 元布尔函数，且，( z ) = c i ，i = 0 ，1 ，铲一1 由引理3 1 1 知，( g ) 的谱矩阵毋是一个2 ”2 ”阶的分块双对称矩阵对于e = 0 ，1 ，一，2 ”一1 ， 2 - f ( o o ) = 2 - 2 ( 一1 ) m ) 州 碍 = 2 - ；【( 一1 ) 。+ 0 + ( 一1 ) 。，+ 1 。+ - - + ( 一1 ) 。p 一，十( 2 “一1 ) 1 = 2 - 【d 0 ( 一1 ) o + d o ( 一1 ) 0 4 + + d 2 n 一1 ( 一1 ) 2 “一1 q 2 卯i 因此日f 与g 具有相同的第一行又因为g 也是一个2 n 扩阶的分块双对称矩阵，由 推论3 1 2 得日f = g 由于g 是一个h a d a m a r d 矩阵，所以_ ，f ) 是一个n 元b e n t 函数， 其唯一性是显然的 称满足定理3 1 4 条件( b 1 ) ，( 岛) ，( 岛) 的矩阵为曰一矩阵 定理3 1 4 告诉我们，n 元b e n t 函数完全由2 n 2 “阶日一矩阵确定定理的证明过 程也给出了由b 一矩阵构造b e n t 函数的方法因此要确定所有的n 元b e n t 函数，只需 要确定所有的2 ”2 “阶b 一矩阵 。 4莓羔；帅 兰州大学硕士学位论文 3 2 由n ：元b e n t 函数构造n + 2 元b e n t 函数 本节我们给出由2 n 2 - 阶b 一矩阵构造2 ”2 2 ”2 阶b 一矩阵的几种方法，也就 是由竹元b e n t 函数构造 + 2 元b e n t 函数的方法 首先我们给出两个分块双对称h a d a m a r d 矩阵同型的定义 定义3 1 s 若两个分块双对称h a d a m a r 旃巨阵的每个对应子块每一行含 有一1 的个数相同，则称这两个分块双对称h a d a m a r d 矩_ 阵同型 在前一节的讨论中，我们将求b e n t 函数的问题转化为求口一矩阵的问题下面我 们给出由2 n 2 n 阶b 一矩阵构造2 n + 2x2 n + 2 阶曰一矩阵的方法 定理3 1 6 设礼= 2 k ，a ，b ，ed 为2 ”x2 ”阶b 一矩阵且满足下列条件之一， ( 1 ) ab ，g ，d 中有三个相同，另一个是它的负矩阵 ( 2 ) a ，b ，g ，d 中有三个同型且仅有两个相同，另外两个互为负矩阵 则 岍= a a a 哪 4 a 2 00 0 、 c 埘= l 。0 4 舍2 。a 0 。0 l 0 00 4 a 2 因为a 是2 ”2 ”阶b 一矩阵，则a 2 = 2 “厶，4 a 2 = 2 ”+ 2 k 于是( 碍，十2 ) 2 = 驴+ 2 厶+ 2 点k + 2 的正交性显然上k 帕的其它情况同样可证 2 ) 不妨设 厂a b a b 、 一l a b a b - a b 口a i 一b ab a 则 、lll- d g b a g d a b 口a d g a 曰e d ，j。一 | | 2+ 兰州大学硕士学位论文 ，2 a 2 + 2 8 2 000 、 ( ) 2 _ i 。0 2 印。a 。 ：i 00 02 a 2 + 2 驴 因为a ，_ b 是2 7 2 n 阶b 一矩阵，所以a 2 = 2 n 厶，b 2 = 2 n 厶，则2 印+ 2 8 2 = = 2 ”+ 2 厶 ，于是( 口：+ 2 ) 2 = 妒+ 2 厶+ 2 ，辑。- i - 2 的正交性显然其它情况也同样可证 接下来分析归一性 若f k + 2 是归一的，则每一行一l 的个数为婴刍乎或者地竺：i 姬要 1 ) 若a ，曰，a d ，含有的一1 的个数为篓二唔坐，则因为在日。- i - 2 中a ，b ，c ，d 有一 个要取负，手是z k + 2 中一行( 列) 中一1 的个数为 s 学+ 学一一4 2 - + 2 v 面t 竿2 ) 若a ，b ，c ，d ，含有的一l 的个数为篓专匝，则因为在上k + 2 d p a ，b ，e ，d 有一 个要取负，于是王k + 2 中一行( 列) 中一1 的个数为 2 n 一西2 n + 伽 2 。 2 4 2 n 一2 、而1 2 n + 2 一v 管n + 2 22 最后我们验证这样构造的日；+ 2 满足( b 3 ) 为此，只需证明2 2 笋r + 2 王k + 2 是一 个4 - 1 矩阵即可 因为 所以 1 l11 b = i ：1 1 二，二； f 1 1 11 p n 十2 = p n 。p l 。p 1 = r 。b = i 笔- r p p n r t 另一另 = a a a - a ) p n r r r + 2 王k + 2 = 其它情况可类似证明 对于第二种情况 因为日。+ 2 有如下的三种类型，分别记为h l ，2 ，- s 即r + 2 巩+ 2 满足( 岛) 峨+ 2 的 不妨假设r a = 2 ；，r b 一2 ；厶其中r 三为2 n 2 n 阶的士1 矩阵则有 p n + 2 埔= 2 华 r + 2 现= 2 孚 p n + 2 凰= 2 半 孓 、 啊a a a a 诅a a a a 诅a a a a “ ，f，一、r 哦哦r r r 名名 r 以r 以 r r r r ，ji_i、 、 埘坷蟛搿耳埘擅 膏k k ，一 学 国 、 毋口a a 口谚a a a a 坩b a a 口齿 -，一 | | 巩 、，、i 坷a b a “b b a a 坩a b b a 培a a b a 书 ，rii-i、 = 醌 口以a b b a 诅ba 口b 诅 ，fi_ll | | 醌 、， t 屯廿毛r 三? 三r 五r 三t 三t 也 ，一 、 l 刁廿“ l t ? 二二叮r 三r r 也 ，fli_liil 、l t 可以屯 t t 也三r 叮二三 t t 五也 ，f 兰州大学硕士学位论文 显然r + 2 凰+ 。也满足( 玩) 其它情况由风+ 。的对称性可类似证明 综上所述，三k + 2 的确是一个2 “+ 2 2 n + 2 阶b 一矩阵 由2 n 2 n 阶b 一矩阵，我们可以构造出大量的妒+ 2 2 叶2 阶b 一矩阵，从而也可 以构造出大量的n + 2 元b e n t 函数 兰州大学硕士学位论文 第4 章四元b e n t 函数 本章的目的是利用前一章关于b e n t i 函数的结构定理，来确定所有的四 元b e n t 函数，并给出四元b e n t 函数的计数 4 1 二元b e n t 函数 (|b a d | ) c 旺 ( 三 + +曲 三) 旺 仨 + + + 一 为 三) 若将其依次记为h 2 1 ，三，奶3 ，点k ，- 1 2 5 ，- 2 6 ，t 2 7 ，王f 2 8 ，容易看出有岛5 = 一飓l ， h 2 6 = 一日船，月2 7 = 一丑j 3 2 8 = f 如4 容易验证上述8 个矩阵都满足( b 3 ) ，因而都是曰一矩阵于是2 2 2 2 阶b 一矩阵只 有这8 个利用定理3 1 4 的证明中的方法，可以求出它们对应的8 个b e n t 函数其代数 表达式依次为 ( ) = 茹l 嚣2 + z 1 + x 2 ， ，2 ) = x l x 2 + 1 ， 0 ) = ：g l x 2 + x 2 ， ) = x l x 2 ， ，5 ( ) = $ 1 9 2 + 峦l + 2 2 + 1 1 ，6 ( o ) = x l x 2 + 嚣l + 1 ， 卉( 茁) = z 1 x 2 + x 2 + 1 ， ，b ( o ) = x l x 2 + 1 这就是所有的二元b e n t 函数 、，、j + 一十+ 一+ 一 一 一十+ + + 一 一 一 + + + 一 一 一 一+ + + 一+ 一 一+ 一 ，t一，一、， + + 一+ 一 一+ 一 十+ + 一 一十 一十+ + + 一 一 一 + 一+ + 一+ 一 一 ，j一，i、 兰州大学硕士学位论文 4 2 四元b e n t 函数 4 2 四元b e n t 函数 由定理3 1 4 女1 1 ，要确定所有四元b e n t 函数，等价于确定所有的2 4 2 4 阶b 一矩阵 设日为一个2 4 2 4 阶b 一矩阵，则由定理3 1 1 知西具有如下形式 日= ( 量茎善霎) ( 4 - 2 ，4 2 ，4 - 2 ，士2 ) 或( 士4 ，0 ，o ，o ) 或( o ，4 - 4 ，0 ，o ) 或( o ，0 ，4 - 4 ，o ) 或( o ，0 ，0 ，4 - 4 ) 由于甘是归一的h a d a m a r d 矩阵，因此日的每一行( 列) 中含一l 的个数等于6 或1 0 ， 我们只需讨论一1 的个数等于6 的情况( 因为的每一行含l o + 一1 时，日仍为曰矩阵 且每一行含6 个1 ) ，此时口的每行的元素之和等于4 ，等价地，a + b + c + d 的每 一行元素也等于4 ，此时，a + b + a + d 的行向量具有形式 ( 2 ，2 ，2 ，一2 ) 或( 2 ，2 ，一2 ，2 ) 或( 2 ，一2 ，2 ，2 ) 或( 一2 ，2 ，2 ，2 ) 或者 ( 4 ，0 ，0 ，o ) 或( o ，4 ，o ，o ) 或( o ，0 ，4 ，o ) 或( o ，0 ，0 ，4 ) 因为口为分块双对称矩阵，要确定曰，只需确定h 的第一行的元素，也就是要确 定a ，b ，g ，d 的第一行的元素 ( 一) 如果a + b + g + d 的第一行的元素含有三个2 或2 ，不妨设其第一个行向 量为 ( 2 ，2 ，2 ，一2 ) ， 其它情况时类似的分三种情况讨论 ( 1 ) 若a ，县，c ，d 中某一个，不妨设为a 的筇行全为一1 ，则另两个一1 的分布要 么全在某一个中，不妨设为b 中，要么分布在两个中，不妨设为b ，g 中若是前者， g 和d 的第一行全为1 ，此时a + b + g + d 的第一行必然含有0 ，矛盾在后者情况 兰州大学硕士学位论文 下，d 的第一行全为l ，b ，g 中的1 必在最后一个位置。此时a + b + g + d 的第一个 行向量为 ( 一1 ，一1 ，一1 ，一1 ，1 ，1 ，1 ，一1 ，l ，l ，1 ，- 1 ，1 ，1 ，1 ，1 ) 由于a ，b ，gd 均为双对称矩阵，则日的第二个行向量为 虽然日的第一行与第二行不正交，与日为h a d a m a r d 矩_ 阵矛盾所以a ，b ，gd 四个 矩阵的第一行最多有三个一1 ( 2 ) 若a 的第一行有三个一l ，则由a 的双对称性知，a 必为一个2 2 2 2 阶b 一矩 阵，此时另三个必然是在b ，g ，d 中各一个否则b ，e ，d 中某一个的第一行必然含 有两个一i ，a + 丑+ a + d 的第一行必有零分量，得到矛盾由于b ，gd 均为双对称 矩阵，因此b ，g ，d 必然是同型的2 2x2 2 阶口一矩阵 ( 3 ) 若a 的第一行有两个一l ，则由上一种情况的讨论知，b ，e ，d 的第一行最多 有两个一1 ，且至少有一个，不妨设b 的第一行有两个一1 ，由于a ，b 均为双对称矩阵， 则a ，b 具有如下形式 l l 一 尬= i 。 l 十 l 手 t + l + 一尬2l 二 l 一 则剩余两个1 ，要么a ，d 各一个，要么全在某一个中如果是前者，那么g ，d 中 至少有一个，不妨设d 的第一行摄后一个分量为1 ，若c = d ，则a ，b 的第一个行向 量必然互为负向量，此时不论何种情况，日的前两行不正交与日是正交矩阵矛盾 若c d ，则ab 第一行最后一个分量全为1 ，且与g 第一行1 对应的位置全为1 ，此 时不论何种情况，都与日是正交矩阵矛盾如果是后者，那么a ，b ，ad 中有三个第 一行有两个一1 ，由双对称矩阵可知，这三个矩阵属于集合 士尬，+ m 2 ，土) ，另一个 不含1 ，必然等于矩阵 ，+ + + + 、 ：f + + + + i l + + + + j + + + + ( 二) 如果a + b + g + d 的第一行有三个o ，一个4 ，不妨设为( 4 ，0 ，0 ，0 ) ，此 时a ，b ，g ，d 的第一行的第一个分量全为1 若a ，b ，c ，d 中有两个第一行有三个一l ，不妨设为a ，日的第一行有三个一 l ，则g ，d 的第一行全为l ，此时日的前两行不正交，与日正交矛盾 、，十一一+ + 一 一+ + 一 一+ 一+一， ，、 = f | 岛 耻 啦 、，j、 + 一+ 一 一十一+ 一+ 一十+ 一+ 一 十一 + 一 一 十一 + 一+ 一+ + + 一 ，jliill、，iiiiii、 一一 j | +：一0_ + + 一 一 一 一 + + 一 一 + 一 一 兰州大学硕士学位论文 如果a ，b ，ad 中有一个第一行有三个一l ，不妨设为a 的第一行有三个1 若另 外三个一1 分布在两个矩阵中不论何种情况，均与日的正交性矛盾因此另三个一1 必 然分布在b ，e ，d 中各个，此时，b ，g d 为同型的2 2 2 2 阶b 一矩阵 如果a ，_ b ，g d 中每个矩阵的第一行至多有两个，1 ，则由f 3 ) 可知，此 时a ，b ，g ，d 必然有一个等于k ，另外三个属于集合 士m ，+ m 2 ，土 如