（基础数学专业论文）伪随机序列的相关特性和线性复杂度的研究.pdf

摘要 相关特性和线性复杂度是影响伪随机序列在通讯和密码系统中应用的两个 决定性因素为了有效地抵抗互相关攻击，在流密码系统中的密钥流序列应 具有低相关性质；另一方面，在c d m a 通信系统中具有低相关性的伪随机序 列还能成功地降低来自同一信道中其他使用者的干扰同时，为了抵抗基于 b e r l e k a m p - m m s e y 算法实施的攻击，保证数据的安全性，在各种应用环境中的 伪随机序列应具有大的线性复杂度因此，研究伪随机序列的相关性和线性复 杂度具有十分重要的意义 本文利用有限域的有关知识，系统地介绍了h i - 序列鼬m m i 序列，g m w 序列n 0 序列和t n 序列的自互相关函数和线性复杂度方面的结果，提出 了两类具有低相关特性的序列族，确定出它们的相关分布，并证明了其中类 序列族有较高的线性复杂度 关键词：伪随机序列；流密码；迹函数；相关特性i 线性复杂度 a b s t r a c t c o r r e l a t i o np r o p e r t ya n dl i n e a rs p a nmt w od e c i s i v ef a c t o r sw h i c hi n f l u c et h e a p p l i c a t i o n so fp s e u d o r a n d o ms e q m i nc o m m u n i c a t i o n sa n dc r y p t o g r a p b ys y s - t e m s t h eh e ys t r e a ms e q u e n c e si ns t r e a mc i p h e r ss h o u l dh a v el o wc r 0 8 s - c o r r e l a t i o n i no r d e rt or 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 ；o nt h eo t h e rs i d e ，t h es 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 nc a nr e d u c ei n t e r f e r e n c ef r o mo t h e ru s e r ss h a r i n gt h es r m ec o l - m u n i c a t i o nc h a n n e li nc o d e - d i v i s i o nm u l t i p l ea c c e s y s t e m s i no r d e rt or e s i s t b 前l e k 唧p _ m a s a e ya l g o r i t h ma t t a c ka n dg u a r a n t e et h ed a t a 8b a f t y ，t h eu s e dp s e u - d o r a n d o ms e q u e n c e si na l lk i n d so fa p p l i c a t i o n ss h o u l dh a v ea l s ol a r g el i n e a rs p a n s oi ti si m p o r t a n tt os t u d yo i lc o r r e l a t i o np r o p e r t ya n dl i n e ns p a no fp s e u d o r a n d o m s e q u e n c e s b yu s i n gt h et h e o r ya n dt h em o t h o do ff m i t ef i e l d ，w ei 址r o d u c e dc o m p l e t e l y t h ea u t o c z o s s - c o r r e l a t i o nf u n c t i o n so f 静s e q i i a 爝，k a 蛔血s e q u e i l c 4 皓，g m w 给 q u e n c e s ，n o8 e q u e n c e sa n dt n8 e q b n 髑，a n dc o n s t r u c t e dt w os e q u e n c e sh m i l i 铝 w i t h l o wc o r r e l a t i o n n l t h e r m o r e w ed e t e r m i n e dt h ed i s t r i b u t i o n o f t h e i rc o r r e l a t i o n v a l u e sa n dp r o v et h a tas e q u e n c e sf a m i l yh a v el a r g es p a n k e yw o r c k ：p s e u d o r a n d o ms e q u e n c e ；s t r e a mc i p h e r s ；t r a c ef u n c t i o n ；c o r m - l a t i o np r o p e r t y ；, l i n e a rs p a n 湖北大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承 担。 论文作者签名：田董妄 签名日期山0 年岁月曲日 学位论文使用授权说明 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本；学校有权保存并向国家有关 部门或机构递交论文的复印件和电子版，并提供目录检索与阅览服务；学校可 以采用影印、缩印、数字化或其它复制手段保存学位论文；在不以赢利为目的 前提下，学校可以公布学位论文的部分或全部内容。( 保密论文在解密后遵守 此规定) 论文作者签名：圆堇乓 签名日期：b d 年s 月暑p 日 导师签名： 签名日碰。 第一章绪论 1 1 前言 第一章绪论 在数据加密，扩频通信和码分多址( c d m a ) 通信系统【l 一羽中，伪随机序 列t e l 的摄关性很大程度上决定了系统的性能优劣程度为了抵抗相关性攻击，使 用的序列必须具有良好的低相关特性：为了抵抗b e r l e k a r a p m a s s y 算法攻击。 使用的序列必须具有较大的线性复杂度因此，研究伪随机序列的相关性和线性 复杂度对信息安全和通信系统具有十分重要的意义 在密钥流、扩频序列等伪随机序列的设计中，由于雎序列具有很好的伪随 机特性。人们通常采用m - 序列或其它随机统计特性好的基本序列通过非线性变 换来构造随机特性好的伪随机序列一般说来，这种非线性交换是通过迹函数来 实现迹函数表示不仅是研究序列生成的简便方法，也是研究序列的相关特性和 线性复杂度的有效方法，本文将就伪随机序列的相关特性和线性复杂度作一些具 体的研究 扩频序列的选取在码分多址( c d m a ) 通讯系统中极为重要在同步捕捉过 程中，要求扩频序列自相关特性好；同步码分系统中，要求自相关、互相关特性优 良；异步码分系统中，则要求同时具有好的自相关、互相关、混相关特性人们 运用近世代数理论和方法，找到了一批具有优异性能的代数型非线性扩频序列， 它们本质上都是m - 序列经过非线性变换得到的一个理想的扩频序列应该具 有如下性质：( 1 ) 序列平衡：( 2 ) 足够的序列数；( 3 ) 每个序列的自相关是一个尖 锐脉冲( 即它的自相关函数是二值的) ；( 4 ) 两个不同序列之问的互相关处处为 零；( 5 ) 尽可能大的线性复杂度。然而，上述理想条件是目前任何实际序歹i j 族蕨达 不到的。因为任何一个序列族，其自相关函数和互相关函数具有相互制约的关系 就扩频通信来说，追求序列族的w e l c h 下限( 即周期为的二元序列，其相关 函数的最大边峰值为、) 是扩频序列设计要达到的目标m 序列、m 序列和 g o l d 序列州是目前扩频通信中常用的扩频序列。它们具有序列平衡、相关特性 较好、序列数日较多、容易用硬件实现等优点但它们的线性复杂度不高，而且 相关特性均没达到w e l c h 下限直到8 0 年到后，入们利用有鼹域上迹函数理论构 造了众多具有随机特性好的高度非线性的序列族：k a s a m i 序列2 8 2 9s o l 、g m w 湖北大学硕士学位论文 序列 嚣，3 4 ，删、n o 序列i 髂】、b e n t 序列 9 , 1 0 , 1 1 , 1 2 l 、t n 序列【3 7 ，勰】等等它们的共同 特点：序列数日多，线性复杂度高，相关特性好 目前，大部分基于m - 序列而产生的伪随机序列的周期特性，自相关函数研 究得比较彻底，但在序列的互相关函数和线性复杂度方面，虽然取得了不少的结 果，可是，仍然没有一个完整地描述本篇论文的主要工作是研究有限域上序列密 码的相关特性和线性复杂度主要探讨的序列有：m - 序列、k a s a m i 序列、g m w 序列、n o 序列和t n 序列给出了两类具有低相关特性的序列族，确定出它们的 相关值及其分布情况，并证明了其中一类序列有较高的线性复杂度 1 2 本文的创新点及内容安排 本文的创新点主要有下面两点： 1 对住= 2 k ，为奇数，d = 2 1 # ，利用两个不同周期的m - 序列钟( ) 和 打 ( 。( 铲+ 1 ) 4 ) 的互相关函数，构造了一类新序列集s = 协( t ) i s t ( t ) = 钟( ) + 打f ( 口坝2 + 1 ) 啬2 ，这里口是f 2 的本原元，铂昂并证明这类序列集具有低 相关特性还确定出它的相关值分布 2 对于偶数t l ，利用垂型函数构造了一类周期为护一i 的序列集s ( r ) ，这里 r 与( 2 州2 1 ) 互素这类序列具有低相关特性，通过取适当的参数r ，还证明序列 集具有较大的线性复杂度特别地，当t l ；2 ( m o d 4 ) 时，完全确定了它的相关值分 布 本文按如下形式安捧各章节： 第二章为基本理论，介绍了有关有限域的知识和序列的相关特性及线性复杂 度方面的理论 第三章系统地介绍了目前已知的m - 序列与它的采样序列之问的互相关函 数，k a s a m i 序列、g m w 序列、级联g m w 序列、n o 序列和t n 序列的自互相 关函数和线性复杂度，同时构造了两类低相关序列集，并确定出它们的相关值的 分布情况对其中一类序列集，还证明了它具有较大的线性复杂度 第四章是结束语 2 第二章基本理论 2 1 有限域的代数结构 第二章基本理论 定义2 1 若域f 含有有限个元素，则称域f 为有限域，其中域中元素的个数 称为有限域f 的阶 最简单而又最基本的有限域是整数环z 模素数p 的剩余类域引( 力为方便 起见，以后总用b 表示p 元有限域z 定义2 2 设f 是任意的一个域，如果f 的素域同构于有理数域q ，则称f 的 特征为0 ( 或c o ) ，记为c h a r f = 0 ( 或c h a r f = ) ；如果f 的素域同构于整 数环z 模素数p 的剩余类域纠( 计，则称f 的特征为p 记为c h a f f = p 域特征的定义等价于：若e 是域f 的单位元，对于任意正整数n ，如果m 0 ， 则称f 的特征为0 ( 或o o ) ，否则称满足雠= 0 的最小正整数n 为f 的特征 结论2 1 若域f 的特征为p ，对于任意乜f o l o ，序列口，2 a ，( p 一 1 ) a ，妒中的元素两两互不相同；若域f 的特征为，序列口，2 a ，们，中 的元紊两两互不相同 结论2 2 任意域的特征或为素数，或为 定理2 1 1 s , 1 4 1 设f 为有限域，则f 中恰有矿个元素，这里c h a f f = p 而n 是f 关于其域昂的域的扩张次数 设f 是一个q 元有限域，记为日，则曰= 日0 为q 一1 阶乘法群，由 l a g r a n g e 定理知，对于任意o l 日，均有酽- 1 = 1 ，从而对于任意o l b ，均有 d 口= n 定理2 2 1 1 s a 4 1 有限域日的乘法群露是一个循环群设e 是域f 的扩 域，a o ，如果存在f 中的非零多项式，( 。) ，使得，( = 0 ，则称。是域f 的 代数元，否则称n 是域f 的超越元如果e 中的元素都是域f 的代数元，则称 e 是f 的代数扩张 定义2 3 设e 是f 的代数扩张，( z ) 是f 【叫中首项系数为1 的多项式，且 d e g ( z ) 1 ，如果满足下列条件： 第二章基本理论 对于任意的自然数巩恒有 特别地，毋，有矿= a 设f ( m ) = 口卜l 矿一1 + + 口l 。+ a o ，啦昂，口是方程，0 ) = 0 的根，则对 于一切自然数，l ，矿也是方程的根因为，( 动的次数有限，那么方程f c x ) = 0 的根也有限，共有n 个：a ，矿，矿“，这些根为，( z ) 的共轭根 2 2 限域上的迹，范函数理论 定义2 6 设域硌是的e 次扩张协= 酬，对于任意的口易，令 e - - i 螺( a ) = a + + + “= ， d - - - - o 称亡r 未( a ) 为域哆j 的迹函数 在序列研究中常用到迹函数的下列基本性质： ( 1 ) t r 嚣( 口) = t r 品( 矽) v 口乃- ，j = 0 ，1 ，2 ； ( 2 ) 亡，景( + 够) = d 打磊( + 托嚅( 回v a ，6 啊，v 口，p 移； ( 3 ) w j 扣，方程炼 ) = p 在彤中的解的个数恰有矿个； ( 4 ) v 口墨，钾( 口) = 打 ( 嬷( 口) ) ； ( 5 ) y a 墨，a 0 ，有e ( - - 1 ) ” ( 。曲= 0 ； z e 如 ( 6 ) ( t 嘿( n ) ) p ，= t r ：( 口一) ，v 口，j = 0 ，1 ，2 ， 由性质( 2 ) 知。迹函数是从有限域弓。到啊上的线性映射，而且它可以描 述出所有从有限域咖到勖上的线性变换，并且与基的选择无关 定理2 7 1 1 3 ，1 1 1 设耳是一个有限域，f 是蜀的一个有限扩张，只k 均可看作k 5 。：i i l 矿 嘲 ，嘲 湖北大学硕士学位论文 上的向量空间，则从f 到k 上的线性变换均可以表示为映射l z ，p f ，其中 卢( q ) = t r 盖( p o ) 、f 口f 并且，如果只7 只p 则有幻以。 定理2 8 8 3 , 1 , 1 设n i q “一1 ，并且q 为靠的次本原单位根，啦= b j ，l = 0 ，1 ，2 ，若 啦) 是日的序列，则此序列可以用迹函数分解 j - - - o 表示为 n - 1 峨= 乏二打r ( ) ，i = 0 ，l ，2 1 - - o 特别地，如果k 是蜀上的m 一序列，n ；矿一l ，那么存在f 的一个本 原元素d 和一个非零元7 使得m = t r ( ，y q ) ，l = 0 ，1 ，2 ， 定理2 8 表明：很多序列都可以经过某些迹函数的适当组合而成。从而启发 人们巧妙地组合一个特定的迹函数来得到多类性能优良的伪随机序列，如仇一序 列、g m w 序列、k a s a m i 序列、n o 序列、r 序列等一个序列用迹函数表 示后，将变得十分整洁，有利于对这些序列的深入分析 定义2 7 设域是跏的e 次扩张= e m ) ，对于任意的口珈，令 孵( 口) = a 矿矿一”= 口一1 ) 一1 ) 称：( a ) 为域昂的范函数 2 3 伪随机序列的相关函数和线性复杂度理论界 所谓序列的理论界( 或称理论限) 。就是序列的一些重要参数。如序列长 度、序列数目、序列自相关值以及互相关值等应满足一定的约束不等式理论界 对序列设计起指导作用，是评判序列优劣的重要指标本章将简要介绍伪随机序 列的相关函数和线性复杂度方面的理论知识 2 3 1 相关函数和w e l c h 界 一6 第二章基本理论 c d m a 系统分配给每个用户一个序列作为地址码，用户有效信号的获取依 赖于这些序列自身和序列间的相关函数下面分别给出它们的精确数学定义 定义2 8 设s 是由肘个周期为的序列集 s = “s ( t ) ，0 s t n l 1 0 ，l m 一1 ) s 中的序列 s ( t ) ) 和 s l ( t ) ，的周期互相关函数定义为 n - 1 j k j ( r ) = 靠( 力巩o + r ) 。， e 印 其中0 _ i l ，z m l ，0 7 i s n 一1 ，其中表示共轭复数。t 4 - r 中的加法运算 是模运算 对二元序列的情巧己，通常用0 表示1 ，l 表示一l 。因此此时 一1 取j ( n = ( 一1 ) 郇佃。卅 l = o 当 z ，风p ) 被称为周期互相关函数；当，i = f r h ( r ) 被称为周期自相 关函数，简写为取( r ) 称r h ( o ) 为t 8 o ) 的能量 序列集的最大边峰值磁。定义为 风一= m 麟 j 吼j ( r ) l ih z 或r 0 ) 理想的序列集要求集合容量m 尽可能的大( 即同一信道能够容纳的用户 多) ，最大边峰值风。要尽可能小( 其决定了通信质量) 然而，这两个条件互相制 约，尽可能的满足一个条件的同时必然会制约另外一个条件的满足这一点可以 从下面的w e l c h 界定理的推论可以看出 定理2 9 ( w e l c h 界) 阳设s 是一个由m 个周期为的序列组成的序列 集，s 中的任意序列s ( t ) 的周期自相关函数满足风( 0 ) = l ，令k 是任意的正整 7 湖北大学硕士学位论文 数，兄= m a x 引风( r ) l1 7 - o 则有下面的不等式 磕击 南_ 1 将s 每一条序列的任意左移f ( 1 7 n 一1 ) 位后的所得的序列添加到s 当中，易得下面的推论 推论2 1 设s 是一个由m 个周期为n 的序列组成的序列集，s 中的任意序 列s h ( t ) 的周期自相关函数满足r h ( o ) = 1 令k 是任意的正整数，则有下面的不 等式 ， 啦志隅。j 2 3 2 线性复杂度 在评价和设计序列时，人们一般使用的复杂度标准是线性复杂度，一是线性 复杂度比较容易理解；二是可以利用b e r l e k a m p m a s s e y 算法来快速地计算序 列的线性复杂度，因此线性复杂度的标准应用比较广泛一般我们提到的序列复 杂度都是对序列的线性复杂度而言的由下面我们讨论的线性复杂度的定义可 知，序列线性复杂度实际上描述了用线性反馈移位寄存器去恢复该序列的难易程 度理想伪随机序列的线性复杂度l s ( s ) = n 2 + 0 0 ) ，这里为序列s 的周期 定义2 9 1 1 e l 设s 是线性移位寄存器序列，定义8 的线性复杂度l s ( s ) 为能够 生成其的最短线性移位寄存器的级数 k e y 在文献【1 7 】中指出，若将s ( t ) 表示成的多项式，则其线性复杂度 l s ( s ) 等于该多项式中所包含的非0 单项式的数目 - 8 第三章几类伪随机序列的相关函数和线性复杂度 第三章几类伪随机序列的相关函数和线性复杂度 3 1 卅序列 廿序列的自相关是一个尖锐脉冲，即它的自相关函数值只有两个，但它的互 相关函数至今还没给出一个完整地描述，仅知道某些特定条件下的互相关函数 值事实上，对于周期相同的n 1 序列的互相关函数的研究，可以归纳为m - 序列与 其采样序列互相关函数的研究 定理3 1 设立是日上任一给定的周期为q | i l 的廿序列一是一整数，若 9 0 呱 矿一1 ) = l ，则f 也是周期为鼋| i 一1 的肚序列 定理3 2 设堡是目上任一给定的周期为矿一1 的d 扣序列，那么日上任一 周期为矿一l 的日i - 序列皆与亚莱一采样序列平移等价 人们利用上述定理求出了若干条件下的二元m 一序列与其采样序列的互相 关函数及其互相关函数值的分配目前已知的二元m 一序列与其采样序列的互相 关函数值和采样因子d 的情况如下： ( 1 ) 当d 耿下列值时m - 序列与其采样序列的互相关函数值是三位的： ( i ) d 一炉- i - l 其中州如地姊是奇数喇； ( 哟d 一俨一2 + 1 。其中州9 。如，耐是奇数嘲； ( 谢) d = 2 - 芦- i - 和“舭+ 1 ，其中玷善2 ( r n , 证4 ) c m ； ( i u ) d 一2 ，蚪1 + 禹其中n 三2 ( m o d 4 ) l 硼； 扣) d = 2 舾l m4 - 3 其中7 1 是奇数m l ； ( “) d 等掣p 1 ) 胆 1 - 群，卜1 ) ，一l 。其中n 暑1 ( m o d 4 ) 嘲； o , i od = 毋卜朔4 - 2 ( 扣1 ) ，一1 其中n 兰3 ( 删嘲 ( 2 ) 当d 取下列值时m - 序列与其采样序列的互相关函数值是四值的： a ) d = 2 , , 翻- t 一1 ，其中n 兰0 ( m 佣h ) 嘲； ( “) d = ( 2 l 卢+ 1 ) ( 2 一1 ) - i - 2 其中n 兰0 ( m 优“) 硼； n 2 ( 托) d ；2 i ，其中t 1 暑o ( 竹l c i d 4 ) ，0 m 2 ； ) d = 2 “2 + 2 们+ l ，其中n 誊0 ( r o o d 4 ) 且n 4 是奇数， ( 4 ) 当d 取下列值时, m - 序列与其采样序列的互相关函数值是六值的： ( 1 ) d = ( 2 “一1 ) + 2 ，其中他是偶数且s 住， 2 1 ( 2 - i 1 ) 2 ( m o d 3 ) f 衢捌； ( t ) d 当2 , t 2 2 吖4 + 1 ，其中n 暑o ( m 洲8 ) 0 甄i t e l - 序列是特性很好的伪随机序列，它序列甲街，有最好的自相关特性，可以 通过线性移位寄存器来实现，有低的互相关特性的优选序列关联集。它的优选对 互相关值已接近形e z 吐给出的相关特性的下限。但它也一个致命的弱点：线性复 杂度太小后来，人们发现用非线性变换可以提高1 1 1 - 序列的线性复杂度，同时又 不改变r r t 序列的其它良好特性如我们即将介绍的g m w 序列、n o 序列、 i n 序列等 3 2k a t m m i 序列 1 9 8 5 年，m k $ i m o n 和腿0 锄n 给出了二元小集合k a m m i 序列族的定 义： 定义文l 嗍设m ，侣是正整敦一= 2 m ，= 哥一1 ，t 一( ：2 - 一t ) ( 2 , - 一”，口 为琢的本原无令s 一 a d 0 1 0st 一1 ，ls s 沙 ，其中曩( t ) 一 亡r p ( 圣r ：( a ) + 乍矿q ，这里铂e 焉- 则称s 为二元( 小集台 ) g a t m i 序列 定理3 0 鲫二元小集合k a u m i 序列的互相关函数尼j ( r ) 卜2 i i i 一 1 ，- 1 2 , n l 由上述定理可知，二元小集合k a l m m i 序列的互相关函数达到了w e l c h 下 匣它是一类具有良好相关特性的码序列1 9 9 2 年，s c l i n 和l r k e m o 将二元小 集合k a 删瞳i 序列推广到p 元l 【a 蛐i 序列，并证明了如下结论： 定理3 4 1 删周期为矿一1 的p 元k a t m m 序列的互相关函数值及其分布情况 - t o 第三章 几类伪随机序列的相关函数和线性复杂度 为 f 一1 + 矿， 酬：卜j 【一l 一“，杪， 出现矿次， 出现矿( 矿一1 ) + p 一( p n 一2 ) ( 矿一1 1 ) 次， 出现矿( 矿一2 ) 次， 出现矿一1 ( 矿一2 ) 次，七= 1 ，2 ，p i 其中u = e 2 f v = t p 定义3 2 1 2 9 ln 为乃。的一个本原元，二元大集合k a s a m i 序列族伊定义如 下： s = 和( t ) ，盘2 h 易，6 & ，。) u 奴c o 蔷2 l ( 趴 其中 s 和( t ) = 打? ( + 一r ( 叫。+ 1 + 1 ) + t r 2 ( d a ( 2 n 7 。+ 1 ) ， 8 ( ( 力= t r ( o ( 矿7 砷1 + 1 ) + 亡r ? 2 ( e ( 铲一+ l ) 当行暑2 ( m o 枞) 时， 当n 兰o ( 删) 时 定理站嘲二元大集合k a s a m i 序列的互相关函数置j ( r ) - 2 2 n 2 1 ，一2 2 1 ，一1 ，2 呐一1 ，2 铲，2 一1 1 2 0 0 5 年，曾祥勇、刘青崇、胡磊等人在文献f 驯中对二元i s a m i 序列( 大 集合) 进行7 推广。并确定了它的相关函数值及其分布情况 定义3 3 阳设詹是一个正整数且满足当，l 兰2 ( , n o , t 4 ) 时g c d ( k ，n ) = 2 或当 n 誊0 ( m o d 4 ) 时9 c d ( k ，帕= 1 q 为j h 的一个本原元，二元序列族鲈定义如 下： 其中 驴= 8 咿( t ) ) 奢2 i v 翰，6 ，。 u 8 妇( i ) 容2 i ( i ，r ) ， s 哪( t ) = t r ( a + ，y a “2 + 1 ) + 打n ，2 ( 缸“2 n 届+ 1 ) ，【 = s 垦这 湖北大学硕士学位论文 这里 5 钾( t ) = t 砰( ( ( 2 - + 1 ) + 岬2 ( 似( 州2 + 1 ) t f l ， 忙i t , a , a 2 ， 当r l , 兰2 ( m o d a ) 时， 当n 兰o ( m o d 4 ) 时 = ( 1 ， 籀耋惟n - - 2 0 ( m o d a 埘) 时, 其咿。 定理3 6 当几兰2 ( m o a a ) 时，序列铲的互相关函数值及其分布情况为 是j o ) = 一1 + 2 “ 一1 - i + 2 - 2 - 1 2 ，i 2 - - 1 2 n l ? , + l 出现2 3 i 2 + 2 彬次。 出现2 吖2 + 1 f 2 “，2 一2 3 - 一3 + 2 孙一1 2 如2 1 + 2 “一2 1 ) 次， 出现f 2 4 - 一1 + 2 7 , 2 + 2 轨+ l 一2 缸 一2 3 ，l 2 + 1 一矿2 ) 3 次， 出现( 沙一1 + 咖一3 2 5 i ，2 + 2 2 ，冲1 - 3 2 翻24 - 2 ，i + 3 2 “2 ) 3 次 出现2 叫肄1 ( 铲一34 - 2 “，2 2 ) ( 2 鼽一1 ) ( 2 ，i ，抖1 一i ) 1 3 次 - 1 2 第三章 几类伪随机序列的相关函数和线性复杂度 定理3 7 当凡i0 ( m o d 4 ) 时，序列s 的互相关函数值及其分布情况为： 最j ( r ) = 一14 - 妒， 出现2 轨，2 + 2 | i 2 1 次， 一1 ，出现2 轨一2 饥，2 一2 加一1 + 3 2 3 ，i 2 1 5 2 ，i l 一铲辟+ 2 次， 一l + 2 - 2 一1 2 n 2 - 1 2 2 + 1 - 1 2 - 2 + 1 3 3g m w 序列 出现( 2 如一1 + 2 7 叫2 + 2 3 ，l + 1 2 如2 3 2 2 - 一5 2 缸胆+ 3 2 2 + 1 2 ) 3 次， 出现( 2 缸一1 + 2 3 - l 一2 5 - 2 + 2 + 2 2 1 2 瓤，2 艟+ 7 2 “一2 - 2 ) 3 次， 出现( 2 4 n 一2 + 3 2 7 “，2 3 2 轴一2 2 5 叫2 1 5 2 知一2 + 2 觚，2 2 + 5 2 n 一2 2 ，i 2 1 ) 3 次， 出现( 2 “一2 5 2 7 n 2 3 + 2 抽- 2 2 缸2 1 + 3 2 “一2 + 5 2 轨，2 - 2 3 2 ，i - 2 + 3 2 - 2 1 4 ) 3 次 3 3 1 二元g m v 4 序列 1 9 8 4 年，r a s c h o l t z 和l 1 己w c l c h 在文献 3 3 1 中给出了尼上的g m w 序列 的定义： 定义3 a 设1 r 2 - ，i 一1 ，m | n 并j j g c d ( r ，2 ，i 一1 ) = 1 ，口为昂的本原元， 则称下列定义的序列乳为g m w 序列： 巩= t r m f 打篇( o ) 】r ，0 s t 2 “一2 显然，当r = 1 时，= 毒r p 降嚅( 叠) 】= 打 ( 0 ) ，于是序列为二元m 序列，故 g m w 序列是m 一序列的一种推广形式 定理3 8 嘲g m w 序列的自相关函数为 晰，= p ；h ，1 老0 咧2 叫l 1 3 湖北大学硕士学位论文 定理3 9 a a g m w 序列的线性复杂度为l a ( s ) = m ( n m ) u 。其中u 为整数r 的二进制中1 的个数 由此可见g m w 序列与m 一序列具有一样，具有好的自相关特性，但在线性 复杂度方面要比m 一序列好得多而且可以根据具体情况的要求选择整数r 来达 到有效控制线性复杂度的目的 3 3 2p 元g m w 序列 1 9 9 2 年，a n t w e i l e 和b s n e r 在文献【3 4 1 中将二元g m w 序列推广到一般有 限域b 上，得到p 元g m w 序列： 定义3 5 设n = e m , o t 为易的本原元，r 是一个整数满足1sr 矿一2 和 g c d ( r , 矿一1 ) = 1 ，则称下列定义的序列鼠为p 元g m w 序列： a t = t r m t r y , c a ) l ，o s t 矿一2 这里蜮代替嵋 从形式上看，p 元g m w 序列和二元g m w 序列完全一样，其实当p = 2 时p 元g m w 序列就退化成常规的二元g m w 序列 定理3 1 0 f a a 设s t 是如上定义的p 元g m w 序列，由此引出复数序列： 啦= e 华0 2 a t 力，0 s t s 矿一2 则序列s t 的自相关函数为 。r 、p r - 2 ，f 矿一1 ，如果r 三o m o d ( 矿一1 ) 剐r ) - 善a t 坼r = p 二，萎薯：2 叫 脚 l 一1 ， h o 。 定理3 1 l a 4 1 如果r ：妻瑚严，1 usp - l ，0s 日蔓m 一1 并且当i j = 1 时，岛勺，那么p 元g m w 序列的线性复杂度为 蜊= m 垂( 咖1 ) 第三章几类伪随机序列的相关函数和线性复杂度 3 3 3 级联g m w 序列 将i n - 序列表示成两层迹函数并经过适当的乘方运算可以得到理想的伪随机 序列，根据迹函数的性质4 知i l l - 还可以表示成多层迹函数仿照双层迹函数的情 形。在每一层迹函数运算之前作一个适当的乘方运算，同样可以得到一类性能优 良的伪随机序列，利用这种思想a 1 【l a p p e r 等人在1 9 9 3 年提出了二元级联g m w 序列阻删 定义3 6 嘲设n 1 ，他，m 和k l ，k 2 ，岛一l 均是正整数且伽= 2 ，儡= 记i ， 儡，g o d ( k , ，毋一1 ) = 1 ，q 是的本原元，称由下式定义的二元序列8 5 为级联g m w 序列： s t = 蝶( 崤( 堞一。( ) ) 1 ) 不难看出，当f = 1 或2 时，级联g m w 序列就退化成m - 序列和g m w 序列 可见级联g m w 序列是它们的推广 定理3 1 2 1 3 珂级联g m w 序列的自相关函数是二值的。即 附) = 莩( 妒= q l - - i 篓j 到唧 t 丹l 定理3 1 3 【胬】如果对每个i ，1 s 一1 都有缸= 啦l + 衣1 并且0 啦 氏 啦和啦g c d ( 啦，如一啦) 为奇数，那么相应的级联g m w 序列的线性复杂度为 l s ( s ) = n l ) 2 ( n 3 ) 妒h ) 2 “ 这里承= 啦l ， = 1 ，z 定理3 1 4 1 蚓如果对每个 ，1 t f 一1 都有= ( 姥l + 啦1 ) ( 豇l + 程1 ) 并且0s 嘶 以 啦，0 c d i 啦，一幽 d 一q 和仉9 甜( 仉，玩一 啦) ，啦向以( 啦，q 一面) 均为奇数，那么相应的级联g m w 序列的线性复杂度为 工s ( s ) = n l ( 行2 ) 4 ( n 3 ) 4 2 ( n f ) 4 一1 1 5 湖北大学硕士学位论文 这里眼= q p _ l ，i = 1 ，z 3 4n o 序列 1 9 8 9 年d s n o 和p v k u m a r 在g m w 序列的基础上，研究开发了另一类具有 优异周期相关特性和大的线性复杂度的n o 序列 定义3 7 3 s j 设m ，n 是正整数m = 2 m ，n = 2 “一1 ，t = ( 2 ”一i ) ( 2 “一1 ) ，a 是艮的本原元，定义 s = & ( t ) j o t n 一1 ，1 is2 m ) 其中 最( t ) = t 曙i 亡r ：( o 产) + 仉o ，t 】， 这里的整数r 满足i r 2 ，i 一2 且g c d ( r , 2 ”一1 ) ；1 , 7 d i = 1 ，2 ，2 ”) 取遍 j 知中的所有元素这样得到的序列族s 称之为二元n o 序列族 显然，当r ；1 时；n o 序列就退化成小集合k a s a m i 序列；当乍兰o 时n o 序 列就退化成g m w 序列；当r z l ，= 0 时加序列就退化成m 序列 n o 序列具有良好的随机特性。具体如下： 定理3 1 5 【硼n o 序列的互相关函数和异相自相关函数都是三值的，即对任意 1 l ，j 2 ”和0 s r n 一1 ，只要 j 或者r 0 ，那么 n - i 忍j p ) = ( 一1 ) “+ “” 一2 ”一l ，一l ，2 “一l 设 r 为r 在二进制表示中”1 ”游程的数目，岛为第j 个”l ”游程的长度 f 一1 ，当非零m 使得护+ q i y + 1 在易中是不可约多项式时 矗。1l ，其它 1 6 第三章几类伪随机序列的相关函数和线性复杂度 最是二次方程护+ + 1 = 0 的一个属于集合 q = 1 1 ，+ 1 1 舻+ ”，q 护- l 一1 ) + n ，矿，舻一n ，扩1 一1 的根； a 由下面关系确定：当c = 一1 时，a i 满足盈= o m ( 妒+ 1 ) ；当岛= 1 时，a 满足 孟= 铲哥一” 又设m ；g a ( a _ ，2 ”+ 日) 于是有 定理3 1 6 【删n o 序列的线性复杂度为 婴r2lj+l-1-2lsci) 【譬等j ) = 价n 【锹j ) j = 其中表示不超过的整数 3 5t n 序列 1 9 9 5 年，k l a p p e r 提出了由具有某些特性的齐次函数( 小型函数) 构造低 相关序列( 正型序列) 的方法。这种方法包古了n o 序列作为其特例，因此是 a j o 序列的推广根据这种思想。k l a 仰e r 提出了t n 序列在一些情况下，t n 序列不仅具有最优的低相关特性，而且具有高的线性复杂度基于同样的思想， 单p 嚣随后提出了相关特性较差一些，但集合比较大、线性复杂度也比较高的 大集合t n 序列 s t , a a l 最近，曾样勇，胡磊和刘青祟等对t n 序列进行了推广，推 广后的1 n 序列具有最优的低相关特性和更高的线性复杂度嗍 3 5 1d - 型函数和出型序列 下面给出垂型函数和垂型序列的精确定义 定义3 8 吲设日( 卫) 是有限域昂上的函数，d 是一个正整数，并且g c d ( d ，q 一 1 ) = 1 ，若对任意的z 野和s ，日有 日( g ) ：；9 日( z ) ， 1 7 一 湖北大学硕士学位论文 则称日( z ) 为从昏到最上的d - 型函数 定义3 9 m 设h ( x ) 为从吩到日向= 矿。) 上的d - 型函数，整数r 满足 g c d ( r ，g 一1 ) = 1 , t r r r ( ) 是从日到昂上的迹函数，口是日n 的本原元，称 s = s ( t ) = n r ( ( 日( a 。) ) 7 ) ) 为一条出型序列 运用d _ 型序列的概念构造出型序列的关键在于：( 1 ) 找到一些好的出型函 数，使得所构造出来的序列集不仅具有较大的集合容量，而且具有低的相关性； ( 2 ) 另一个关键问题是如何决定它们的相关值分布和线性复杂度 关于d 型痔列相关值分布有下面的定理 定理3 1 7 设e22 ，佗= e k ，t = ( 2 ，i 一1 ) ( 一1 ) ，1 r d 2 。一1 ， g c d ( r d ，于一1 ) = 1 令o t 和，y = a d r 分别表示易和见t 本原元设序列 危) 一 蜡( 7 “) 盘2 具有两值自相关性，其中j 是一个指标集，矗( z ) ，| l f 1 0 ) 是 从昂到b 。的d - 型函数令s ( 7 ) = 8 9 ，s 旺。 ，其中8 = s ，) 啬2 ， s ，( t ) = 亡r ；( 陋( 0 ) j “) 则s ( ) 和s ( 1 ) 具有相同的相关值分布 t ， 证：对任意的0 s t ，r 2 ，i 一2 ，将t 和f 分别写成t = t t i + 颤和r = t n + 见 的形式，其中0 s h ，n s2 。一2 ，0 岛，死t 一1 对i 和t ，定义 io o ，i f 五( a 9 ) = 0 ， 2 i 删，i f ，t ( 扩) ：r 记俨；0 ，并且对任意的整数c 规定o o + c s 因为五( 茹) 是出型函数，因此 8 ( t ) + 妒0 + 7 - ) = 埘( m ( 口) 】“) + 嘶( 防( n ”) 】”) = 域( b 扪t 五( 驴) 1 “) + 嘶( 【口四 蜘办( 驴h ) 】”) = ： ( ，( t l - - q b ) + ( ，y 7 ( l + n + e j q + 它) ) ， 1 8 第三章几类伪随机序列的相关函数和线性复杂度 并且s ，和妒的相关函数为 其中 t - 2 ( 一1 ) 一( t ) + t 卅 t - 12 e - 2 ( 一1 ) ( t l 恫吩) + “ ”f l h 如忉) 挈= “= o ee ( 如，i ，j ，n ，r 2 ) ， h = m 9 f 厶i 、= 2 - 2 ( _ 1 _ i h ( 7 1 r ( 1 l 佃她) + t l 蜘+ 勺2 + 口) e ( 如，l ，j ，1 ，1 2 ) =e 、， q q 叫她) + h u q 一1 1 扭+ 口n t l 卸 因为 ( r ) ) 具有两值自相关性，并且g c d ( r , 2 一1 ) = 1 ，所以有 e ( 如，i ，j ，7 l ，恐) ；2 e 一1 或一1 。并且e ( 如，i ，j ，n ，您) = 铲一1 当且仅当 - f t 乜= p 均，乜呐令n ( i ，五n ，1 2 ) 表示使得铲出= p 均如+ ，并且在大于 或等于0 夺于或等于t 一1 的范围内的t 的个数于是 j ( r ) = ( 2 。一1 ) ( ，五n ，n ) 一( t l v ( i ，鼻1 1 ，死) ) = t n ( i ， 7