（信号与信息处理专业论文）序列密码中若干关键技术研究.pdf

北京邮电大学博士论文序列密码中若干关键问题研究 摘要 序列的互相关性和序列的线性复杂度一直是序列研究中的重点问题。近年 来，国外学者又提出了序列三项式特性的概念，序列的三项式特性与序列的线性 复杂度有密切的关系，因而这一概念一经提出就得到了广泛的研究。另外，将序 列深度的概念应用到线性码中也是一种很好的尝试和探索。本文主要对这些方面 进行了研究，主要贡献如下： ( 1 ) 序列的互相关性 在序列的互相关性方面，本文研究了m 序列与其采样序列的互相关性。对m 序列与其采样序列的互相关函数的上界和取值进行了研究，同时也对互相关函数 值的概率分布进行了研究。 i ) 在采样因子为d = 等+ 时，推广了 1 】中的结论，从而解决了【1 中提出的一个公开问题，指出【1 】的结论只是我们的结论在p = 3 时的特例。 i i ) 在采样因子为d ；等和d ；等+ 型时，给出了互相关函数巳( f ) 口+ jp + l z 的精确取值。 i i i ) 针对以上三种采样因子，得到巳( f ) 关于r 的概率分布的结果。结论表明， 当p 充分大时，l + g ( f ) 取最大值的概率趋向于0 。 ( 2 ) 序列的三项式特性 在序列三项式特性的研究方面，本文对【2 】的主要结论给出了不同的证明，而 且给出了以固定的正整数对为三项式对的周期为d 的二元序列的精确计数，给出 了求解给定序列的所有三项式对的有效算法，从而完美地解决了与序列三项式特 性相关的问题。同时，本文将三项式对的概念从二元序列推广到任意有限域上的 序列，并证明了对二元序列成立的所有结果对一般有限域上的序列仍然成立。 ( 3 ) 线性码的深度分布 深度的概念最初是用来研究序列的线性复杂度的，【3 】最初将深度的概念应用 第i 页 北京邮电大学博士论文序列密码中若干关键问题研究 到线性码中，而 4 给出了线性码深度分布的精确公式。本文从深度的定义出发 用更简单明了的方法证明了【3 】和 4 】的主要结果。 第i i 页 北京邮电大学博士论文序列密码中若干关键问题研究 a b s t r a c t c r o s s c o r r e l a t i o no fs e q u e n c e sa n dl i n e a rc o m p l e x i t yo fs e q u e n c e sa r ea l lt h e w h i l et h eh o t s p o t so f s e q u e n c e sr e s e a r c h r e c e n t l y ，t h es c h o l a r sa b r o a dh a v er a i s e d t h ec o n c e p to ft r i n o m i a lp r o p e r t yo fs e q u e n c e s ，t h i sc o n c e p th a sc l o s er e l a t i o n s h i p w i t hl i n e a rc o m p l e x i t yo fs e q u e n c e s ，a n di th a sb e e ns t u d i e dw i d e l ys i n c ei t sb i r t h f u r t h e r m o r e ，a p p l y i n g t h ec o n c e p to f d e p t ho fs e q u e n c et ol i n e a rc o d ei sa l s oag o o d a t t e m p t i nt h i st h e s i s ，i s h a l l g i v em yr e s e a r c hr e s u l t s o nt h e s ea s p e c t s ，a n dm y c o n t r i b u t i o nt ot h e s ea s p e c t si sa sf o l l o w s ： ( 1 ) c r o s s c o r r e l a t i o no f s e q u e n c e s i nt h er e s p e c to f c r o s s c o r r e l a t i o no f s e q u e n c e s ，ih a v es t u d i e dt h ec r o s s c o r r e l a t i o n o fm s e q u e n c ea n di t s d e c i m a t i o ns e q u e n c e s c o n c r e t e l y , ih a v es t u d i e dt h eu p p e r b o u n d sa n de x a c tv a l u e so ft h ec r o s s c o r r e l a t i o nf u n c t i o n so fm s e q u e n c ea n di t s d e c i m a t i o n s e q u e n c e s ；m e a n w h i l e ，i h a v es t u d i e dt h e p r o b a b i l i t yd i s t r i b u t i o n o f v a l u e so f c r o s s c o r r e l a t i o nf u n c t i o n st o o ；) w h e na c c ；m 撕。n t s d = 等+ 型，- h a v e g e n e r a i z e a 血em a i n r e s u l tg i v e ni n 【l 】，a n dt h u ss o l v e da no p e np r o b l e mr a i s e di n 【l 】，a n dp o i n t e do u tt h e r e s u l ti n 【1 】i sa s p e c i a lc a s eo f m y r e s u l tw h e np = 3 t i ) w h e nd e c i m a t mf a c t o r 州= 等州= 并p + 掣，i h a v cg i v e n p + l + lz t h ee x a c tv a l u e so f c r o s s c o r r e l a t i o nf u n c t i o n c a ( r ) i i i ) f o rt h et h r e ed e c i m a t i o nf a c t o r sm e n t i o n e da b o v e ，ih a v eg i v e n t h er e s u l to n p r o b a b i l i t yd i s t r i b u t i o no fg ( f ) w i t hr e s p e c tt o ，t h er e s u l ts h o w s t h a tw h e n p i s b i ge n o u g h ，t h ep r o b a b i l i t yo f1 + o ( r ) a c h i e v i n gt h em a x i m a lv a l u e i s e q u a l a p p r o x i m a t e l y t o1 ( 2 ) t h e t r i n o m i a lp r o p e r t yo f s e q u e n c e 第i i i 页 北京邮电大学博士论文序列密码中若干关键问题研究 i nt h er e s p e c to fr e s e a r c ho nt r i n o m i a lp r o p e r t yo fs e q u e n c e ，ih a v eg i v e na d i f f e r e n tp r o o ft op r o v et h em a i nr e s u l ti n 2 】，a n dh a v er a i s e dt h ee x a c te n u m e r a t i o n f o r m u l ao ft h en u m b e ro f b i n a r ys e q u e n c e sw i t hp e r i o ddt h a th a v eaf i x e dp o s i t i v e i n t e g e r sp a i r a sat r i n o m i a lp a i r , m o s ti m p o r t a n to fa l l ，ih a v eg i v e na ne f f i c i e n t a l g o r i t h m t of i n do u ta l lt h et r i n o m i a lp a i r so f a g i v e ns e q u e n c e ，a n d h e n c ec o m p l e t e l y s o l v e da l lt h ep r o b l e m sa s s o c i a t e dw i t ht r i n o m i a lp r o p e r t yo f s e q u e n c e s m e a n w h i l e ih a v eg e n e r a l i z e dt h ec o n c e p to ft r i n o m i a lp r o p e r t yo f s e q u e n c ef r o mb i n a r yc a s et o a r b i t r a r yf i n i t ef i e l dc a s e ，a n dh a v ep r o v e dt h a ta l lt h er e s u l t si nb i n a r yc a s ea r es t i l l h o l di na r b i t r a r yf i n i t ef i e l dc a s e ( 3 ) t h ed e p t hd i s t r i b u t i o no f l i n e a rc o d e t h ec o n c e p to fd e p t hi s f o r m e r l yu s e dt oa n a l y z et h e l i n e a r c o m p l e x i t yo f s e q u e n c e ，a n d t h ea u t h o r so f 【3 】f i r s ta p p l yt h i sc o n c e p tt ol i n e a rc o d e ，b u tt h ea u t h o r s o f 4 】g i v et h ee x a c t f o r m u l ao f d e p t hd i s t r i b u t i o no f l i n e a rc o d ef i r s t i nt h i st h e s i s ，i h a v ep r o v e dt h em a i nr e s u l ti n 【3 】a n d 【4 】b yu s i n gd i f f e r e n tm e t h o dt h a ti sm o r e s i m p l ea n d c l e a r 第i v 页 北京邮电大学博士论文序列密码中若干关键问题研究 第一章绪论 信息理论的奠基者s h a n n o n 在1 9 4 8 年发表了开创性的论文“通信的数学理 论”，从而带来了信息理论和信息技术的革命。信息理论和信息技术因此得到了 广泛而深入的发展。序列分析与设计作为信息理论和信息技术的重要组成部分， 一直就是国内外专家和学者研究的热点问题【l o 】【1 1 】【1 4 】【1 6 】【1 8 】 2 6 】【4 0 】。序列作 为信息技术的一个重要分支，在实际中得到了广泛的应用。 本章首先介绍序列理论和技术在实际中的应用背景，指出序列分析与设计中 的关键问题，然后给出最近在序列研究方面的国际动态，最后给出本文的主要研 究内容和贡献。 1 1 序列应用背景和研究问题 序列技术在实际中具有重要的应用。例如，在扩频通信中，通常使用具有良 好自相关特性和互相关特性的序列作为扩频码序列，在保密通信中也通常采用序 列密码进行数据的加密传输。 研究和设计具有良好自相关特性和互相关特性的序列族是扩频通信中序列 设计追求的目标。例如，在扩频通信中，可以用m 序列作为不同用户的载波序 列，为保证通讯的质量，要求同一个用户的载波序列的不同相位序列之间的干扰 尽可能的小，不同用户的载波序列之间的干扰尽可能的小。因此，就要求载波序 列具有良好的自相关特性和互相关特性。m 序列具有理想的自相关特性，但是m 序列的互相关特性还远没有解决，并且m 序列的数量也较少。这极大限制了m 序列的广泛应用。因此在扩频通信中通常是基于m 序列来构造具有更好互相关 特性并且数量更多的序列族，例如。g o l d 序列就是根据m 序列优选对来构造的 满足如上特性的序列族。同时，研究m 序列的互相关性也为构造基于m 序列的 吏优序列奠定了理论基础。 序列密码是一种重要的密码技术，在实际中有广泛的应用。序列密码以其加 解密速度快，密文无扩展的独特优点在某些场合下备受青睐，因此，序列密码成 为密码学研究中一个非常活跃的领域。序列密码加解密相对简单，其安全强度主 第1 页 北京邮电大学博士论文序列密码中若十关键问题研究 要取决于种子序列的安全性，线性复杂度是衡量种子序列安全性的一个重要性能 指标，根据b m 算法，具有较大线性复杂度的种子序列往往具有较大的安全性， 因此，在序列密码的设计中通常要求产生的种子序列具有较高的线性复杂度。 可见，序列的自相关性、互相关性和序列的线性复杂度是序列研究中的三个 主要问题。 1 2 序列研究的动态 近年来，国外学者将对m 序列之间的互相关性的研究扩展到i n 序列与其具 有较大周期的采样序列的互相关性上，并得到了一定的成果 1 】，但是还有一些 公开问题没有解决。另外，一些学者在研究m 序列的过程中发现m 序列具有良 好的“三项式特性”，即对于m 序列 口， ，任意的j ，i j ，都存在k 使得 口，+ a ，= a 。，并将这个特性推广到任意二元周期序列中，得到了二元周期序列具 有“三项式特性”的充要条件，并对特定序列的“三项式对”进行了研究，但是 他们没有给出通用的求解给定序列的所有“三项式对”的有效算法，也没有给出 一般有限域上序列具有三项式特性的充要条件。 序列的“三项式特性”与序列的线性复杂度具有密切的关系，因此研究具有 “三项式特性”的序列，特别是研究一般有限域上序列的“三项式特性”具有重 要的理论价值和实际意义。 序列的“深度”是在研究序列的线性复杂度过程中提出的一个重要概念，最 近国外的一些学者将序列“深度”的概念应用到线性码上，得到了线性码的些 新的特性，而且给出了线性码的另一个等价分类标准，即按照深度分布等价进行 分类。线性码，特别是线性码中的循环码在纠错编码中具有重要的意义。因此， 研究线性码的深度分布也具有重要的理论研究价值和实际应用意义。 1 3 研究内容和成果 在本文中，我们对m 序列与其采样序列的互相关性、序列的“三项式特性” 以及线性码的深度分布这三个方面进行了研究。并得到了如下结果。 第2 页 北京邮电大学博士论文 序列密码中若干关键问题研究 1 3 1 序列的互相关性 最大长度线性反馈移位寄存器厅歹u ( 也叫m 序歹0 ) 具有理想的目彳h 天特性， 因而在实际中得到了广泛的应用。m u l l e r 在【1 】中研究了当p = 3 且采样因子为 d ：型二掣+ 篁时，有限域g f ( p ) 上的m 序列与其采样序列的互相关函数 p 十l z i i + c 。( f ) i 的上界问题，指出1 1 + c 。( t ) l 3 时1 1 + c 。( f ) i 的上限等于多少? 本文不仅圆满地解决了这个公开问题，指出：当p 3 时 1 1 + c a ( ，) l 旦芸7 ，从而【1 的结果只是我们的结果在p = 3 时的特例，而且 还证明了当采样因子为d = 型p 等1 和d = 垒p 等1 + 型善2 ，p = 3 时，采样序列扣。) + 也是m 序列，并且互相关函数g ( f ) 的取值为三值，即： e ( f ) - 1 ，一l + j 可，一1 一j 万 。最后，本文还针对以上三种采样因子对互相 关函数1 1 + c 。( f ) i 关于，的取值分布进行了研究，证明了： 1 ) 当采样因子为d = 署+ 型时，当p 充分大时，1 1 + c 一( o l = _ p r + l 吖- p - 7 的 概率趋向于0 。 2 ) 当采样因子为d ：型善时，当p 充分大时，l + 巳( r ) ：o 的概率趋向于1 。 p 十1 3 ) 当采样因子为d ：z ! ，p ：3 时，p ( 1 + o ( r ) 二o ) 丢。 p + 1 z 1 3 2 序列的“三项式特性” 二元周期序列的“三项式特性”的概念最初是e hg o l o m b 提出的，g o l o m b 在【2 中提出了二元周期序列的“三项式特性”和“三项式对”的概念，并利用 第3 页 北京邮电大学博士论文序列密码中若干关键问题例 究 序列分解的方法给出了个数对是一个序列的“三项式对”的充要条件，同时对 序列的“三项式对”的分类和个数进行了研究；c h a r p i n 在【7 】中从循环码的角度 重新刻化了具有“三项式特性”的二元周期序列，得出了以固定的数对( 七，) 为 “三项式对”的序列的集合实质是一个循环码的重要结论，并给出了以( 七，) 为 “三项式对”的二元周期序列的个数的计数公式：但是他们都没能解决如下两个 问题：求解给定序列的所有的“三项式对”的有效算法? 一般有限域上序列的“三 项式特性”的概念是否存在，如果存在，在二元情形下的结论在一般有限域上是 否成立? 本文用序列多项式的方法对具有“三项式特性”的二元周期序列重新进行刻 划，同样得到了如下结论： 1 ) 一个数对是一个序列的“三项式对”的充要条件； 2 ) 一个序列没有“三项式对”的充分条件； 3 ) 一个数对可作为“三项式对”的充要条件； 4 ) 以( 七，f ) 为“三项式对”的周期为d 的序列的计数公式和具体求解方法。 另外，本文还进一步将“三项式特性”的概念推广到一般有限域上，并且证 明了在二元情况下的结论在一般有限域上都成立，同时给出了求解给定序列的所 有“三项式对”的有效算法。用序列多项式的方法将“三项式特性”的相关结论 从二元序列推广到一般有限域上的序列非常直观简洁，而用序列分解的方法则要 困难得多。 1 3 3 线性码的深度分布 深度的概念最初是用来分析序列的线性复杂度的，t e t z i o n 在【3 】中首先将它 成功地应用到线性码中，并给出了码字深度、线性码深度分布的概念，证明了每 一个【n ，k 】线性码恰有k 个非零深度值，并且由任意k 个具有不同深度的非零码 字都可以构成这个线性码的一个生成矩阵，同时提出了一种新的对等价线性码进 行分类的方法：按深度等价进行分类，并确定t 8 ，4 ，4 】扩展h a m m i n g 码的深 度分布等价类，但是t e t z i o n 没有给出一般线性码的深度分布公式；y l u o 在【4 】 中用矩阵和线性方程组的方法研究线性码的深度分布，给出了线性码深度分布的 第4 页 北京邮电大学博士论文序列密码中若干关键问题研究 一般公式，并进而对具有特定分布的子码的计数问题进行了研究，同时也确定了 _ - - 元 1 1 ，6 ，5 g o l a y 码的深度分布等价类。 在本文中，我们从深度的概念出发，用不同的证明方法给出了同样的结果， 这些证明方法更加直观、简洁，并对线性码深度和深度分布可能的研究方向和应 用前景进行了探讨。 t 1 4 文章组织 本文的组织如下：在第二章中给出序列设计与分析的基础理论知识；第三章 介绍m 序列与其采样序列的互相关性；第四章研究具有三项式特性的序列；第 五章给出线性码的深度分布方面的结果；接下来给出与本文相关的一些参考文献 和博士期间完成的论文；最后是本文的致谢。 第5 页 北京邮电大学博士论文序列密码中若干关键问题研究 第二章序列密码理论基础 在本章中，我们将介绍序列分析与设计中的些基本概念和基础知识，包括 有限域的基本理论和线性反馈移位寄存器序列的基本理论，并给出证明我们的结 论需要的一些基本定理。 2 1 有限域 有限域是序列分析与设计中的个重要概念，我们所研究的序列都是有限域 上的序列。因此，作为序列分析的基础理论知识，我们有必要先简要介绍一下有 限域的相关理论。关于有限域的更完整的理论请参考参考文献【5 】。 定义2 1 1 ( 群) ： 令g 是个集合，在g 上定义了个二元运算。，并且满足如下条件： 1 ) 。满足结合律；即，对于任何口，b ，c g ，都有口。( 6o c ) = 。b ) 。c 2 ) 存在单位元e g ，使得对于任何a g 。都有a o e = e o 口= a 3 ) 对于每个口g ，都有一个对应的逆元口_ 1e g ，使得口。口= a o 口= e 那么，就称g 关于二元运算。构成一个群。特别的，如果还满足 4 ) 对于任何口，b g ，都有口o b = b o 口 则称g 为阿贝尔群，也叫交换群。 定义2 1 2 ( 环) ： 令r 是一个集合，在r 上定义两种二元运算+ 和o ，如果下面三个条件成立，就 称r 关于二元运算+ 和。构成环： 1 ) 尺关于+ 运算构成一个阿贝尔群 2 ) 。满足结合律，即：对于所有的口，b , c r ，都有0 。b ) o c = 口。( b 。c ) 3 ) 满足分配律：即：对于所有的口，b ，c r ，都有口o ( b + c ) = 口o b + do c 和 ( b + c ) 。口= bo 口+ c 。d 卮览立。 + 运算通常称为加法运算，o 运算通常称为乘法运算。口关于加法运算的逆 第6 页 北京邮电大学博士论文序列密码中若干关键问题研究 元记为一口，a + ( 一b ) 写为口一b ，加法运算的单位元记为0 ，n 个d 相加记为n d 口。b 通常记为幻， 个口相乘通常记为a 8 。 定义2 1 3 ( 子环) ： 环月的子集s 如果在加法运算和乘法运算下都是封闭的，并且也构成个 环，那么称s 为r 的子环。 定义2 1 4 ( 理想) ： 环r 的子环，。如果满足：对所有的a ，r r ，都有a r i 和r a i ，我们 就称，是r 的一个理想。特别的，如果r 是交换环，并且存在口e i ，使得 i = a r ir r ) ，就称，是r 的一个主理想。主理想通常也简称为理想。 定义2 1 5 ： ( i )如果一个环关于乘法运算具有单位元，即：存在一个元素e r ，对 所有的口r ，都有a e = e a = a ，那么就称这个环为具有单位元的环。关 于乘法运算的单位元通常记为1 。 ( i i )如果一个环关于乘法运算是可交换的，即：任何口，b r ，都有a b = b a ， 那么就称这个环为交换环。 ( i i i )如果在一个具有单位元e 0 的交换环中，西= 0 意味着a = 0 或者 b = 0 ，那么就称这个环为整环。 ( i v )如果一个环中的非零元在乘法运算下构成一个群，那么这个环叫做除 环。 ( v )交换除环叫做域。域通常记为f 。 域中的元素口关于乘法运算的逆元通常记为口。 定义2 1 6 ( 有限域) ： 含有有限个元素的域称为有限域。含有q 个元素的有限域通常记为只，有时 也记为g f ( g ) 。 定义2 1 7 ( 特征) ： 令f 是个域，e 是它的乘法单位元，0 是它的加法单位元，如果存在正整 数 ，满足n p = 0 ，那么我们称满足上式的最小的1 为f 的特征，否则称f 的特 第7 页 北京邮电大学博士论文序列密码中若干关键问题研究 征为旬。 定理2 1 1 ： 域f 的特征为素数或0 。 证明： 如果域f 的特征为0 ，那么定理得证。 现在假设f 的特征不为0 ，令刀为f 的非零特征，那么有船= 0 ，假设 不 是素数，那么”= n 玎2 ，其中1 啊，n 2 栉。因此，0 = 甩l 肝2 9 = t i e 2 e ，从而h i e = 0 或者n 2 e = 0 ，根据特征的定义，f 的特征为m i n ( n 。，”2 ) n 。矛盾。 推论2 1 1 ： 有限域f 的特征为素数。 证明： 令e 为，的乘法单位元，那么根据域的定义，p ，2 e ，都是f 中的元素。因 为f 是有限域，所以必然存在1 m ”，使得m e = 珂p ，即伽一m ) e = 0 ，所以f 有 非零特征，根据定理2 1 1 ，的特征为素数。 定理2 1 2 ： 有限域f 的特征为p ， 为任意自然数，口，b 为f 中任意两个元素。那么 ( 口+ 6 ) ，= a ，+ b ，( 2 1 i ) 证明： 只需证明( 口+ 9 = 口9 + 6 9 然后利用数学归纳法就可证明结论。 因为 ”p = a l , + b p + 篓 弘川 ”， 又当1 i p 时， 件世群=p虹紫=ps-o(m。di(i 1 i ( i 1 力( 2 1 3 ) l fj 1 ) 。 一1 ) 、 、。 所以 第8 页 北京邮电大学博士论文 序列密码中若干关键问题研究 定理得证。 定理2 1 3 ： 任何有限域尸都含有p ”个元素，其中p 为f 的特征，m 为正整数。 证明： ( 2 1 4 ) ( 2 1 5 ) 显然，0 ，e , 2 e ，( p 一1 ) e 捏r ：f 中不同的元素，如果，中再没有其它元素，则 结论成立。 否则，令函是不同于o ，e , 2 e ，( p - 1 ) e 的元素，那么a o e + a i 都是f 的元素， 其中a 0 吼= o ，l ，2 ，p i ，并且不同的( 口。，口。) 对应不同的元素。如果现在再也 没有不同于口。e + a 。q 的元素，那么结论成立。否则，我们可以一直进行下去。 因为f 为有限域，所以，在有限步之后，一定存在正整数肼，使得 a o e + a l a l + + 口“口构成f 的所有元素，其中a 0q ，口= 0 , i ，2 ，p l ， 并且不同的( 口o ，口l ，一，口) 对应不同的元素。而e + a 1 + + 口“口“的所有 可能组合构成的元素个数恰好是p “，定理得证。 定义2 1 8 ： 令f 是一个域，口是f 中的一个非零元素，如果存在正整数7 ，满足口”= 1 ， 那么称满足条件的最小的n 为1 2 的阶，如果不存在这样的7 ，就称口的阶为无穷 大。 显然，有限域中的非零元素都有有限的阶。 定理2 1 4 ： 令c 为一个含有g 个元素的有限域，那么中阶最大的元素口的阶为q l 。 证明： 令为e 中的任一非零元素，口的阶为埘，的阶为”，那么妒的阶为 第9 页 o 1 i + 矿 口 ， 叭 矿 ，、 p 氰 ” 而从 北京邮电大学博士论文序列密码中若干关键问题研究 m n g c d ( m ，h ) 。 因为口为中阶最大的元素，又筇，所以筇的阶小于等于口的阶 即m n g c d ( m ，”) m ，因此必要g c d ( m ，”) = 玎，即r i ，”。 由的任意性可知，c 中的任何非零元素都满足方程 工辨= l ( 2 1 6 ) 所以聊q 一1 ，又显然有m q l ，因此，m = q l ，即c 中阶最大的元素 的阶为q l 。 定义2 1 9 ： 称有限域中具有最大阶的元为有限域的本原元。 定义2 1 1 0 ： 令g 是一个阿贝尔群，如果g 中存在一个元素口，使得g 中的任意一个元素 都可以表示为口的幂次的形式，那么就称g 是一个循环群，口成为它的生成元， 并记g = ( 口) 。 根据定理2 1 4 ，很容易得到下面的推论。 推论2 1 2 ： 有限域中所有非零元素关于乘法运算构成循环群。 证明： 令f 口为一个含有g 个元素的有限域，口为它的本原元，那么口的阶为q l ， 从而1 ，口，口2 ，口构成了中所有的非零元素。显然+ = “口，口2 ，d q - 2 关于乘法运算构成一个循环群。 定义2 1 1 1 ； 令为有限域，工为变量，称多项式，( 工) = 口o + 口l x + + a n x ”为有限域上 的胆次多项式，其中口。，口l ，一，o ，如果厂( z ) 不能表示为两个次数更 低的多项式的积，就称( 工) 为不可约的。称满足， ) = 0 的口为多项式厂( z ) 的 根。 第1 0 页 北京邮电大学博士论文序列密码中若干关键问题研究 有限域上多项式的集合通常记为【x 】。 定理2 1 5 ： 为一个有限域，那么一个元素口是中的元素的充要条件是 口9 = 口 ( 2 1 7 ) 证明： 必要性。 如果口= 0 ，则显然有0 q = 0 。如果口0 ，那么根据定理2 1 4 的证明，有 口g = 1 ，因此口9 = d 。 充分性。上的多项式x 9 一x 最多有g 个根，而中的元素都是它的根。因 此，满足r x = o 的元素a 必然是中的元素。 定义2 1 1 2 ： 令口为有限域中的一个元素，那么上满足：， ) = o 的多项式称为口的 多项式，其中次数最小的多项式，称为口的极小多项式。本原元的极小多项式称 为本原多项式。 由极小多项式的定义，不难得出如下定理。 定理2 1 6 ： 极小多项式都是不可约多项式。 本原多项式的概念在序列设计中有重要的意义，如m 序列的特征多项式就是 本原多项式，而且不同的本原多项式对应不同的m 序列，在序列循环移位等价 的意义下，本原多项式与m 序列之间存在一一对应关系。 定义2 1 1 3 ( 子域和扩域) 令f 为一个有限域，s 为它的一个子集合，如果s 本身也构成域，那么称s 为 f 的子域。称f 为s 的扩域。 定义2 1 1 4 ( 迹函数) ： 令为一个含有p ”个元素的有限域，为它的子域，含有p ”个元素，t r 第1 l 页 i ! 室堂皇奎堂堕主堡奎 壁型宣里主耋! 芝塑业亚堕! 堑翌 是从f p ，到。的映射： 称乃为c 。到的迹函数。 t r ( a ) = a 一 ( 2 1 8 ) 定义2 1 1 5 ( 二次型) ： 令e 为一个有限域，”为一个自然数，九，l i ，j 3 时计算1 1 + c 。( f ) 的上限等于多少? 我们圆满地解决了这个公开问题，指出【l 】中的结果只是我们 的结果在p ：3 时的特例。而且我们还计算了当采样因子d ：型等，n 为奇数且 口+ l p ；3 ( m o d 4 ) 时和采样因子d = 等+ p - 2 + l ，露为奇数，并且p = 3 时，互相 关函数满足：c a ( t ) - 1 ，一l + 以i 一一1 一正万) ；最重要的是，针对前面三种采 样配靴= 并+ 竿一等符+ 掣硎悯 1 + c 。( f ) i 关于t 的分布进行了研究，并且得到非常好的结果：当p 很大时 第1 9 页 北京邮电大学博士论文 序列密码中若干关键问题研究 1 1 + c 。( ，) i 取最大值的概率很小。这个结果可以解释为当p 很大时，f 芋歹l j ( a 。) 。和 ( ) ，之间的干扰可以忽略，这正是我们在实际应用中追求的效果。 3 2 一些引理 为了得出我们的结论，在本节中，我们给出需要的一些引理。 引理3 2 1 设n 3 是一个奇数，p = 3 ( m o d4 ) 为一个素数， 口， 为有限域g f ( p ) 上的 周期为p - - l 的m 序列，d = 符+ 孚，那么采样序列 的周期为 p n f - - 1 ，从而和。) 为周期次长序列。 证明： 令口为有限域g f ( p ”) 的本原元，那么根据定理2 2 3 ，存在g f ( p “) ，使 得 口，) = 乃( 触) ) ，从而采样序列 口m 可以表示为 口m ) = t r ( f l f z “) ) 。因此为了 证明和。) 的周期为型，只要证明g c d ( d ，p ”一1 ) = 2 。 我们先来证明2 1 9 c d ( d ，p “一1 ) 。因为p ；- 3 ( m o d 4 ) ，”为奇数，所以 p 一；3 ( m o d 4 ) ，从丽1 2 1 ( p - 1 ) ，但4 不能被p “一l 整除，因此型是奇数： 址等+ 孚= 止拿萼巡+ 兰一鳓为 奇数个奇数的和与差，因此d 。为奇数，从而d = d 。+ 以= 奇数+ 奇数= 偶数，因 此2 i d 。所以2 l g c d ( d ，p ”一1 ) 。 下面证明g c d ( d ，p “- i ) 12 。为了证明这个结论，只需证明任一奇素数s 都不 可能为d 与p “一1 的公因子。 北京邮电大学博士论文序列密码中若干关键问题研究 假设存在奇素数s 3 满足j id ，s i ( p ”- 1 ) ， 那么必有 sj ( ( p + 1 ) d 一掣( p 一一1 ) ) ，l l p s 12 ，矛盾。 因为2 l g c d ( d ，p ”一1 ) ，同时又有g c d ( d ，p ”一1 ) 1 2 ，所以g c d ( d ，p ”一1 ) = 2 ，从 而和。 的周期为：旦；1 。 引理3 2 2 设月3 是一个奇数，p ；3 ( m o d4 ) 为一个素数， a ， 为g f ( p ) 上的周期为 p n 一1 的m 序列，d ：星等，那么采样序列如。) 的周期为p n 一1 ，从而 ) 也 口+ l 是m 序列。 证明： 令口为有限域g f ( p “) 的本原元，那么根据定理2 2 3 ，存在卢g f ( p ”) ，使 得 口，) = r r ( p g m ，因此采样序列 可以表示为扣。 = ( r ，( f l a 。) ) 。因此为了 证明扣。 的周期为p ”一l ，只要证明g c d ( d ，p ”1 ) = 1 。 由引理3 2 1 中的证明可知：d = 并为一个奇数，而p n - - l