（基础数学专业论文）不同周期序列的四值相关分布.pdf

i i i ii iii l l i iii ii i illi 、t17 3 6 8 5 1 f o u r - v a l u e dc r o s sc o r r e l a t i o nd i s t r i b u t i o no f n o n b i n a r ys e q u e n c e sw i t hd i f f e r e n tp e r i o d s at h e s i ss u b m i t t e df o rt h ed e g r e eo fm a s t e r c a n d i d a t e ：y uh u i f e n g s u p e r v i s o r ：p r o f z e n gx i a n g y o n g h u b e i u n i v e r s i t y w u h a n ，c h i n a 湖北大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研 究所取得的研究成果除了文中特别加以标注引用的内容外，本论文 不包含任何其他个人或集体已经发表或撰写的成果作品对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明本人完 全意识到本声明的法律后果由本人承担 论文作者签名：弟犍幸 签名日期：训年，月7 日 学位论文使用授权说明 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本；学校有权保存并向国家有 关部门或机构送交论文的复印件和电子版，并提供目录检索与阅览服务；学校可 以允许采用影印、缩印、数字化或其它复制手段保存学位论文；在不以赢利为目 的的前提下，学校可以公开学位论文的部分或全部内容( 保密论文在解密后遵守 此规定) 作者签名： 指导教师签名： 日期：矽f - s ，7 日期：川s 7 旁 刍1 舀 趁，劢日镁曾 、口刀 中文摘要 摘要 伪随机序列在密码学和通信系统等领域有着广泛的应用互相关性质是伪随 机序列的一个重要指标当用作码分多址系统的地址码时，为容纳更多的用户和 减少用户之间的相互干扰，伪随机序列集应包含较多的序列，并具有较低的互相 关值m 序列是一种非常重要的伪随机序列，具有理想两值自相关性，它可以由 线性反馈移位寄存器生成组合m 序列是构造具有较好性质的伪随机序列集的 一个主要方法在此种构造方法下，序列集的相关分布与m 序列及其采样序列的 相关性有着紧密的联系因此研究m 序列及其采样序列的互相关性具有一定的 理论和应用价值 当采样d 满足( d ，p n 一1 ) 1 时，m 序列及其采样序列的周期不相等最 近，s e o ，k i m ，n o 和s h i n 对当正整数n 三0 ( m o d 4 ) 和p 为奇素数时的互相关性进 行了研究，得到了它i f 为四值相关其中采样d = ( 掣) 2 基于此，本文将 这个结果进行了横向推广当n 三2 ( m o d 4 ) 和p 三l ( m o d 4 ) 时，证明了该m 序列与其采样序列的相关值也为四值，通过计算相关函数的幂和式，构造了 关于频数的线性方程组，从而完全确定了其相关值的分布文中还指出了 当n 三2 ( m o d 4 ) 和p 三 l ( m o d 4 ) 时，其相关分布函数不为四值 关键词：m 序列；迹函数；互相关；d 采样 湖北人学硕士学位论文 a b s t r a c t p s e u d o r a n d o ms e q u e n c e sa l el a r g e l ya p p l i e di nc r y p t o g r a p h ys y s t e m sa n dc o m m u n i c a t i o n s t h ec r o s sc o r r e l a t i o ni sa ni m p o r t a n tc r i t e r i o no ft h e m u s e da st h e a d d r e s sc o d e so fc d m a ，t h es e to fp s e u d o r a n d o ms e q u e n c e sm u s ti n c l u d em o r es e q u e n c e sw i t hl o wc r o s sc o r r e l a t i o nv a l u ei no r d e rt oc o n t a i nt h em o r eu s e ra n dr e d u c e i n t e r f e r i n ge a c ho t h e rb e t w e e nt h eu s e r s m s e q u e n c ei sak i n do fi m p o r t a n tp s e u d o r a n d o ms e q u e n c e s ，w h i c hh a si d e a l - l e v e la u t o c o r r e l a t i o n n e yc a nb eg e n e r a t e db yt h e l i n e a lf e e d b a c ks h i f tr e g i s t e r ( l f s r ) ，a n dc o m b i n i n gm - s e q u e n c e si sam a i nm e t h o dt o o b t a i nt h en e ws e q u e n c e sw i t hg o o dr a n d o m n e s sp r o p e r t i e s i nt h i sw a y , t h ed i s t r i b u - t i o n so fc o r r e l a t i o n so ft h en e ws e q u e n c e sh a v ec l o s er e l a t i o n s h i pw i t h 仇一s e q u e n c e s a n di t sd e c i m a t e ds e q u e n c e s t h e r e f o r ei ti sq u i t ev a l u a b l et os t u d yt h ec r o s sc o r r e l a t i o n sb e t w e e nm s e q u e n c e sa n di t sd e c i m a t e ds e q u e n c e s i f ( d ，矿一1 ) 1 ，t h ep e r i o do fm s e q u e n c e si sn o te q u a lt oi t sd e c i m a t e ds e - q u e n c e r e c e n t l y , f o rap o s i t i v ei n t e g e rn 三o ( m o d4 ) a n da no d dp r i m ep ，s e o ，k i m ， n oa n ds h i np r o v e dt h a tp - a r ys e q u e n c ea n di t sd e c i m a t e ds e q u e n c e sh a v eaf o u r - v a l u e dc r o s s c o r r e l a t i o nf u n c t i o n ，w h e r et h ed e c i m a t i o nd = ( 芝咎) 2 b a s e do nt h e i r p r o o fm e t h o d ，t h es a m er e s u l ta l s oh o l d sf o rn 兰2 ( m o d4 ) a n dp 三l ( m o d4 ) ，t h e i r c r o s s c o r r e l a t i o nf u n c t i o ni sf o u r - v a l u e d l i n e a le q u a t i o n sa r ec o n s t r u c t e db yc a l c u l a t i n gt h ep o w e r - s u mo ft h ec o r r e l a t i o nf u n c t i o n ，t h e nt h ed i s t r i b u t i o no fc o r r e l a t i o ni s c o m p l e t e l yd e t e r m i n e d i ti sa l s op o i n t e dt h a tt h ec o r r e l a t i o nf u n c t i o ni sn o tf o u r - v a l u e d i nt h ea r t i c l ew h e n 佗三2 ( m o d 4 ) a n d p 三 ( m o d 4 ) k e yw o r d s ：m - s e q u e n c e s ；t r a c ef u n c t i o n ；c r o s s c o r r e l a t i o n ；d - d e c i m a t e d 目录 目录 摘要 i a b s t r a c t ( 英文摘要) 1 引言 1 1 1 研究背景 1 1 2 伪随机序列与m 序列 1 1 3 相关值2 1 4 论文的研究内容和组织结构 2 2 预备知识5 2 1 有限域理论5 2 2 迹函数及其性质6 2 3m 序列及相关函数7 3 互相关值的分布 9 3 1 互相关值的种类9 3 2 互相关值的分布1 1 4 结果与展望1 9 参考文献2 l 致谢2 5 i i i 1引言 1 1 研究背景 1引言 密码学泛指一切有关研究密码通信的学问，可以分为以下两个领域：如何达 到信息的秘密性，鉴别性的科学以及如何破解秘密系统，或伪造信息使密码系统 误以为真的科学，即密码编码学和密码分析学它们之间是相互依存相互支持、 密不可分的两个方面，共同促进密码学的发展然而密码学不仅仅只包含编码与 破译，随着密码学和通信技术的进一步发展，涌现了大量新概念和新技术，如散列 函数，数字签名，秘密共享，用户认证和电子投票等【1 2 t 3 4 1 伴随计算机网络通信 技术的发展和信息时代的到来，信息安全显得越来越重要同时给密码学提供了 前所未有的发展机遇 密码加密体制可以分为分组密码和序列密码( 又称流密码) 【5 1 序列密码是由 少量的随机密钥，通过硬件移位寄存器以及非线性变换等多层编码环节，产生变 化量大、复杂度高、随机性好的伪随机序列【6 】，利用简单的加密法把它与明文数 据串进行结合，从而实现对明文数据的加密的密码系统这种密码系统由于其易 操作性而备受重视所以，序列密码系统的安全性完全决定于它所产生的伪随机 序列的好坏s h a n n o n 于1 9 4 9 年证明了一次一密系统具有完善保密性1 7 ，从理论上 说明了序列密码系统的可行性 序列密码作为现代密码研究的一个重点和难点，广泛应用于雷达、声纳、同 步、信道估计和均衡、系统辩识、测试与测量、编码孔径成像等众多工程领域， 具体请参阅文献【5 ，8 ，9 ，1 0 ，所以对伪随序列设计进行研究具有重要理论价值和 广阔的应用前景一些技术上相关的参考文献包括【1 1 ，1 2 ，1 3 ，1 4 ，1 5 1 1 2 伪随机序列与m 一序列 伪随机序列是指具有某种随机特性的确定序列一方面它的结构是可以预 先确定的，并且可以重复的产生和复制；另一方面又具有某种随机特性它的应 用非常广泛，软件设计中它可在用于模拟实践环境工程中可用于模拟自然环 境、模拟干扰、模拟噪声等在通信中可用于扩频通信的关键技术，例如码分多 址( c d m a ) 技术在其他专业领域如测量测距、雷达导航、气象、空间探测、军 事和密码学中都有应用 伪随机序列因为具有随机特性，无法从一个已经产生的序列的特性中判断是 真随机序列还是伪随机序列，只能根据序列的产生办法来判断 1 6 ，1 7 1 伪随机序列 系列具有良好的随机性和接近于白噪声的相关函数，并且有预先的可确定性和可 湖北人学硕士学位论文 重复性 人工产生的序列不可能真正随机，所以一般得到的都是伪随机序列，基于 理论研究和实际的需要，又归纳出许多刻画序列伪随机性的指标，来区别序列 的实际应用意义【1 8 1 如序列的周期，线性复杂度，平衡性，自相关性和稳定性等 等【1 9 刹 m 序列是伪随机序列中应用最广的序列集之一它能够由线性反馈移位寄 存器( l f s r ) 来产生它以其极好的伪随机性而得到广大密码学专家和学者的青 睐特别是m 序列以其运算速度快和易于实现等特点而广泛应用现代密码体制 中具体表现为以下几个方面： ( 1 ) 平衡性：在每个周期内，等于0 的个数与等于1 的个数相接近，或者说它们 的个数之差的绝对值不超过1 ( 2 ) 最大周期：由相同个数的密钥所产生的序列中，m 序列的周期最大 ( 3 ) 自相关性：m 序列有理想二值自相关函数 现在发现一类较好性质的序列集就成为了研究的热点之一在上世纪中，相 继发现 女i g o l d 序列 2 h ，b e n t 序列【2 2 】，n o 序列【2 3 1 ，t n 序列c 2 4 】，小集合的k a s a m i 序 列【2 5 】和广义的大集合k a s a m i 序列闲并就这些特殊的序列集从是否具有较好随 机性质角度进行了分析，详见文献【2 7 ，2 8 ，2 9 ，3 0 ，3 l 】 1 3 相关值 随着通信容量的增长，频率资源利用也日益提高，这要求序列集必须具有很 高的防干扰能力于是乎相关值这一伪随机序列的一个重要指标，被广大学者 所重视一般地说，序列集的相关特性越好，系统的干扰就越小现在应用最广 的c d m a 系统的容量主要受限于干扰，具有软容量与大容量的特点因此研究序 列的互相关性具有非常重要的实际意义 3 2 , 3 3 , 3 4 ，3 5 , 3 6 这里所讨论的互相关值是关于m 序列及其采样序列之间的相关值当 采样序列的周期与m 序列的周期相等时，采样序列其实是与原m 一序列移位 等价，因此此时的相关值实质就是m 序列的自相关值，即为二值当采样序 列的周期与m 序列的周期不相等时，此类的研究结果比较多，具体请参阅文 献【3 7 ，3 8 ，3 9 ，4 0 ，4 1 1 4 论文的研究内容和组织结构 对于n 三0 ( m o d 4 ) 和p 为任意的奇素数，周期茭- d p n 一1 的p 元m 一序列s ( t ) 与 它的采样序列s ( d t + z ) 的相关值分布，s e o 等已经得到其为四值相关 4 h ，其 中d = ( 型) 2 ，0 l 出2而对于n 三2 ( m o d4 ) 和p 三3 ( m o d4 ) ，采样d 不 2 一 l引言 是一个n i h o 型，其相关值不为四值本文的主要内容是证明n 三2 ( m o d 4 ) 和p 三 l ( m o d4 ) 时其相关值为四值的，并给出了相关值分布 论文结构如下： 第1 章介绍了研究背景，伪随机序列与m 序列以及相关值的有关内容 第2 章为预备知识，介绍了有限域的相关内容、迹函数及其性质和序列的相 关知识 第3 章是本文的主要结果，大致可分为两个部分： 1 由相关函数a ( r ) 的定义出发，借助有限域的有关知识得到为四值的 2 构造频数的方程，分别求出每个频数文章中通过计算g ( 下) ，砰( 7 ) ， 7 - = or = 0 口，一2 四( 丁) 来完成 1 - - 0 第4 章给出了结果与展望 一3 2 预备知识 2 预备知识 本章第一节介绍了有限域的相关理论；第二节介绍了序列的相关理论；第三 节给出了伪随机序列的随机性指标 2 1 有限域理论 本节介绍有限域的相关知识 定义2 1 1 若域f 含有有限个元素，则称域f 为有限域，其中域中元素的个数称 为有限域f 的阶 最简单而又最基本的有限域是整数环z 模素数p 的剩余类域纠( p ) 为方便 起见，以后总用b 表示p 元有限域纠 ) 设f 是任意的一个域，如果f 的素域 同构于有理数域q ，则称f 的特征为0 ( 或) ，记为c h a r f = 0 ( 或c h a r f = o 。) ； 如果f 的素域同构于整数环z 模素数p 的剩余类域纠p ) ，则称f 的特征为p ， 记为c h a r f = p 域的特征还有另一种定义：若e 是域f 的单位元，对于任意正 整数佗，如果t g e 0 ，则称f 的特征为0 ( 或。o ) ，否则称满足n e = 0 的最小正整 数n 为f 的特征 推论2 1 1 【4 2 】任意域的特征或为素数，或为o o 定理2 1 1 【4 2 】设f 为有限域，则f 中恰有矿个元素这里c h a r f = p ，而n 是f 关 于域b 上的扩张次数 设f 是一个g 元有限域，记为乃，则巧= 日【o ) 为q 一1 阶乘法群， 由l a g r a n g e 定理知，对于任意口日，均有c q - 1 = 1 ，从而对于任意a 日， 均有a g = q 定理2 1 2 蜊有限域日的乘法群日是一个循环群设e 是域f 的扩域，q 0 ， 如果存在f 【z 】中的非零多项式，0 ) ，使得，( q ) = 0 ，则称q 是域f 的代数元，否 则称q 是域f 的超越元如果e 中的元素都是域f 的代数元，则称e 是f 的代数 扩张 定义2 1 2 设f 是有限域，如果q 为f 的代数元，则称使得，( q ) = 0 的首项系数 为1 的次数最低的多项式f ( x ) f k 】为o z 的极小多项式 由于域f 中的每个元素均为f 的代数元，因此，对f 中的任一元素q 而 言，其极小多项式为x q 一般而言，如果o l 为f 的代数元，则o t 的极小多项 式f ( x ) 一定为f ( z ) 中的不可约多项式 定义2 1 3 有限域日的乘法群露的生成元叫做b 的本原元，而本原元 一气 湖北人学硕士学位论文 在昂吲上的极小多项式叫做上的一个本原多项式 定理2 1 3 4 2 1 对于每个素数p 和每个整数n ，在昂中总存在佗次本原多项式， 从而也存在n 次不可约多项式 定理2 1 4 4 2 1 设f 为有限域，c h a f f = p ，则对f 中的任一元素o l ，有 ( z + a ) p = 矿+ 扩 由定理2 6 - i 以推知，若q 1 ，q 2 ，q 。是有限域f 中的元素，c h a r f = p ，则 对于任意的自然数仉恒有 特别地，v q 易，有o f = o e 2 2 迹函数及其性质 在这一节，给出了迹函数的定义以及它的基本性质 定义2 2 1 设q f = 耳n 且k = b ，定义在k 上的函数 如果k 是f 的素子域，那么就把t r f k 称之为q 的绝对迹函数，并简记 为t r e ( a ) 如果k = ，则迹函数可简记为t r y , ( q ) 在本文中需要用到迹函数的下列基本性质： ( 1 ) 嘿( q ) = t r y , ( ) ，比，歹= 0 ，1 ，2 ，； ( 2 ) t 嘿( a q + 够) = o t 嘿( q ) + b t 吆( p ) ，v a ，b 砀，比，p 哆； ( 3 ) 即跏，方程t r y , ( 。) = p 在彤中的解的个数恰有p n m 个； ( 4 ) v q 易，t r ( a ) = r ? ( r 象( a ) ) ； ( 5 ) 比哆，q 0 ，有( 一1 ) 打? ( ) = o ； z e f p , , ( 6 ) ( t r 篡( q ) ) p ，= t 礁( q 矿) ，地，j = 0 ，1 ，2 ，- 一 由性质( 2 ) 知，迹函数是从有限域b 。到b 。上的线性映射，它可以描述出所 有从有限域到跏上的线性变换，并且与基的选择无关 6 。：l = 矿 。汹 舻 q 础 - | 一m 扩 + 扩 +口 i i 口 k 吖 打 2 预备知识 特别的，当p = 2 时，易n 表示含有2 n 个元素的有限域，e 1 是而的乘法群 设正整数n ，k ，e 满足n = e k ，对z 尼n ，从易到忍* 的迹函数t r j ；( z ) 为 2 3m 序列及相关函数 定义2 3 1 设8 = 8 0 8 1 表示有限域b 上的序列，即8 晶若存在正整数n 满 足s 件n = 8 i ( i 0 ) ，则称序列8 为周期序列，n 称为该序列的周期所有可能周 期的最小值称为序列的最小周期，通常所指的序列的周期都是最小周期若序 列s 的周期为n ，则记该序列为8 = ( 8 0 ，8 1 ，8 n - 1 ) 定义2 3 2 设s = ( 8 0 ，8 1 ，8 n - 1 ) 为b 上周期为n 的序列，定义8 的线性复杂 度l c ( s ) 蔓3 满足下列关系式 c o s i + e l + 8 i 一1 + + e 1 8 i l ，i i n 的最小正整数1 其中c o = 1 ，c 1 ，c 2 ，c f 日，相应的多项式c ( x ) = 1 + c l x + + q 称为s 的极小多项式从l f s r 的观点看，c ( z ) 即为能够产生8 的l f s r 的 反馈多项式，而z 则为l f s r 的级数 定义2 3 3 设8 = 8 0 8 1 8 2 是一个p 元n 级线性移位寄存器序列，它适合线性递 归关系式： s 七+ c 1 8 k l + 0 2 s k 一2 + + c n s k n = 0 ，k 佗 其中0 如果8 的周期是矿一1 ，我们就说8 是最长p 元n 级线性移位寄存器 序列，简称仇序列如果q = 2 ，则称为二元m 序列 定义2 3 4 设s = 8 0 8 1 8 2 是日上的一个周期序列设d 是一个正整数，令s ( d ) = 8 0 8 d 8 2 d 我们称s ( d ) 是8 的一个采样，或称为8 的一个d 采样 定理2 3 1h 3 l 设8 是昂上任一给定的周期为矿一1 的m 一序列，d 为正整数， 若( d ，矿一1 ) = 1 ，则s ( d ) 也是周期为矿一1 的m - 序列 定理2 3 2 4 3 】设s 是昂上任一给定的周期为矿一1 的m - 序列，那么昂上任意周 期为矿一1 的m 序列皆与8 移位等价 定义2 3 5 设s = ( s 0 ，s 1 ，8 n - 1 ) 为b 上周期为n 的序列，记u = e 2 霄仃p 表 7 铲 z - i 御 = z 恤铷 = z 仡缸 r 湖北人学硕士学位论文 示p 次本原单位根，则8 的周期自相关函数定义为 若序列的自相关函数只取k 个不同的值，则称之为k 值自相关序列 一l 定理2 3 3 4 3 , 删设n i p 一1 ，并且a 为易的次本原单位根，a i = q 巧，i = j = o 0 ，1 ，2 ，若a = a o a l a 2 是昂上的序列，则它可以用迹函数分解表示为 特别地，如果a = a o a l a 2 是昂上的m 一序列，周期为矿一1 ，那么存在的 一个本原元素o t 和一个非零元，y 使得a i = t r ( t a i ) ，i = 0 ，1 ，2 ， 8 1 上一n 一 r 一 o 以一 + 以 渤 = r g 21 上o = 一u 口 叼 r m ：豆 = o 3 互相关值的分布 3 1 互相关值的种类 3互相关值的分布 下文中，若无特别指明，正整数n 三2 ( m o d 4 ) ，素数p 三1 ( m o d 4 ) ，采样d = ( 型) 2 令q 是易的本原元，由定理2 3 3 可知：周期为矿一1 的一个p 元m 序列可以表示成s ( t ) = t 7 i ( q 。) 因为g c d ( d ，矿一1 ) = 也2 ，则该m 序列 有出2个不同的采样序列，且可表示为s ( 出+ z ) = t r ? ( q 出州) ，其中0 z p n 2 + 1 2 令a = o l 。，b = q j ，则m 序列8 ( t ) 和它采样序列s ( d t + z ) 在7 - 移位上的互相 关函数为 p n - 2 p n - 2 a ( 1 - ) = w s ( t + r ) - s ( d t + 1 ) = u 打弛件7 _ q 出州) - u 矧一) ( 3 - 1 ) t = o皓0 z 譬 令p = q 肛+ 1 ) 2 ，y = a 2 ( p 7 2 一，则对于任意的正整数让，t ，以下式子都成 立：( p 2 u ) d = p 2 u ，( p ) d = ( 一1 ) ( p ”7 2 + 3 ) 4 p ，一= 1 ，甲严2 = ，y 一1 ，7 。一1 本节利用( 3 1 ) 计算p 一元m 序列s ( t ) 与它的采样序列s ( d t + 1 ) 的自相关值的 个数为书写的方便，记m = n 2 当p 是奇素数并且n 是偶数时， v x 哆，都有z = 剪，q 为本原元，0 歹p m ，y 砀v y 蹄，都存在一个非负整数t ( 0 t 矿一1 ) ，都满足y = q ( 矿+ 1 ) t 当n 三2 ( m o d 4 ) u p 三l ( m o d 4 ) 时，容易证明矿：q + 1 ) ( 学) 2 t ： q ( p m + 1 ) p m 。= q ( 矿+ 1 弦= y ，因此等式( 3 - 1 ) 可以表示为 p m q ( 丁) = u 打砌) - u 打 ( a n j y - b ( 8 ) 霉f j = o 可f n p ”p m ：ffu 竹( ( 和一k 审) v ) ：ffu r r ( 嘿( 列一6 口审) 训 一- - - 1 一 j - 0y e f 知j = oy e f 知 对于某个口，b 哆，任意的歹( o j 矿) ，都有 矿一1 ，如果t r 篡( o 一她肖) = 0 i 一1 ， 其他情况 一9 1 i 陌 由 k甜 n m m 打 u 吩 矿触 湖北人学硕士学位论文 因此要计算a ( 7 ) ，就必须先计算在 0 ，p m 】中有多少个整数歹满足 t 嚅( o 一b a d j ) = 0 引理3 1 1 若n 兰2 ( r o o d 4 ) ，p 兰l ( m o d 4 ) ，对讹，b 哆，0 jsp m ，关于j 的 方程礁( o 一b a d j ) = o 解的个数可能为0 ，1 ，2 ，3 个 证明由迹函数的定义 t 7 象( n 一b q d j ) = 口一6 q 亩+ a p ”q p ”j 一6 p m q p ”彩 因为o t p ”d d = ( 一1 ) ( p m + 1 ) j 2 q 肖，则t r 焉( a a j 一她亩) = o 等价于 严甜严j 一( b + ( 一1 ) + 1 ) j 2 b p * ) o e d j + o = 0 ( 3 2 ) ( 3 2 ) 式两边同乘q j 扩一q ( p ”一1 h 一( 6 + ( 一1 ) ( p “+ 1 ) j 2 6 p m ) q ( d 一1 ) 4 - q = 0 因为q ( d 一1 h = a 一1 ) j 4 q 杪一1 ) j 2 ，( q ( d 一1 ) j ) 2 = ( 一1 ) j a o 一1 h ，则( 3 - 2 ) 式等价于 ( 一1 ) j a r ( a ( d 一1 h ) 2 一( 6 + ( 一1 ) + 1 h 2 矿) n ( d 一1 h + 口= 0 那么当歹为奇数和偶数时，等式( 3 2 ) 分解为两个关于q ( d 一1 h 的二次方程因 此满足等式( 3 2 ) 的歹的个数不超过4 个下面将证明满足条件j 的个数不可能 为4 个采取反证法 假定( 3 2 ) 有四个解分别为q ( d 一1 ) 负，o f ( d - 1 ) j 2 ，a ( d ) j 3 ，o ( d - 1 ) j 4 ，并且歹1 ，力为 偶数，如，a 为奇数，j l 如，j 3 a ，则 q ( d 一1 b 1q ( d 一1 ) j 2 ：q ( d 一1 ) d 1 卜而) = a 1 一，“= q r ( 1 一矿“) q ( d - 1 ) j a o l ( d - 1 ) j 4 ：q ( d 一1 ) u 3 + a ) ：一n l p m ：口量+ r ( 1 一p “) 所以 ( d 一1 ) ( 歹1 + 歹2 ) 兰7 i ( 1 一p , n ) ( m o d ( p 一1 ) ) ( d - 1 ) ( j 3 + j 4 ) - - 竿+ 1 - ( 1 一矿) ( m o d ( p n 一1 ) ) 即 f 三一p m 丁+ 3 1 + 如) ( m 。d ( 矿+ 1 ) ) r 三一p 丁m + 3 ( j 3 - b j 4 ) ( m o d ( p n + 1 ) ) 1 0 3 互相关值的分佰 因为巨型2 兰1 ( m o d 2 ) ，所以这两个式子不能同时满足，假设不成立，命题得 注释3 1 1 引理3 1 1 证明的是n 兰2 ( m o d 4 ) 时的情形，当n 三2 ( m o d 4 ) ，p 三 3 ( m o d 4 ) 时，y d = 可并不对所有的y 砀都成立，则此时的q ( 7 ) 就不能够按照 上述方法计算 3 2 互相关值的分布 依照引理3 1 1 可得a ( 7 ) 一1 ，一1 士矿，一l + 矿) 记1 ，2 ，3 和4 分 别为- 1 ，- 1 - p m ，1 + 矿和一l + 妒出现的次数那么1 + n 2 + n 3 + n 4 = 矿一1 为了计算m ( 1 i 4 ) ，构造关于a p ) 的幂和式。q ( 7 - ) u = 1 ，2 ，3 ) r = 0 2 j - v b b n ，令a ( b ) = u 一。7 ( k d 、当b = 0 时，a ( o ) = p n 一1 ；当b 霉 m椰 彤时，a ( 6 ) = u 一岬( 妇嘶沪) = w - t r r ( t r 磊审) v ) = p i n k ( b ) 一0 m + 1 ) 其中k ( b ) 表示 0 ，p m 】内满足嘿( b a d 3 ) = 0 的整数j 的个数 因为t 7 象( 6 q 肖) = 6 q 面+ b p m o f p ”亩= ( 1 + ( 一1 ) 6 p m _ 1 ) 6 q 谚= 0 即1 + ( 一1 ) j b p ”- 1 = 0 令b = 旷q ，这里0 t 2 ( p m 1 ) ，0 i 乌寻，则 有 州，= 斧鞣： t i r l 一竹n 一 基于以上准备工作，ea ( 7 - ) 和研( 7 ) 的值就, - i d a 计算 v = 0r = 0 皇椰1 ，1p 甚2p ，。一j ，一a 2 _ = 2 2 2 + 1 ，若l 0 定理3 2 1 三吲丁卜气矿7 1 ，一；z 三o ： ，_ = 0 l ”+ 右z = u 证明由( 3 1 ) 式 ( 3 3 ) p “- 2 q ( 7 ) = u 叼( 七4 ) - u - - t r 4 u 岬( = 一a ( 6 ) r 2 0 a e z 蹄a e 由b = q 。，0 l 贮笋得a ( 6 ) = a ( q ) = p m k ( a 。) 一m + 1 ) ，则 专：a ( 7 ) ：一矿k ( q 。) + ( 矿+ 1 ) ：，一芝芋+ l ，若f o r - - - - o 吲7 ) - - 矿+ 矿“卜 荔篡 ip r 上 钼一u 湖北人学硕士学位论文 棚2 2 p n _ 2 晰，= 舻3 p 2 + 2 p 矿3 4 - - p n - - 矿4 p m - - 1 , 篆暑 证明由( 3 1 ) 式 p “一2 c ? o - ) = t = o 5 2u r r ( n z l 一嘲! ) - j a e 吩z l 譬 z 2 e 吩 2p n z 2 e 吩 u t r r ( 凹2 一咧) w - t r 擀f 托搠u 打 ( 口( z 1 倒) a e 蹄 o j - t r 6 ( z f + z d ) ) 一o j - t r 6 巧+ z d ) ) z l 知，x 2 = 一茹lz l ，z 2 哆 = 矿p n 一1 ) 一a 2 ( q 。) 其中0 2 世2由于a ( q ) = p m k ( a ) 一眇+ 1 ) ，所以 p 薹n - 2 珊，= 舻3 p 2 - + 2 p 易3 m - f 一- 妒4 f ”一_ 篆呈 p n - 2 想要计算四( 1 ) ，还需要以下引理 r = o 引理3 , 2 1f ：zhx d 是到自身的映射，有以下性质： ( 1 ) 如果，( z 1 ) = f ( x 2 ) ，, 贝qx 2 = z 1 ，y 。，0 t 芝丝2 ( 2 ) ，( f ) = 伊u ，p 2 u + 110 让 矿一1 ) ( 3 ) 对于某个u ( o u p m 一1 ) 得到 f - l ( ，2 缸) = 沪r l 唆 掣 ) ，厂1 ( 了2 州) ：【( 一1 ) 学p 2 u + 1 ，y t ) 由于引理3 2 1 的证明过程非常简单。这里就不多加详述 引理3 2 2 令o e 矿一1 ，对每一个i ( 1 is 学) ，都存在一组解e = e 1 和e = p m 一2 一e l ，满足l + p 2 8 + 1 = 矿q ，这里0 u 2 0 , m 一1 ) 证明假设1 + p 2 e l + 1 = 伊1 q ，那么1 + p 2 - 2 - e 1 ) + 1 = 伊1 一( 2 e l + 1 ) q 要注意的 是u l 一( 2 e 1 + 1 ) 是在m o d ( 2 p m 一2 ) 意义下的令e l ，e 2 是就同一个i 的两个不同 解，那么1 + p 2 8 - + 1 = 伊- q i ，1 + 伊。：+ 1 = 2 q ，可变形为 l + 1 + 3 2 e l + 1 ，2 e 2 - i - i) 2 一1 ) = ( 1 - - u 2 ) 2 ( p ”一1 ) = 1 1 2 3 互相关值的分布 化简得 即 p 2 e 2 + 1 一卢2 8 1 + 1 = p 2 ( 8 i + 8 2 + 1 ) ( 卢2 8 2 + 1 一p 2 8 l + 1 ) 所以e 2 = 矿一2 一e 1 因为任意的4 0 e p m 一1 ) ，都存在这样的i ( 1 e 芝竺2 、，满足1 + 伊8 + 1 = 伊a 所以对任意的i ( 1 e 华) 都存在组 解e = e 1 和e = p m 一2 一e l ，满足1 + 俨件1 = 矿 弓i 理3 2 3 令九( y ) = 1 + 矿一( 1 + 可) d ，y j ，则 ( 1 ) h ( y ) = 0 当且仅当y 珞 ( 2 ) 假设h ( y ) = 1 + 一( 1 + 可) d = 矿q ，其中0 t 2 ( 矿一1 ) ，0s i 2 竺2 则当i = 0 时方程h ( y ) = 0 解的个数为( 已m - 1 ) 4 ( p m - l - 3 ) 而对每一 个1 i 2 掣都有必2 个解 证明( 1 ) 对v y 珞，都有y d = y ，h ( y ) = l + 一( 1 + 秽) d = 1 + 可一( 1 + y ) = 0 下面接着证充分性因为d 是一个奇素数，所以 ( 一1 ) = 0 假设y 是 在略 一1 ) 上方程h ( y ) = 0 的一个解 如果y dg 蹄，( 1 + 可) d 砀，有= ( 1 + 可) d 一1 f r ，该式不成立如 果y d 砀，( 1 + y ) dg 砀，有( 1 + ) d = 1 + y d f , m ，该式不成立若y d ，( 1 + y ) dz 略，根据引理3 2 1 ，存在u 1 ，u 2 使得y d = p 2 - + 1 ，( 1 + 矽) d = p 2 u 2 + 1 因 此1 = ( 1 + 可) d 一= ( p 2 牡：一p 2 u ) 该式不成立所以y d ，( 1 + 耖) d 岛 假设1 + y d = ( 1 + 可) d = p 2 u ，由引理3 2 1 得y = ( p 轧一1 ) 7 。t = 伊u ，y 。z 一1 即俨u ( 7 。：一，y 2 - ) = l 一矿- 如果t l t 2 ，则有p 2 u = 辑即 1 = ( 俨“) 矿- 1 = ( 毒三睾) 矿一= 7 b ，且t 2 = t - = 。 这与t 1 t 2 相矛盾，即t 2 = t 1 = 0 ，且y = p 轧一1 ( 2 ) 若 ( 秒) 0 ，则 ( 秒) = 矿q ，其中0 t 2 ( p m 一1 ) 且0 i 笆型2 ( 2 1 ) 如果矿，( 1 + y ) d 易，那么h ( y ) = 1 + 一( 1 + 可) d 勋，所 以h ( y ) = 0 或p 知，0 u p m 一1 因为d 是奇数，y d ，( 1 + 可) d 等 价于可和1 + y 是略 一1 ) 中的平方元而总共有学个可使# tyn 1 + 是岛 一1 ) 中的平方元依据( 1 ) ，此时h ( y ) = 矿q 解的个数为学一妒一 2 ) ：( p r n - 1 ) ( p m - 3 ) 且i ：0 ( 2 2 ) 如果y d ，( 1 + y ) dgc 知当l + y d = 0 ，则h ( y ) = 一( 1 + 可) d = 1 3 湖北r 大学硕士学位论文 卢2 q + 1 ；当l 十y d 0 ，则h ( y ) = 1 + y d 一( 1 + 可) d = 伊q 且i 0 ( 2 2 一1 ) i = 0 我们先来证明当i = 0 时当且仅当1 + y d = 0 假设1 + y d = 卢2 “- 0 ，( 1 + y ) d = 卢2 u ：+ 1 ，则h ( y ) = 卢2 u - 一伊“。+ 1 = 伊，该式不成 立；若l + y d = 0 ，则( 1 + 可) dg 砀假设( 1 + 可) d 砀，由引理3 2 1 可 得( 1 + 剪) d = 胪，1 + y = 胪7 打因为y d = 一1 ，那么y = 一，y 幻也就得 到p 2 t 7 。l 一1 = - 7 幻，卢2 “= ( 1 一，y 。2 ) 一，y “所以1 = ( 1 7 。2 ) p ”一1 7 一( p 竹1 1 ) 。l = 一，y 2 。- 以2 ，该式也不成立 综合起来就是在该条件下方程h ( y ) = 伊解的个数等于满足y d 略且l + = 0 的y 的个数因为y = 一1 ，那么y = 一7 幻，0 t 2 2 坐2 因此解的个数 为p r 0 2 - - 1 ( 2 2 2 ) i 0 由( 2 - 2 1 ) 可得l + y d 0 那么将会存在u 1 和u 2 ，使得1 + = 卢2 m ，( 1 + 秒) d = 一p 2 t