（基础数学专业论文）二元序列线性复杂度的研究.pdf

中文摘要 摘要 伪随机序列在密码学和通信系统等领域中应用较为广泛线性复杂度和相关 性质是影响伪随机序列应用的两个重要因素为了抵抗基于b e r l e k a m p m a s s e y 算 法实施的攻击，保证数据的安伞件，存某些应用环境中要求伪随机序列具有大的 线性复杂度为了有效抵抗互相关攻击，应用在流密码系统中的密钥流序列应具 有低相关性质；在c d m a 通信系统巾具有低相关性的伪随机序列能成功地降低 来自同一信道中其他使用者的干扰因此，研究伪随机序列的线性复杂度和相关 性质具有十分重要的意义 本文构造了两类伪随机二元序列。一类具有大的线性复杂度，一类具有理 想自相关性质一方面，利用新的d 一齐次函数，运用数论和有限域的相关知识， 构造了一类周期为2 n l 的序列s t 这里7 , 为偶数，r 与2 n 2 一l 互素通过选 取适当的参数7 ，证明了s ( r ) 具有较大的线性复杂度，并且精确地给出了线性复 杂度的大小我们所构造的这类序列，它们的线性复杂度比g o l d 序列、小集合 的k a s a m i 序列、g o l d 1 i k e 序列以及u d a y a 序列的线性复杂度大很多另一方面， 从有限域易。上的2 对1 映射出发，构造了一类周期为2 m 一1 的具有平衡性的二 元序列，利用w a l s h 变换技巧，证明了这类序列具有理想自相关性质 关键词：迹函数；线性复杂度；平衡性；理想自相关序列；p a r s e v a l 等式；2 对l 映射 湖北大学硕上学位论文 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 ee x t e n s i v 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 s ，c o m m u n i c a t i o n sa n ds oo n l i n e a ls p a na n dc o r r e l a t i o np r o p e r t ya l et w oi m p o r t a n tf a c t o r s w h i c ha f f e c tt h ea p p l i c a t i o no fp s e u d o r a n d o ms e q u e n c e s i no r d e rt or e s i s tt h ea t t a c k b a s e do nb e r l e k l a m p m a s s e ya l g o r i t h ma n dg u a r a n t e et h ed a t a ss a f e t y ，p s e u d o r a n d o m s e q u e n c e si ns o m ea p p l i c a t i o n ss h o u l dh a v el a r g el i n e a ls p a n t h ek 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 rs h o u l ds a t i s f yl o wc r o s s c o r r e l a t i o nt or e s i s tc r o s s c o r r e l a t i o n a t t a c k s ；s e q u e n c e sw i t hl o wc r o s s c o r r e 1 a t i o nc a na l s or e d u c ei n t e r f e r e n c ef r o mo t h e r u s e r ss h a r i n gt h es a m ec o m m u n i c a t i o nc h a n n e li nc d m as y s t e m s a b o v ea l l ，i ti s s i g n i f i c a n tt os t u d yo nt h el i n e a rs p a na n dc o r r e l a t i o np r o p e r t yo fp s e u d o r a n d o ms e q u e n c e s w ec o n s t r u c t e dt w of a m i l i e so fp s e u d o r a n d o ms e q u e n c e si nt h i sp a p e r o n ef a m i l y h a sl a r g el i n e a ls p a n ，a n dt h eo t h e rf a m i l yh a si d e a la u t o c o r r e l a t i o n u s i n gan e w d f o r mf u n c t i o n ，w ec o n s t r u c t e dak i n do fs e q u e n c es ( r ) w i t hp e r i o d2 n 1b a s e d o nt h ek n o w l e d g eo fn u m b e rt h e o r ya n df i n i t ef i e l d ，w h e r e 扎i se v e n 。7 a n d2 n 2 1 a l ec o p r i m e w e p r o v e dt h a ts c a nh a v el a r g el i n e a ls p a na n dg a v et h ev a l u eo fi t e x a c t l yt h r o u g hc h o o s i n gp r o p e rp a r a m e t e rr t h e i rl i n e a rs p a ni sm u c hl a g e rt h a nt h e l i n e a rs p a no fg o l ds e q u e n c e s ，s m a l ls e to fk a s a m is e q u e n c e s ，g o l d - l i k es e q u e n c e s a n du d a y as e q u e n c e s b a s e do na2t o1m a p p i n gi nf i n i t ef i e l d 毋2 m ，af a m i l yo f s e q u e n c e sw i t hp e r i o d2 m 一1h a v i n gb a l a n c ep r o p e r t yi sc o n s t r u c t e d a n dw ep r o v e d t h eb i n a r ys e q u e n c e sh a v ei d e a la u t o c o r r e l a t i o np r o p e r t yb yt h et e c h n i q u eo fw a l s h t r a n s f 6 r m a t i o n k e yw o r d s ：t r a c ef u n c t i o n ；l i n e a rs p a n ；b a l a n c ep r o p e r t y ；s e q u e n c ew i t hi d e a l a u t o c o r r e l a t i o np r o p e r t y ；p a r s e v a l se q u a t i o n ；2 - t o - 1m a p p i n g 1 1 湖北大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研 究所取得的研究成果除了文中特别加以标注引用的内容外，本论文 不包含任何其他个人或集体已经发表或撰写的成果作品对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明本人完 全意识到本声明的法律后果由本人承担 论文作者签名：郴蠲 签名日期：呷年f 月2 乒日 学位论文使用授权说明 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电r 了版本；学校有权保存并向国家有 关部门或机构送交论文的复印件和电子版，并提供目录检索与阅览服务；学校可 以允许采用影印、缩印、数字化或其它复制手段保存学位论文：在不以赢利为目 的的前提下，学校可以公丌学位论文的部分或全部内容( 保密论文在解密后遵守 此规定) 作者签名：郴盖郎 指导教师签名：嗜弓季寥 日期：呼兮2 4 日j t 褒j ：卵r 珥 1引言 1 1 伪随机序列的研究背景 1 引言 伪随机序列在测最测距、扩频通信、多址通信、软件测试、雷达导航和密 码学中都有广泛应用【1 - 1 2 】一些技术上相关的参考文献包括【l3 一1 9 】 人们归纳出许多刻画序列伪随机性的指标【2 0 1 ，如序列的周期、线性复杂 度、平衡性、自相关性和稳定性等等 不同的应用背景卜对伪随机序列的要求有所不同通常在测距、导航和般 通信系统中应用时重点考虑它的自相关性质，而在保密通信系统和密码学卜则需 要莺点考察它的线性复杂度冈此，构造具有低自相关值的序列和具有大线性复 杂度的序列有很重要的现实意义 密码学分为私钥密码学和公钥密码学，私钥密码学主要用于信息加密序列 密码作为一种私钥密码体制，它的安全性主要取决于密钥流序列的随机性设计 具有良好随机性的序列是序列密码的重要内容。般的要求是序列具有长剧期、 大线性复杂度、平衡性和易于实现等1 2 1 现有的几乎所有的公钥密码体制中。 如d i f i e h e l l m a n 密钥交换协议、数宁签名标准、椭圆曲线公钥密码体制等都需 要随机数【1 0 】著名的r s a 公钥算法在产生私钥时也需要随机数卜面提到的一 些协议、标准和算法已经应用在通信和计算机网络中伪随机序列生成器可以作 为伪随机数生成器，其基本要求是序列具有良好的串分布性质冈此伪随机序列 既可作为序列密码体制的密钥流，又可作为公钥密码体制的会话密钥、产生随机 数等也町以直接利用伪随机序列构造公钥密码体制和数字签名算法等 1 2 伪随机序列的发展 通过抛硬币的方法可以得到一个随机序列，它具有两个方嘶的特点：一是预 先不可确定、不可重复实现即在实验前无法预知序列是怎样的，i n 日在所有的 序列中不可能有两个是完全一致的另一方面所有序列都具有某些共同的随机特 性，对二元序列，g o l o m bf 7 1 结了三条随机性假设： r 1 若序列的周期l 为偶数，则0 的个数与l 的个数相等；若l 为奇数，则0 的 个数比1 的个数多l 或少1 r 2 长为z 的串占1 2 f ，同0 串和1 串的个数相等或至多差1 个 1 湖北大学硕上学位论文 r 3 序列的异相自相关函数为一个常数，即序列为二值自相关序列 如果一个序列，一方面它的结构是可以预先确定的，并且可以重复地产生和 复制；另一方面又具有某种随机特性( r 1 r 3 ) ，便称这种序列为伪随机序列即伪 随机序列是具有某种随机特性的确定序列 伪随机序列的理论与应用研究大体上可以分成三个阶段【7 1 ：( 1 ) 纯粹理论研 究阶段( 1 9 4 8 年以前) ；( 2 ) m 序列研究的黄金阶段( 1 9 4 8 1 9 6 9 ) ；( 3 ) 非线性生成器 的研究阶段( 1 9 6 9 一) 最早的序列研究可以追溯到1 8 9 4 年，作为一个组合问题来研究d e b r u i j n 序 列1 9 4 8 年以前，人们研究伪随机序列的理论主要是因其具有优美的数学结构 1 9 4 8 年s h a n n o n 信息论诞生后，伪随机序列被广泛地应崩在通信以及密码 学【1 - - 5 , 2 2 - - 2 5 】等重要的技术领域s h a n n o n 证明了“一次一密”是无条件安全的，无 条件保密的密码体制要求进行保密通信的密钥量罕少与明文量一样大此后的 一段时间内，人们一直研究具有足够长周期的伪随机序列如何产生这样的序列 是2 0 世纪5 0 年代早期的研究热点线性反馈移位寄存器( l f s r ) 序列是这个时期 研究最多的，凶为一个n 级l f s r 可以产生周期为2 n 一1 的最大长度序列，而且具 有满足g o l o m b 随机性假设的随机特性，通常称之为m 序列这段时期的研究奠 定了l f s r 序列的基本理论，一些经典的结论参见文献【3 ，7 】 1 9 6 9 年m a s s e y 发表了“移位寄存器综合与b c h 译码 2 6 1 ”一文，使得伪随 机序列的研究进入了构造非线性序列生成器的阶段b e r l e k a m p m a s s e y 算法( 简 称b m 算法) t 2 7 , 2 8 1 指m ：如果序列的线性复杂度为n ，则只需要2 n 个连续比特就 可以恢复出全部的序列从这个结论可以看出m 序列的线性复杂度很小，因而彳i 能够直接片j 来做流密码系统的密钥流序列 此后人们一直在寻找伪随机性较好的序列的构造方法 1 3 伪随机序列的构造方法与方向 目前，伪随机序列的构造方法可以分成两大类：一是基于数学理论构造伪随 机序列；二是基于l f s r ( 线性反馈移位寄存器) 构造伪随机序列两种构造方法 各有优缺点前者在理论上容易分析序列的随机性质，但往往不容易实现或者实 现的代价较高；而后者在工程上很容易实现，成本较低，但有的情况下不容易分析 其随机性质 基于数学理论构造伪随机序列也可分成两类：基丁数论的构造和基于有限域 一2 一 1引言 的构造【2 0 - 3 5 1 前者利用的数学工具主要是二次剩余理论和割圆理论；后者利用的 数学工具主要是迹函数但是这两类划分的界限并不是十分严格，即有些时候可 以把数论和有限域结合起米构造伪随机序列 基于l f s r 的伪随机序列生成器有很多，总体上可以分为两大类：一类是用 一个几元布尔函数作用于n 个输入比特，布尔函数的输出作为密钥流序y t j ；另一 类是用一个l f s r 控制另一个l f s r 前者包含两种生成器，即非线性组合生成器 和非线性滤波生成器 2 5 1 南于m 序列的线性复杂度小，不能直接用作密钥流序 列，凶此通常采用将m 序列作驱动序列，然后用一个布尔函数作用于这些驱动序 列的方法来提高序列的线性复杂度非线性组合牛成器南仡个l f s r 和个非线 性组合器组成：非线性滤波生成器由一个l f s r 和一个前馈逻辑组成第二类生 成器也包含两种控制模型，钟控生成器1 3 6 ，3 7 】和缩减牛成器【6 ，3 8 1 这两种牛成器的 原理都是用一个控制序列对另一个基序列做不规则采样钟摔生成器是在基序列 中插入新的符号，其输出序列指数幂依赖于产生它的生成器的输入参数：而缩减 生成器包括自缩减生成器是存基序列中删除符号，这种构造结构简单，易于用硬 件实现 基于l f s r 的伪随机序列构造还有一些其它的方法，如钟控非线性组合生成 器、钟控滤波生成器、g u n t h e 钟控生成器等【2 5 】，主要是将上面提到的方法做不 同的组合 现在人们获得的伪随机序列主要有m 序列1 7 1 ，g o l d 序列【3 9 4 0 ，4 ，g m w 序 列 4 2 4 34 4 ，k a s a m i 序列【4 5 - 4 引，b e n t 序n t 4 9 5 2 】，t n 序列 5 3 , 5 4 1 ，n o 序列1 5 5 等 m 序列是研究其它序列的基础，它满足平衡性，有最好的白相关特性，但- 瓦 相关满足一定条件的族序列数很少g o l d 序列互相关函数为3 值，序列部分平 衡，有良好的相关特性，族序列数相对较大，但它的弱点是线性复杂度很低，仅 是相同长度的m 序列的两倍g m w 序列具有平衡性、线性复杂度大、自相 关性好( 与m 序列相同) 等优点它是非线性序列，且数量比m 序列多尽管单 个g m w 序列有优势，但一族满足一定互相关条件的g m w 序列数很少 k a s a m i 序列分为小集合的k a s a m i 序列和大集合的k a s a m i 序列小集合 的k a s a m i 序列族序列数大，且互相关值达w e l c h 下界，大集合的k a s a m i 序列族序 列数非常大。互相关性没有小集合的k a s a m i 序列好k a s a m i 序列的缺点是：序列 是不平衡的，且线性复杂度f i 大( 但比r n 序列，g o l d 序列稍大) b e n t 序列具有平衡 性、相关值达w e l c h 下界、族序列数多、线性复杂度人等优点，是目前综合性能 一3 一 湖北大学硕上学位论文 很好的伪随机序列但b e n t 序列的弱点是实现比较困难，线性复杂度1 i 好衡量等 n o 序列的相关值口j 达到w e l c h 下界，族序列数多，但有序列不平衡的弱点 b m 算法指出，只要已知序列8 的任意连续两倍线性复杂度个比特即口j 恢 复出整条序列设计性能好的密钥序列是密码学的一个研究热点为了抵抗基 于b m 算法实施的明文攻击和提高数据的安全性，在某些应用环境巾伪随机序 列应具有较大的线性复杂度因此，设计其有大线性复杂度的序列是一个重要的 研究课题 文献【5 3 】提出了一种增大d 齐次序列线性复杂度的方法，这种方法仍能保持 序列集的相天性质虽然这种方法成功提高了d 一齐次序列的线性复杂度，但只有 很少的儿类d 齐次序列被证明有较人的线性复杂度下届，其中最成功的例子是对 小集合的k a s a m i 序列的各种推广，如n o 序列1 5 5 1 、t n 序列 5 3 1 和文献【5 6 】中的一 类广义的k a s a m i 序列集尽管这些推广的序列集同小集合的k a s a m i 序列。样具 有优良的低卡h 关性质，而且能获得很大的线性复杂度，但是它们的集合容最依然 很小，长度为2 n l 的序列集的集合容量仪为2 , * 2 ，这里t , 为偶数 文献 5 7 】构造了周期为2 n 一1 ( 其中n 兰2 ( m o d4 ) ) 的低相关出齐次序列集， 这类序列集具有较好的低相关性质、大的集合容景和线性复杂度文献【5 8 n 用 一种d 一齐次函数构造了周期为2 n 一1 的低相关序列集，完全确定了它们的相关值 分布，并证明了这些序列具有大的线性复杂度，这里t , 兰0 ( m o d 4 ) 文献【5 9 】利 用另一种d 齐次函数构造了周期为2 n 一1 的序列集s ( r ) ( r 与2 n 2 1 互素) 这类 序列集的相关性质略小于小集合的k a s a m i 序列【5 7 1 ，但是其集合容量为2 n 1 4 论文的研究内容和组织结构 本文研究内容有两部分： ( 1 ) 刈丁i 偶数t , ，利用新的d 齐次函数构造了一类周期为2 n 一1 的序列s ( 川， 这里r 与( 2 n 2 1 ) ：巨素通过选取适当的参数r ，证明序列具有较大的线性复杂 度，并且精确地给出序列线性复杂度的大小 ( 2 ) 从有限域毋。卜的2 对1 映射出发，构造了一类周期为2 m 一1 具有平衡 性的二元序列证明了这些序列具有理想l _ - i 相关性质 论义结构如卜： 第l 章介绍了伪随机序列的研究背景、发展现状以及伪随机序列的构造方 法与方向 一4 一 1引言 第2 章为预备知识，介绍了有限域的相关内容、迹函数及其性质和序列的相 关知识 第3 章利用d 一齐次函数构造了一类周期为2 “一l 的序列s ( ，这里? 与( 2 ”2 一 1 ) 互素通过选取适当的参数r ，证明了s ( r ) 具有较大的线性复杂度，并且精确地 给出序列线性复杂度的大小 第4 章从有限域毋：。上的2 对1 映射出发，构造了一类周期为2 m 一1 具有平 衡性的二元序列证明了这些序列具有理想自相火性质 第5 章给出了结果与展望 一5 一 湖北大学硕j 二学位论文 2预备知识 本章第一节介绍了有限域的相关理论；第二节介绍了迹函数及其性质；第三 节给出了伪随机序列的随机性指标 2 1 有限域理论 本节介绍有限域的相关知识根据义献【6 0 ，6 l 】可得有限域的相关知识如下： 定义2 1 若域f 含有有限个元素，则称域f 为有限域，其中域中元素的个数 称为有限域f 的阶 最简单而又最基本的有限域是整数环z 模素数p 的剩余类域z ( p ) 用符 号昂农示p 元有限域z p ) 定义2 2 设f 是任意的一个域，如果f 的素域同构于有理数域q ，则称f 的 特征为0 ( 或o o ) ，记为c h a r f = 0 ( 或c h a r f = o o ) ；如果f 的素域同构于整数 环z 模素数p 的剩余类域z 0 ) ，则称f 的特征为p ，记为c h a r f = p 域特征的定义等价于：若e 是域f 的单位元，对于任意正整数n ，如果n e 0 ， 则称f 的特征为0 ( 或c o ) ，否则称满足n e = 0 的最小正整数n 为f 的特征 结论2 1 若域f 的特征为p ，对于任意q f a 0 ，序列a ，2 a ，( p 一 1 ) a ，p q 中的元素两两互不相同；若域f 的特征为o o ，序列q ，2 a ，礼q ，中的 元素两两互不相同 结论2 2 任意域的特征或为素数，或为o o 定理2 1 设f 为有限域，则f 中恰有矿个元素，这里c h a r f = p ，而n 是f 关 于其素域r 的域的扩张次数 设f 是一个q 元有限域，记为日，则c = 局 o 为q 一1 阶乘法群， 由l a g r a n g e 定理知，对于任意口日，均有o f f _ 1 = 1 ，从而对于任意q 日， 均有o g q = q 定理2 2 自限域r 的乘法群露是一个循环群设e 是域f 的扩域，q 0 ， 如果存在f m 中的非零多项式，( z ) ，使得，( q ) = 0 ，则称q 是域f 的代数元，否 则称a 是域f 的超越元如果e 中的元素都是域f 的代数元，则称e 是f 的代数 扩张 6 2 预备知识 定义2 3 设e 是f 的代数扩张，f ( x ) 是f m 中首项系数为1 的多项式， 且d e g f ( x ) 1 ，如果满足下列条件： ( 1 ) f ( x ) 在e 中能分解成一次因式的乘积，即 ，( z ) = ( x q 1 ) ( z 0 1 2 ) ( z q 。) ， 其中q t e ，i = 1 ，2 ，8 ； ( 2 ) e = f ( a l ，o t 2 ，o t a 则称e 是f ( x ) 在f 上的分裂域 易知，( z ) 在域f 上的分裂域实质卜就足域f 的包含，( z ) 的全部根的最小 扩域 定理2 3 设f 是一个域，f ( x ) 是f x 】中首项系数为1 的多项式，d e g f ( x ) = n 1 ，f ( x ) 在f 上的分裂域总是存在的，并且在同构意义下唯一 定理2 4 对于每个素数p 和每个正整数n ，都存在矿元有限域，并且任 意q = p n 元有限域都同构于护一z 在域r 上的分裂域 定义2 4 设f 是有限域，如果q 为f 的代数元，则称使得f ( a ) = 0 的首项系 数为1 的次数最低的多项式，( z ) 州z 】为o l 的极小多项式 由。_ ：域f 中的每个元素均为f 的代数元，对f 中的任一元素a ，其极小多 项式为z o t 一般而言，如果q 为f 的代数元，则q 的极小多项式f ( x ) 。定 为f x 1 中的不可约多项式 定义2 5 有限域目的乘法群e 的生成元叫做岛的本原元，而本原元 在f 口m 上的极小多项式叫做日上的一。个本原多项式 定理2 5 对于每个素数p 和每个整数n ，在昂陋】中总存在n 次本原多项式， 从而也存在几次不可约多项式 定理2 6 设f 为有限域，c h a r f = p ，则对f 中的任一元素口，有 ( x + o ) p = x p + 扩 由定理2 6 - - i 以推知，若口1 ，q 2 ，q 。是有限域f 中的元素，c h a r f = p ，则 对于任意的自然数n ，恒有 一7 一 湖北大学硕士学位论文 特别地，对任意及砀，有q p “= 口 2 2 迹函数及其性质 根据文献【5 0 ，6 1 ，本节给出了迹函数的定义以及它的基本性质 定义2 6 设昂n 和m 为有限域，n = e m 称t r n m ( ) 为域到砀的迹函 数，如果对于任意的口哆，t r 未( q ) 均满足 在序列研究中常用到迹函数的下列基本性质： ( 1 ) t r ：l ( a ) = t r 景( 口p ”) ，v q f 知，j = 0 ，1 ，2 ，； ( 2 ) t r 备( a a + 6 p ) = a t r ：( q ) + 6 t r 未( p ) ， v a ，b j 加，v a ，p ，如； ( 3 ) 耶跏，方程t r “m ( x ) = p 在砀中的解的个数恰有矿一m 个； ( 4 ) v q ，t r ? ( a ) = t r ，( t r 嚣1 ( 口) ) ； ( 5 ) v 口易，q 0 ，有( - 1 ) h 2 ( q 蕾) = o ； x e 昂n ( 6 ) ( t r y ( a ) ) 矿= t r 昌( q 矿) ，v a e 俨，j = 0 ，l ，2 ， 由性质( 2 ) 知，迹函数是从有限域b n 到耳。上的线性映射，它口j 以描述出从 有限域b 。到昂。上的线性变换，并且与基的选择无关 特别的，当p = 2 时，r 。表示含有2 n 个元素的有限域，昂是见。的乘法群 设正整数亿，k ，e 满足n = e k ，对z f 2 n ，从易n 到疋t 的迹函数t r ( x ) 为 迹函数有如下性质： ( 1 ) 对于所有a ，b 易一，z ，y r n ，有t r ( a x + b y ) = 口t r ( z ) + 6 t r ：( ) ； ( 2 ) 对于所有z 玛。，有t - - 心n 以- - 2 k ) = t r 2 ( z ) ； 一8 n p 1 口 。汹 | | 竹 尸 q 。甜 矿 口 “铷 i i 以 扣 m 扩+ m p a + a = q n m rc z “铷 = 舻 z 恤铷 = z旺 2 预备知识 ( 3 ) 对于所有z r n ，有t r ? ( x ) = t r k t r ( x ) 一1 定理2 7 设n i q n l ，并且q 为n 的次本原单位根，a i = 吗q 巧，i = j = o 0 ，1 ，2 ，若 o t ) 是日上的序列，则此序列町以用迹函数分解表示为 特别地，如果 o t 是最上的m 序列，n = q “一1 ，那么存在b 。的一个本原元 素。和一个非零元，y 使得a i = t r ? ( 7 0 ) ，i = 0 ，l ，2 ， 定理2 7 表明：很多序列都口j 以经过某些迹函数的适当组合而成，从而启发 人们巧妙地组合一个特定的迹函数来得到多类性能优良的伪随机序列，如m 序 列、g m w 序列、k a s a m i 序列、n o 序列、t n 序列等一个序列用迹函数表示 后，将变得简单明了，有利于对这些序列进行分析 2 3 伪随机序列的随机性指标 评价序列随机性的指标有整体随机性指标和局部随机性指标 整体随机性指标从无条件安全的角度看，伪随机序列的随机性评价指标 主要有：周期、平衡性( r 1 ) 、游程性质( r 2 ) 、自相关函数( r 3 ) 以及线性复杂度 等【7 】 线性复杂度是序列随机性的一个最蕈要的指标，它考虑的是用怎样 的l f s r 重构给定的序列周期是一个非随机特性，但是周期越大表示序列 的可测性就越小通常称具有长周期、大线性复杂度并且满足性质r l r 3 的序列 为最优伪随机序列 定义2 7 设8 。= 8 0 8 1 表示有限域g f ( q ) 上的序列，即8 c f ( q ) 若存 在正整数n 满足8 件。= 8 t ( i 0 ) ，则称序列s o o 为周期序列，n 称为该序列的周 期所有可能周期的最小值称为序列的最小周期，通常所指的序列的周期都是最 小周期若序列s o 。的周期为n ，则记该序列为 定义2 8设8 = ( 8 0 ，8 1 ，8 n - 1 ) 为g f ( g ) 上周期为n 的序列，记= 一9 2l0 = 一叼 口 幻三， 舢 = 凸 湖北大学硕士学位论文 e 2 丌厅口表示q 次本原单位根，则8 的周期自相关函数定义为 ( 2 - 1 ) 我们通常所说的自相关函数就是指周期自相关函数若周期序列的自相关函 数只取k 个不同的值，则称之为k 值自相关序列 定义2 9 设8 = ( 8 0 ，8 1 ，8 n - 1 ) 为g f ( q ) 上周期为n 的序列，定义8 的线性 复杂度l c ( s ) 为满足下列关系式 c o s i + e 1 8 i 一1 + + c 1 8 i f ，l i n 的最小正整数f 其中c o = 1 ，c 1 ，c 2 ，c l c f ( q ) ，相应的多项式c ( z ) = 1 + c l x + + c 1 x l 称为8 的极小多项式从l f s r 的观点看，c ( z ) 即为能够产 生8 的l f s r 的反馈多项式，而z 则为l f s r 的级数 定义2 1 0 【6 2 1 设8 是线性移位寄存器序列，定义s 的线性复杂度l s ( s ) 为能够 生成8 的最短的线性移位寄存器的级数 记8 ( x ) = 8 0 + 8 1 x + + 8 n - l x ”1 ，则序列s 的线性复杂度和极小多项式可 以简单的表示为【6 0 ，6 3 】 c ( x ) = ( x n 一1 ) g c d ( 矿一1 ，s ( z ) ) ( 2 - 2 ) l c ( s ) = n d e g g c d ( 2 7 n 一1 ，s ( z ) ) 】 ( 2 - 3 ) ( 2 2 ) 式和( 2 3 ) 式给出了计算周期序列线性复杂度和极小多项式的公式 k e y 在文献【6 4 】中指出，若将序列8 = s ( ) 表示成a 的多项式，则其线性复杂 度l s ( s 1 等于该多项式中所包含的非零单项式的数目 局部随机性指标判断序列的随机性，原则卜可以通过计算其整个周期一卜的 一些随机性r 1 一r 3 但由于输出序列周期都很长，因而直接计算是很闲难的，故可 用数理统计的方法进行局部随机性检验常用的指标有频度检验、序偶检验、图 样分布检验、游程检验、自相关特性检验以及局部复杂性检验等【6 5 1 假设截取 序列的长度为，其巾0 ，l 的个数分别为0 ，1 ，决策门限值取a = 5 频度检验该指标刖于检测长序列中1 的个数是否与均值2 相差很大 1 0 一 一 n 一 r 一 0 以一 + 以 “铷 = 丁g 2 预备知识 计算t = ( n o n i ) 2 ，丁服从自由度为1 的) ( 2 分布，即t x 2 ( 1 ) 若t 3 8 4 ， 则检测通过 序偶检验该指标用十检测长序列中0 0 ，1 1 ，0 1 ，1 0 出现的次数是否接近 计算 t 2 志丢东呜一熹善研+ 1 ， t 服从自由度为2 的x 2 分布，即t x 2 ( 2 ) 这里n o o ，n n l o ，n 0 1 分别表 示0 0 ，1 1 ，1 0 ，0 1 出现的次数若t 2 ) 长符号出现次 数的接近程度把长序列分成k 个组，k = 【g m j 表示不超过m 的最大整 数计算 t = 警芹一k 2i 厶7 一 i = 0 t 服从自由度为m 的) ( 2 分布，即t x 2 ( m ) 设i = i m - i 2 一1 + + i x 2 + i o ， 则五表示( i m 一1 ，i l ，i o ) 出现的次数当m = 3 ，4 ，5 时，相对应的) ( 2 值分别 为1 4 0 6 7 ，2 4 9 9 6 ，4 4 9 7 0 ，若t x 2 ，则检测通过 游程检验该指标用于检测序列中各种长度的游程总数是否与真随机序 列相似当序偶检验通过时才进行游程检验设均值= 1 + ( 2 n o ) n 1 n ) ，方差= ( 均值一1 ) ( 均值一2 ) ( n 一1 ) 以及t = ( 游程一均值) 、方著，计算均值、方蔗 和丁的值t 服从均值为0 ，方差为l 的正态分布，即t n ( 0 ，1 ) 若i t i o ) ，若l 【t ( d ) 一( ( 一d ) 2 ) 】识矿习历i 1 9 6 ，则检测通过 湖北大学硕上学位论文 3一类具有大线性复杂度的序列 人们构造了几类具有大线性复杂度的序列集，这些序列集的容罱均 为2 n ，并且线性复杂度都比g o l d 序列、小集合的k a s a m i 序列、g o l d 1 i k e 序列 以及u d a y a 序列的线性复杂度大很多 5 7 , 5 8 , 5 9 本章主要是根据文献【5 7 5 9 】中序 列的构造方法，利用新的d 一齐次函数构造了一类周期为2 几一l 的序列集s ( ”，这 里n 为偶数，r 与( 2 n 2 1 ) 互素这类序列集的容量也为2 n ，通过取适当的参数r ， 证明了该序列具有大的线性复杂度，并精确计算出线性复杂度的值 本章中g c d ( a ，b ) 表示数a 和b 的最大公因数 首先介绍d 一齐次函数的定义 定义3 1 【5 3 】设f ( x ) 是从而。到见。的函数，d 是一个正整数，满 足g c d ( d ，2 m 一1 ) = 1 称f ( x ) 为d 齐次函数，如果对于玛。中的任意元素y ， 均有f ( v z ) = y d f ( x ) ，其中z 为尼m e 中任意一个元素 设s ( ) 是二元序列，且 s ( r ) = _ 【s ；( ) ) 銮i 2 = t r t r ：( q + 仳q 纪) ”) ：i 2 ( 3 - 1 ) 其中n = 2 k ，d = 4 ( 2 七一1 ) + 1 ，q 为尼n 的本原元，m 为毋n 中任意一个冗素，参 数7 为正整数 序列s ( r ) 对应的多项式为 g ( z ) = t r k t r ( z + m 一) n 。( 3 - 2 ) 根据文献【6 4 】可知，要计算s ( ) 的线性复杂度，只需计算g ( x ) 的展开式中关 于z 的次数互彳i 相同的非零单项式的数目即可 引理3 1 令 ( z ) = t r 2 0 + 3 x d ) ，则 ( z ) 是1 - 齐次函数 证明由于五( z ) 是从易到f 2 t 上的函数任取y 唯，则 五( 可z ) = t r ( z ) + m ( 可z ) d = t r ( 可z ) + t r 2 m ( 可z ) d = y t r ( x ) + t r 。n 、m 可d 一) 一1 2 一 3 一类具有大线性复杂度的序列 = y t r , ( x ) + y d t r 2 ( 7 i x d ) = y t r y ( x ) + t r ( t i x d ) = y t r 2 ( x + m 一) = y 五( z ) 其中d = 4 ( 2 k 一1 ) + 1 ，故y d = y a ( 2 k - 1 ) + 1 = ( y 2 k - 1 ) 4 y = y 当y = 0 时，必有 ( 可z ) = 秒五( z ) 对( 3 2 ) 式进行化简，令g ( z ) = t r t r 2 ( x + m ) ) ，则有 g ( x ) = 七一l j = o 七一l j = o 七一1 t r 2 ( x + m ) r ( z + m z d ) + + m z d ) 2 。 r 掣 = ( z j = o + 饥z d + z 2 + 曾。z d 2 ) 7 2 k - 1f z - - ，、i x 4 _ 1 ) + 1 + z 2 + 伊z 时_ 1 ) + 卜掣 j = o 、 7 二k - 1m 协4 叫彬_ 1 + 督。x ( 2 k - - 1 ) ( 4 2 4 - 1 ) ) 卜 其巾d = 4 ( 2 七一1 ) + 1 设y = x 2 1 ，那么 g ( x ) = 七一l j = o k l j = o k 一1 =r j = o x ( 1 + o i y a + y + 谢+ ，) r 卜( 1 - 1 - m y 4 + y + 霄y 一3 ) r 2 j z 一s ( ，i 2 k + y 3 + y 4 + m 可7 ) ” 其中y 4 2 。+ 1 = y ( y 2 + 1 ) 4 y 一4 = 可一3 引理3 2 如果r 由下而形式给出，那么g c d ( r ，2 七一1 ) = 1 1 3 湖北大学硕上学位论文 k = 3 m ，且7 不整除m 一1 ( m 为大于等于2 的整数) k = 3 m ，且7 整除m 一1 ( m 为大于等于2 的整数) k = 3 m + 1 ( m 为正整数) k = 3 m + 2 ，且k 为奇数( m 为正整数) k = 3 m + 2 ，且k 为偶数( m 为正整数) 证明( 1 ) 当k = 3 m ，且7 不整除m 一1 时( m 为大于等于2 的整数) ，由丁r = ( 2 七_ l 一1 ) 7 ，因而 g c d ( r ，2 七一1 ) = g c d ( ( 2 七一3 1 ) 7 ，2 七一1 ) = g c d ( 2 七一一1 ，7 2 七一7 ) 7 = g c d ( 2 七一8 7 2 七一7 ) 7 凶( 7 2 七一7 ) 一7 ( 2 七一8 ) = 7 2 ，故 g c d ( r ，2 一1 ) = g c d ( 2 七一8 ，7 2 ) 7 mmm 又2 k _ 8 = ( 7 + 1 ) m 一8 = c 7 + 1 8 = 一7 = 嚷+ 7 m 一7 = i = li = 1i = 2 i n 嚷7 + 7 ( m 一1 ) ，则7 整除2 七一8 但7 不整除m 一1 ，因而7 2 不整除2 七一8 ， i = 2 故g c d ( 2 七一8 ，7 2 ) = 7 所以g c d ( r ，2 七一1 ) = g o d ( 2 七一8 ，7 2 ) 7 = 7 7 = 1 ( 2 ) 当k = 3 m ，且7 整除m 一1 时( m 为大于等于2 的整数) 因r = ( 2 七一 1 ) 7 + 2 凫一，有 g c d ( r ，2 七一1 ) = g c d ( ( 2 七一6 1 ) 7 + 2 七一5 ，2 七一1 ) = g c d ( 7 2 七一5 + 2 七一6 1 7 2 七一7 ) 7 = g c d ( 7 2 七+ 2 七一1 2 5 ，7 2 七一7 ) 7 因为( 7 。2 七+ 2 七一1 2 5 ) 一( 7 2 七一7 ) = 2 七一1 2 5 ，故 1 4 5 7 一 一 七 忌 2 2 + + 7 7 7 7 7 、i，、l，、l，、l，、l， 1 _ i 1 1 1 1 一 一 一 一 一 3 6 l 2 8 一 一 一 一 一 七 七 詹 七 七 2 2 2 2 2 ，j，j，i，i、，- ，、【 i l r 3 一类具有大线性复杂度的序列 g c d ( r ，2 七一1 ) = g c d ( 2 七一1 2 5 ，7 2 七一7 ) 7 = g c d ( 2 七一5 0 7 2 七一7 ) 7 由于( 7 2 七一7 ) 一7 ( 2 七一5 0 ) = 7 3 ，因而 g c d ( r ，2 一1 ) = g c d ( 2 七一5 0 ，7 a ) 7 m竹l 又2 奄一5 0 = 2 3 m 一5 0 = ( 7 + 1 ) m 一5 0 = c ，n i7 + 1 5 0 = c 7 一4 9 = = 1 = 1 除2 七一5 0 m 一4 9 = 嚷+ 7 ( m 一1 ) 一4 2 综上7 整除2 七一5 0 ，但7 2 不整 i = 2 所以g c d ( r ，2 七一1 ) = g c d ( 2 七一5 0 ，7 3 ) 7 = 7 7 = 1 ( 3 ) 当k = 3 m + 1 时( m 为正整数) ，由于r = ( 2 肛1 1 ) 7 ，所以 g