（应用数学专业论文）bent序列集的研究与一类新的最优四相序列集的设计.pdf

摘要 具有低相关性的伪随机序列集在码分多址( c d m a ) 扩频通信系统和密码 系统中具有极其重要的作用作为c d m a 扩频通信系统中的扩频序列集，低 相关性的伪随机序列集能够成功降低来自同一信遭中其它用户的干扰；作为 流密码系统中的密钥流生成嚣或者作为数字签名算法中的伪随机数生成器， 低相关性的伪随机序列能够抵挡相关攻击( c r o s s - c o r r e l a t i o na t t a c k s ) 为了能够 抵抗b m 算法( b e r l e k a m p m a s s ya l g o r i t h m ) 的攻击，运用于上述系统中的伪随 机序列还应具有大的线性复杂度( l i n e a rc o m p l e x i t y , l i n e a rs p a n ) 迄今为止， 人们利用代数( 特别是有限域上的迹函数) 、编码、组合等数学工具对随机序 列集进行了研究，并取得了相当大的成就，已经提出了大量的构造方法，但是 这些方法都很单一，适用范围有限，同时对于由一些构造方法构造出酌序列 集。我n 还不能全面把握该序列集的伪随机性质。如求一些序列的线性复杂 度、确定一些序列集的相关值分布对于序列设计来说一直是个难点因此，针 对目前的一些伪随机序列的构造方法如何扩大它们适用范围，如何确定一些 序列集的相关值分布以及序列集的线性复杂度，如何提出新的构造方法，这些 都是十分有意义的研究课题 本文主要研究了以下问题。( 1 ) 系统研究了b e n t 序列集的构造方法，分 析了各种构造方法之间的联系，确定了b e n t 序列集的相关值分布；利用一类 b e n t 函数构造了一类b e n t 序列集，精确给出了每条序列的线性复杂度；( 2 ) 基于扩大b e n t 序列集容量的想法，本文还研究了不同的b e n t 序列集之间的 互相关性结果表明；在一定条件下，来自不同b e n t 序列集的两条b e n t 序列 之间的互相关性除在一个移位处的取值比较大外，其它移位处的取值不超过 b e n t 序列集的极大非平凡相关值，所的结果纠正了g o n g 给出的一个结果； ( 3 ) 研究了一类g w m 型函数的迹表示，并将所得结果运用于确定b e n t 序列的 线性复杂度；( 4 ) 基于两值自相关序列和四相最优序列，利用交织构造，本文 提出了一种构造四相最优序列集的新方法对于一类正整数m ，利用该方法所 构造的序列集具有参数( 2 “一1 ，2 ”十1 ，2 m + 1 ) ，不仅相关隆渐近达到了w e l c h 下界而且序列数目较大 关键词 二相序列，四相序列，b e n t 序列，自相关函数，互相关函数，线性复杂 度，迹变换，b e n t 函数，有限域 a b s t r a c t af a m i l yo fp s e u d o r a n d o ms e c i u e n c e sw i t hl o wc r o s s c o r e l a t i o n ，g o o dr a n d o m h e s s ，a n dl a r g el i n e a rs p a nh a si m p o r t a n ta p p l i c a t i o n s i nc o d e - d i v i s i o nm u l t i p l e a c c e s s ( c d m a ) c o m m u n i c a t i o n sa n dc r y p t o l o g y t h ep s e u d o r a n d o ms e q u e n c e sw i t h l o wc r o s s c o r r e l a t i o ne m p l o y e di nc d m ac o m m u n i c a t i o n sc a ns u c c e s s f u l l yc o m b a t i n t e r f e r e n c ef r o mt h eo t h e rl l s e r sw h os h a r eac o n l m o nc h a n n e l o nt h eo t h e rh a n d ， t h es e q u e n c e sw i t hl o wc r o s s c o r r e l a t i o ne n m p l o y e di ne i t h e rs t r e a mc i p e rc r y p t o s y s - t e r n sa sk e ys t r e a m 目e n e r a t o ro ri nd i g i t a ls i g n a t u r ea l g o r i t h m sa sp s e u d o r a n d o m n u m b e rg e n e r a t o r sc e , nr e s i s tc r o s s c o r r e l a t i o na t t a c k s i ti sw e l lk n o w nt h a tt h ep s e u d o r a n d o ms e q u e n c e se m p l o y e di nt h ea b o v et y p e so fa p p l i c a t i o n sm u s th a v el a r g e l i n e a rs p a n s ( a l s oc a l l e dl i n e a rc o m p l e x i t y ) i no r d e rt or e s i s ta t t a s k sf r o mt h ea p p i i c a - t i o no fb e r l e k a m p m a s s e ya l g o r i t h m u pt on o w ，t h ep s e u d o r a n d o ms e q u e n c e sh a v e b e e ne x t e n s i v e l yr e s e a r c h e db ym e a n so fa 【i g e b r a ，c o m b i n a t o r i c sa n dc o d i n gt h e o r y al o to fc o n s r u c t i o nm e t h o d sh a v eb e e np r o p o s e da n dm a n ys q e u e n c ef a m i l i e sw i t h d e s i r e dp r o p e r t i e sh a v eb e e ng e n e r a t e d h o w e v e r ，s o m eo ft h e s em e t h o d sa l w a y s h a v el i m i t a t i o n sw h e na p p l i e d i na d d t i o n ，n o ta l lt h ep r o p e r t i e so ft h es e q u e n c e s c o n s t r u c t e db ys o m ee x i s t e dm e t h o d sc a l lb ed e t e r m i n e d f o ri n s t a n c e ，i ti sa l w a y s ad i f f i c u l tp r o b l e r mt od e t e r m i n et h el i n e a rs p a na n dt h ec o r r e l a t i o nd i s t r i b u t i o no f s o m es e q u e n c ef a m i l i e s t h e r e f o r e ，h o wt oi m p r o v et h e s ee x i s t e dm o t h o d s ，h o wt o d e t e r m i n et h el i n e a rs p a na n dt h ec o r r e l a t i o nd i s t r i b u t i o n so fs o m es e q u e n c ef a r o - i l y ，h o wt op r o p o s ed e wm e t h o d st og e n e r a t eg o o ds e q u e n c ef a m i l i e s ，t h e s ea x ea l l m e a n i n g f u lr e s e a r c hp r o j e c t s i nt h ep r e s e n tp a p e r ，t h ef o l l o w i n gp r o b l e r m sh a v eb e e nr e s e a r c h e d ( 1 ) a l l t h ec o n s t r u c t i o nm e t h o d sf o rg e n e r a t i n gb e n ts e q u e n c e s8 ew e l ls t u d i e d ，t h er e l a - t i o n s h i pb e t w e e nt h e s em e t h o d sa r ea n a l y s e d t h ec o r r e l a t i o nd i s t r i b u t i o no fb e n t s e q u e n c ef a m i l yi sd e t e r m i n e d an e wc l a s so fb e n ts e q u e n c e sa r ep r o p o s e da n dt h e l i n e a rs p a no ft h e s es e q u e n c e si se x p l i c i t l yp r e s e n t e d ( 2 ) m o t i v a t e db ye n l a r g i n g t h ef a m i l ys i z eo fb e n ts e q u e n c ef a m i l y lt h ec o r r e l a t i o nb e t w e e nd i f f e r e n tb e n t8 e q u e n c ef a m i l i e s a r ed e t e r m i n e d t h er e s u l to fo u r sm o d i f y sar e s u l to fg o n g ( 3 ) i i 】 t h et r a c er e p r e s e n t a t i o no fkt y p eo f g m wf u n c t i o ni 8d e r i v e d t h e s er e s u l t sa r e h e l p f u lt od e t e r m i n et h et i u e rb p m 碰b e n ts e q u e n e e sp r o p o e di nt h i sp a p e r ( 4 ) b a s e d0 1 2t w o - l e v e la u t o c o r r e l a t i o ns e q u e n c e sa n do p t i m a lq u a d r i p h a s es e q u e n c e s ，a i l e wf a m i l yo fq u a d r i p h a s es e q u e n c e sf o rc d m ai sc o n s t r u c t e d k e yw o r d s b i n a r ys e q u e n c e s ，q u a d r a p h a s es e q u e n c e s ，b e n ts e q u e n c e s ，a t u o c o r r e l a - t i o n ，c r o s s c o r r e l a t i o n ，l i n e a rs p a n ，b e n tf u n c t i o n s ，t r a c et r a n s f o r m a t i o n ，f i n 址e f i e l d s 1 v 湖北大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或 集体已经发表或撰写过的作品或成果。对本文的研究做出重要贡献的个人和集体， 均已在文中以明确方式标明。本声明的法律后果由本人承担。 论文作者签名：夏求；史时间：o ? 。年二月坫日 学位论文使用授权说明 本人完全了解湖北大学关于收集、保存、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本； 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务 学校可以采用影印、缩印、数字化或其它复制手段保存论文； 在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。 ( 保密论文在解密后遵守此规定) 论文作者签名：疆j ri 乏 签名日期：d ”年5 月日 导师签名：幸蛉阂导师签名：享忑墨、j q 签名日期辟s 月巧自 一导论 具有低相关性的伪随机序列集在码分多址( c d m a ) 扩频通信系统和密码 系统中具有极其重要的作用作为( c d m a ) 扩频通信系统中的扩频序列集，低 相关性的伪随机序列集能够成功降低来自同一信道中其它用户的干扰；作为 流密码系统中的密钥流生成器或者作为数字签名算法中的伪随杌数生成器， 低相关性的伪随机序列能够抵挡相关攻击( c r o s s - c o r r e l a t i o na t t a c k s ) 为了能够 抵抗b - m 算法( b e r l e k a m p m a s s ya l g o r i t h m ) 的攻击，运用于上述系统中的伪 随机序列还应具有大的线性复杂度( l i n e a rc o m p l e x i t y , l i n e a rs p a n ) j 1 从应用 的角度来讲，一个理想的伪随机集应当具有以下性质：( 1 ) 序列平衡；( 2 ) 序 列数目多；( 3 ) 每条序列是二值自相关的；( 4 ) 两个不同序列的互相关函数处 处为零；( 5 ) 尽可能大的线性复杂度然而上述理想条件是目前任何实际序列 集所达不到的这是因为对于一个伪随机序列集来说，在其序列长度，序列数 目，自相关函数以及互相关函数之间最存在着一定的制约关系s i d n i k o v 界和 w e l c h 界常用来验证所设计出的伪随机序列集是否有最佳的相关特性【2 ，3 _ 对 ( c d m a ) 扩频通信来说，追求序列集的w e l c h 下界( 即周期为的二元序列 集，其相关函数的最大旁瓣值达到镢) 是伪随机序列集设计要达到的目标 一般来说，我们设计的随机序列集，应该具有以下性质：( 1 ) 平衡性；( 2 ) 低 相关特性t 能够达到或渐近达到s i d n i k o v 下界或w e l c h 下界；( 3 ) 大的线性复 杂度迄今为止，人们利用代数( 特别是有限域上的迹函数) 、编码、组合等数 学工具对随机序列集进行了研究，并取得了相当大的成就f 1 ，4 1 在二元序列集设计方面，除2 0 世纪6 0 年代就已提出的、工程技术人员熟 知的g o l d 序列、小集合的k a s a m i 序列和大集合的k a s a m i 序列 5 8 】( 这些序 列序列具有相关特性好，序列数目多，容易用硬件实现等优点，但是他们的线 性复杂度不高) 以外，扩频序列的研究在近几十年来又取得了长足发展1 9 8 2 年，j d o l s e n 等人构造出了具有最优相关特性、平衡特性以及大线性复杂度 的b e n t 序列【9 ，1 0 】；1 9 8 9 年，j - s n o 等人构造出具有最优相关特性的n o 序列 【1 1 1 ；1 9 9 4 年，b o s t a 和k u m a r 构造出了g o l d - l i k e 序列1 1 1 ，这是对g o l d 序列构 1 造的推广；1 9 9 5 年，k l u p p e r 利用有限域上的齐次函数构造了具有优异相关性 和高线性复杂度的d - f o r m 序列【1 3 1 ；同年，g o n g 提出了交织序列( i n t e r l e a v e d s e q u e n c e ) 的概念【1 4 1 ，随后。2 0 0 2 年，g o n g 叉利用两值自相关序列和交织构 造的方法成功的构造出了一大批具有低相关性和高线性复杂度的二元序列集 f 1 5 】；2 0 0 3 年，j s n o 等人利用广义迹变换推广了j do l s e n 等人的构造方 法，得到了广义b e n t 序列 16 j ，n o 的广义b e n t 序列不仅包含了b e n t 序列这 一特殊情况，而且在构造方法上有更大的自由度最近，z e n g 等人又推广了 小集合的k a s a m i 序列和大集合的k a s a m i 序列的构造，他们不仅确定了广义 小集合的k a s a m i 序列的线性复杂度而且解决了大集合的k a s a m i 序列的相关 分布这一二十多年以来的公开问题f 1 9 ，2 0 】这些重要结果的不断出现，表明 序列设计的研究具有广阔的前景 在四相序列设计方面，对于奇整数m ，1 9 9 0 年n o v o s a d 构造了类具有参数 ( 2 “一1 ，2 m ，2 “+ 1 ) 的四相最优序列集【2 1 】；随后，对于任意正整数m ，m a t s u f u j i 和i m g m u r a 利用实值b e n t 函数也构造了一类具有参数( 2 2 m 一1 ，2 m ，2 m + 1 ) 的 四相最优枣列集，并且给出了序列集的相关值分布i 嘲、有趣的是这两类四楣 序列的构造方法都源于二元b e n t 序列的构造这说明通过研究二元序列的构 造，能为我们提供构造四相序列的新方法 由于伪随机序列集在通信系统和密码系统中具有重要的应用，所以这些 年来一直是国际上的研究热点，并且已经形成了一门学科：序列设计虽然目 前已经有了大量的构造方法，但是这些方法都很单一，适用范围有限，同时对 于由一些构造方法构造出的序列集，我们还不能金面把握该序列集的性质， 如求一些序列的线性复杂度、确定一些序列集的相关值分布对于序列设计来 说一直是个难点因此，针对目前的一些伪随机序列的构造方法，如何扩大它 们适用范围，如何确定一些序列集的相关值分布以及序列集的线性复杂度， 如何提出新的构造方法，这些都是十分有意义的课题此外，伪随机序列的设 计同密码学的其他分支，如布尔函数、编码等具有紧密的联系，如何将这种联 系运用于序列设计也是一个值得研究的问豚本文的主要目的就是试图在以 上提及的这些方面做一些探讨 1 2 论文的主要结果及安排 本文的主要创新点- ( 1 ) 系统研究丁b e n t 序列的构造方法，指出了各种 构造之间的联系，确定了b e n t 序列集的相关值分布；利用一类b e n t 函数构 2 造了一类b e a t 序列集，精确给出了每条序列的线性复杂度；( 2 ) 本文还研究 了不同的b e n t 序列集之间的互相关性结果表明：在一定条件下，来自不同 b e n t 序列集的两条b e a t 序列之间的互相关性除在一个移位处的取值比较大 外，其它移位处的取值不超过b e n t 序列集的极大非平凡相关值，所得结果纠 正了g o n g 在文献【2 3 】中给出的一个结果；( 3 ) 研究了一类g w l v i 型函数的迹 表示，深化了文献1 2 4 】中的结果，并将所得结果运用于确定b e n t 序列的线性 复杂度；( 4 ) 基于两值自相关序列和四相最优序列，利用交织构造，本文提出 了一种构造四相最优序列集的新方法对于一类正整数m ，利用该方法所构造 的序列集具有参数( 2 2 m 一1 ，2 m - 4 - 1 ，2 m + 1 ) ，不仅相关性渐近达到了w e l c h 下界 而且序列数日较大 本篇论文的结构安排如下：在第二章，介绍有关序列设计的一般概念和代 数基础，主要包括相关函数的定义，s i d n i k o v 界和w e l s h 界，有限域上的迹函 数，b e n t 函数，以及f o u r i o r 变换和迹变换；第三章，对目前已有b e n t 序列 的构造加以研究，确定所有b e n t 序列集的相关值分布，然后研究不同的b e n t 序列集之间的互相关性；第四章，研究了一类g m w 型函数的迹表示，并利用 此结果确定了一类b e n t 序列集的线性复杂度；第五章，基于两值自相关序列 和四相最优序列，利用交织构造，提出了一种构造四相最优序列集的新方法 3 二序列设计的基本概念和代数基础 2 1 序列设计的基本概念 设p 为一素数，玮表示含有p 个元素的有限域再设g 为一正整数，z g 表示m o d t 的剩余整数环。设u 是一个q 次本原单位根，即u = e “凡q 定义2 1 设a = ( a o ，a l ，a n 1 ) 和b = ( b o ，b l ，b n 一1 ) 为z 口上两个 周期为的序列，即a i ，6 i z q ，i ；0 ，1 ，一1 ，它们的互相关函数r 。 ( r ) 定义为 r a 山( r ) = 山， i - - - - o 这里下标中的加法是在模的意义下相加的；若a = b ，那么称冗。b 为序 列a 的自相关函数，记为r 。( r ) 定义2 2z 。上的周期为的序列b = 慨) 称为具有两值自相关函数的 伪随机序列( 简称为两值自相关序列) ，如果对r 0 ( r o o d n ) ，其周期自相关 函数凰( ，) ：譬泸哳，- 1 定义2 3 设a = ( a o ，a l ，a n 一1 ) 为一个长度为的周期序列，其上的 左移算子上定义为 l ( a ) = ( 毗，a 2 ，一，n 一1 ，a o ) ， 对于任意的正整数i 0 ，定义l i ( a ) = l ( l 。1 ( a ) ) 定义2 4 设序列集s 含有条周期为_ 序列，即 5 = t s t l i = 1 ，2 ， f ) ，s i = ( s d o ) ，q ( 1 ) ，一，以( 一1 ) ) 序列集s 的最大非平凡相关值( 简称晟大相关值) 定义为 。；m “ ，r ) ， 其中 吼= m a x r s ；( 下) 0 下 ，1 i m ) ， r c = m a x 1 r ( r ) i 0 下 1 ，mj n ，( r , p ”一1 ) = 1 ， 序列 t 吁( a ) ) 譬i 2 和 t r p 【f 懦( 舻) r 】) 篓i 2 分别称为m 一序列【2 7 j 和g m w 序 列f 2 8 】，根据性质3 ) 和5 ) 可以证明它们的两值自相关性 2 3 b e n t 函数 本节介绍b ：和叼上的b e n t 函数 定义2 6 设，( 鲫是从叼到的一个逻辑函数，= e 2 ”f 1 ，p ，( 墨) 的 6 f o u r i e r 变换和其逆变换定义为 弛2 去三删吐2 m e 叼 2 去聂弛w a - x t , v _ x e 睇 其中互= ( l ，x 2 ，。) 叼，表示互的转置，_ x t b 表示点乘 定义2 7 设，( z ) 是从f 矿到的一个函数，u = e 2 ”凡p ，( 。) 的t r a c e 变换和其逆变换定义为 氕2 万1 。蠹删螂封，v 唧 删2 去。衲删m 晦 设扣，o l 2 ，a 。) 是n 在f p 上的一组基， 历，虎，风) 是其对偶基 【2 6 】，即 埘池舻庐”一，n 设= x i 卢i + + 。n 风，a = a l f l l + + a 。阮f 扣，贝0 打 ( a z ) = k l x l + ，+ a n $ 且选择一组基后睇n 可以等同地看成叼，故上述两种变换实际上是等价的 定义2 8 删设，( 墨) ( 或，( 。) ) 是从叼( 或睇n ) 到韵一个函数，若 氕玉) i = 1 ，v 玉f ；( 或1 ( a ) l = 1 ，v a 跏) 则称，( 篓) ( 或，( 。) ) 是昭( 或n ) 上的一个b e n t 函数 关于b e n t 函数的研究及构造，有大量的文献，可参考【2 9 3 2 7 3 1 引言 三b e n t 序列的研究与设计 具有良好伪随机特性和低相关性的周期序列对c d m a 通信与扩频通信系 统的性能具有重要作用扩频序列应具有的特性包括：尽量小的异相自相关 值和互相关值、好的平衡特性、较高的线性复杂度和足够多的序列数目等j do l s e n 等人在1 9 8 2 年首次将非线性函数运用于序列的构造，开创了一种构 造序列的新方法，构造出一种伪随机性质非常好的序列，即b e n t 函数序列 9 | b e n t 函数序列集是一类平衡的序列，其相关值达到了w e l c h 下界，其中的每一 条序列具有相同的线性复杂度而且通过选取适当的b e n t 函数可使线性复杂度 最大值的下界非常大【9 ，1 0 ，3 3 1 ；2 0 0 3 年，j s ，n o 等人利用广义迹变换推广了j d o l s e n 等人的构造方法，得到了g e n e r a l i z e db e n t 序列 1 6 】，n o 的g e n e r a l i z e d b e n t 序列不仅包含了b e n t 函数序列这一特殊情况，而且在构造方法上有更大 的自由度特剐，利用齐次b e n t 函数和n o 序列的l i f t i n g 思想【1 1 1 ，n o 还构 造出了b e n t - l i f t 序列，b e n t - l i f t 序列在保持优良相关性与平衡性的同时，与 b e n t 函数序列相比还可具有更高的线性复杂度随后，d o n g - j o o ns h i n 等人 又将b e n t - l i f t 序列作了推广，构造出了e x t e n db e n t 序列【3 4 】，使得b e n t l i f t 序 列成为了一种特殊的e x t e n db e n t 序列为了便于叙述，我们将b e n t 函数序 列、g e n e r a l i z e db e n t 序列、b e n t a i 托序列以及e x t e r l _ db e n t 序列统称为b e n t 序列文献f 9 ，1 6 ，3 4 在研究b e n t 序列时，仅给出了b e n t 序列相关函数的可能 取值，均未给出b e n t 序列的值分布的情况本文进一步研究了b e n t 序列的构 造，指出了各种构造之间的联系，证明了b e n t 类序列具有相同的值分配，明 确地给出了它们的值分配情况，结果表明b e n t 序列的值分布的情况与构造时 所选用的b e n t 函数无关同时，还研究了扩大b e n t 序列集容量的可能性，在 一定条件下确定了不同b e n t 序列集之间的互相关性最后，利用有限域上一 类新的b e n t 函数，构造出了一类新的b e n t 序列集，精确给出了它们的线性复 杂度 3 2 b e n t 序列集的各种构造及其相互关系 8 - 设n ，k ，e 为任意正整数，f 2 n 表示元素个数为2 ”的有限域，噤表示有 限域f 2 t 上的k 维向量空间 定义3 1 设，恒) 是从睡到f 2 的函数，称 m 卜去毒卜q 他h ”孔小扪 。1 为函数，( 尘) 的广义迹变换，其中互= ( z 1 ，z 2 ，一，z k ) ，= ( a 1 ，a 2 ，一，k ) 哗， ，表示兰和矗的点乘 当e = 1 时，广义迹变换实际上就是f o u r i e r 变换【9 ，3 3 】；当k = 1 时，广 义迹变换实际上就是迹变换【9 】 也称为h a d a m a r d 变换 1 ；一般地，通过选取 局c 在f 2 上的一组标准正交基，容易证明广义迹变换和f o u r i e r 变换时等价的 1 6 卜 根据定义，可以证明广义迹变换具有如下性质t ( i ) 逆变换： 。1 严k 去磊触。1 烨+ n _ 慨2 ( i i ) 乘法移位性质t 设ye 昆，若对任意的尘噤有，( 蓟= 9 ( 姓) ，则 于公) = ( 一1 玉) 任意的玉咕 ( 3 3 ) ( i i i ) 加法移位性质：设型瞪，若对任意的墨谍有，( 互) = g 也+ 墨) ，则 氕玉) = 贰蓟( 一1 ) 。叶瞌g “，任意的a 噔( 3 4 ) ( i v ) p a r s e v a l 恒等式l ( 一1 ) 他+ 9 ( 2 ) = 翘) 芽( 盘) ( 3 5 ) 嘻批岵 根据广义迹变换可以将b e n t 函数的定义【2 9 1 加以推广 定义3 2 设，( 星) 是从噤到f 2 的函数，若 氕玉) = 5 = 1 ，v 噔 则称，( 墨) 为噔上的b e n t 函数 9 根据定义3 2 易知：若，渔) 为畦上的b e n t 函数，则必有2 i e k 目前已 有很多b e n t 函数，见【1 8 】和f 2 9 3 2 】 定义3 3 1 1 3 设d 为一正整数，( d ，2 。一1 ) = 1 ，日( ) 是从马。一到毋e 的一 个函数，若对任意的z 马。* 和ye 见c ，坷有 h ( y x ) = v d h ( x ) 则称日( z ) 为一个d 一齐次函数 利用定义3 ，2 中的b e n t 函数，n o 等人成功地构造了大量的g e n e r a l i z e d b e n t 序列集下面来介绍g e n e r a l i z e db e a t 序列集和e x t e n d e db e n t 序列集的构 造 设n = 2 m = 2 e k ，n ，m ，e ，为正整数，8 为b 。的一个本原元，给定 d ，口昂马m 令从f 2 n 到噔的一个线性映射为 工( ) = ( t 曙( 历z ) ，t 曙( 岛。) ，t 嘻( 臃z ) ) ( 3 6 ) 其中 风，虎，风) 是马m 在f 2 e 上的一组基 g e n e r a l i z e db e n t 序列集的构造方法：任取选取从堪到屁的一个b e n t 函 数，定义序列集 s ；( ( t ) l q 易m ， s 玎( t ) =，( 工( 口。) ) 十t r ( ( 占盯+ 町) a ) ( 3 7 ) 称s 为g e n e r a l i z e db e n t 序列集 注( i ) 当e = 1 时，g c n e r a l i z e db e n t 序列集就变成了【9 】中b e n t 序列集； ( i i ) i i 当k = 1 时，则工( z ) = t 嘿( 触) ，其中p 路，( z ) 为玛m 上的一个b e n t 函数，这时的构造就是g o n g 在文献 1 ，2 3 】中给出的b e n t 构造；( i i i ) 注意这里 没有要求为偶数，而文献【1 6 中作了强制要求，实际上是不必要的，只须保 证，( 墨) 是从咭到毋的一个b e n t 函数即可 在介绍e x t e n d e db e n t 序列集之前，先介绍一类特殊的b e a t 函数( 1 6 ，3 4 】： 设，( 星) = 打 ( u ( 星) ) 是从咕到玛的一个b e n t 函数，其中t 注) 为噔到毋e 的 函数，且u 的每个单项式的次数d 满足以下性质一 1 0 存在正整数t ，使得de 分( r o o d2 。一1 ) ， ( 3 8 ) 即可设“( ) = 毗( 星) ，其中咄( 查) 的每一个单项式的次数d 满足( 3 8 ) 式，那 么可以将，( 苎) 改写成2 a 一齐次的b e n t 函数，6 ( 笙) ： od ，( 堡) = t r i ( u i ( 互) ) = t r i ( “尹1 扭) ) ；，“( 篓) ( 3 9 ) = 0 i = 0 e x t e n d e db e n t 序_ 歹h 集的构造方法 a 4 1 ：设| 8 是f 2 c 的一个本原元，任意 选取一个满足条件( 3 8 ) 的b e n t 函数，( 互) = t r f ( u ( 互) ) 和一两值自相关序列 6 ( t ) = t r f ( 卢毗) ，其中j 为指标集：，c 历1 定义序列 d e l e = s u ( t ) j q 尼m ) 唧( ) = 嵋 i t “( 三( 。) ) 2 一+ t 曙( ( 哺+ 5 a ) a 。) 2 6 】。) ( 3l o ) d e li = 0 称e 为e x t e n d e db e n t 序列集 注当b ( t ) = 埘( ) 时，e 叶( t ) 就是利用同一个b e n t 函数构造出的( t ) ； 当b ( t ) = r f ( 。) ，( r ，2 6 1 ) = 1 时，唧( t ) 就是文献【1 6 】中的b e n t 1 i f t 序列 3 3 b e n t 序列集相关值的分布 考虑有限域岛n 上的函数岛l ( z ) = ，( l ( $ ) ) + t r ( 0 + 5 q ) x ) 的迹变换，根 据p a r s e v a l 恒等式和乘法移位性质，可以将序列集s 相关性的计算转化成函 数s q ( z ) 和岛( 。”z ) 的逊变换的计算同样，序列集s 的平衡性的计算也可以 转化成函数如( z ) 的迹变换的计算根据这一思路，可以得到下面的结果，具 体的推导过程参见文献【l6 引理3 1 设s 为( 3 7 ) 中构造的g e n e r a l i z e db e r n 函数序列集，任取 卸( t ) ，即( d s ，令h ； + 缸f 兄m ) ，其中口，j 如( 3 7 ) 则 ( i ) 当o r 2 ”一1 时，1 日n d 7 h i 1 ，且( t ) 和即( t ) 的相关函数 。车? ，仙m m ( i + ，1i - 1 ， l h f l lv e v h = o , 且岛c 吼水，2 t = o 一u 岛。+ “+ 叫2 一。士卯，：- r 、。，一- i ：， 1 一l 士z 。，i1 0 i = 1 ( i i ) 当r = 0 时， r s 。c 咄m ，= 。- 。1 一, 。，：! ：，i ( i i i ) s 中任意一条序列时平衡的，即 ，( 如( t ) ) = ( 一1 ) s , k 。) = 一1 根据上述结果，文献【9 1 和【l6 在研究b e n t 序列时仅指出相关函数的可能 取值为 2 “一1 ，一1 ，一1 2 ”，一l + 2 ”) ，但并没有给出它们各自的分配情况，本 文的主要目的就是要给出b e n t 序列相关函数取值的具体分配情况，同时利用 有限域上的一类新的b e n t 函数，构造出了一类新的b e n t 序列集 为了确定b e n t 序列相关函数取值的具体分配情况，还需要下面的一些结 果 引理3 2 任取岛( 亡) ，也) s ，则 l ”一2 冗“( t ) ，晶，( 。) ( r ) = ，( 如( t ) ) j ( 马，( t ) ) ；1 f = o 证明根据相关函数的定义。容易证明下面的恒等式 2 “- 2 冗如( t ) ，即b ) 汀) = j ( 卸( t 】) j ( s ，( t ) ) f = 0 由引理3 1 知f ( 坼( t ) ) = j ( 即( t ) ) = 一1 ，从而原命题得证 引理3 3 设f 1 ，f 2 m ，定义函数 地如) = 锇， u 口十c 其中矾j 同( 3 1 2 ) 令g = ( 1 ，如) 旧0 ， i ，而n ) ，则 ( i ) ( 1 ，2 ) f 2 m 当且仅当l = 2 ( i i ) $ ( f 1 ，) 是从g 到f 2 n f 2 m 的一个一一映射 证明( i ) 设( f l ，已) = z 最m ，则衍+ f l = 。曲+ 。因为 l ，f ) 是f 2 。 在兄m 上的一组基，故有f 1 = z 如，d = 。5 ，从而有。= 1 ，l = 当 l = 岛，显 然( 1 ，白) ；1 f 2 m ( i i ) 若( 1 ，f 2 ) g ，由( 1 ) 知，( 1 ， 2 ) 玛n f 2 m 又因为f g i = lf 2 “ f 2 m i = 2 4 2 “有限，故只需证明( 白，) 是从g 到如n f 2 m 的一个单射 设( 1 ，已) ，( 昏岛) g ，假设( 1 ，已) = ( 巳岛) ，贝0 有 亭l 品户+ 善l 盯占+ g 盯5 = 矗白口2 + 矗盯d + g 盯臣 进一步可得 1 2 ( l 韪十f i ) 盯+ ( f 1 + 斟十屯十舀) d = 0 注意到f 1 岛+ 酯缸，( l + i + 如+ 琶) 6 f 如，且 l ，d 为岛n 在跏上的一组 基，从而有 亭，岛= 善i 。， i 。+ h = + 岛 由于( 乳) g ，故1 ，6 中必有一不为0 ，不妨设l 0 ，则 l ( 1 + 缸) = 矗( “+ 岛) = 1 9 + g = g ( 1 + f 2 ) ， 故 l = f i ，进而已= 岛，从而对( 1 ，f 2 ) ，( 氤f ；) g ，( 1 ，缸) = ( 氨琶) 当且仅 当( 轧如) = ( 岛) 引理3 4 设日= 缸+ i f 2 m ) 同引理3 1 对每一个r ：0 r 2 ”一1 ， 有 日n 日矿l = ：耋三袭耋：；竺： 进而，当r 跑遍集合 1 ，2 ，垆一2 ) 时， m 驸l = ri 二凳 证明设 日n c t 7 ，则存在轧2 最m ，使得 僻兰缸 即 羔蒜 慨m 因为1 r 2 n 一2 ，故0 7 1 ，对于给定的r ：1sr 2 n 一2 ，若扩场，根 据引理3 3 知( 3 1 1 ) 中的第2 式不可能成立，从而a 不存在，日n 日a r = o ； 若旷f 2 n f 2 m ，根据引理3 3 知t 存在唯一的( l ，已) g 使得( 3 1 1 ) 中的第 2 式成立，从而存在唯一得a h n 日a 7 ，即l h n h a 7 i - 1 ，再注意到，当r 跑 遍集合 1 ，2 ，一，2 “一2 ) 时，有2 一2 个f 使得d r f 2 。；有2 n 一2 m 个r 使 得。7 f 2 n 毋m ，即可得到引理中的结论 类似n o 在文献1 1 6 中定理1 9 的证明，可以证明下面的一个更一般的结 论 ；l 理3 5 设日l ( z ) 和h 2 ( x ) 是两个从f 2 ”到b t 的d 一齐次函数，其中 ( d ，2 8 1 ) = 1b ( ) = t r ( z ”) 和c ( t ) ；et r t ( 序j 2 ) 是两个两值自相关序列， 4 1 j j 定义序列 s b z ( t ) = 打h h d 。) ns q ( t ) ；t r ；( 旧( ) n ，扛1 ，2 讵1 j j 则对任意的0 r 2 n 一1 ，有 风b 、，。b ( 下) = 置。c l ，血( t ) 证明令t = 善昔，则对任意的o ! t 2 “一1 ，t 可唯一地表示成t = t l t + t 2 ，0 t l 2 e 一1 ，0s t 2 ( t ，贝0 r s h , s b ，( ，) ：基誉( 叫善埘“1 m f 纠。+ 驴垆“慨沁叫m t 2 = 0t 1 = 0 因为卢是马c 的本原元，( d ，2 8 1 ) = 1 ，故1 = 也为马t 的本原元对于 给定的r 和亡2 ，h 1 ( a 屯) ( 或醌( a 7 ) ) 或者为0 或者为7 的一个方幂为此，设 日l ( 驴) = 9 1 ( “，并约定g l ( 2 ) = 。如果1 ( 口t 2 ) = o ；设飓( o b + 7 ) = 俨( 。2 + ”， 并约定9 2 ( t 2 + f )