高斯周期_分圆序列及码本

要 我们首先利用 阶广义分圆集合以及经典的分圆集合来构造二元伪随机序列及两类 察其相关性质；其次计算了 (3)的三阶和六阶 期，作为应用，得到两类 3 经典分圆序列的线性复杂度；最后，给出周期为11q 的二元序列线性复杂度的一种计算方法，作为特殊情形，给出 ( 1), ( 1) 4pp 的具体的线性复杂度。详细结果如下： 第二章，我们利用 阶广义分圆集合构造一类周期为 的二元序列，这里,p 满足 1, 1) 4，然后计算该序列的线性复杂度，讨论 ,p 得该序列具有较好的自相关值。 第三章，我们计算 阶广义分圆集合及其对应的 期，作为应用，利用阶广义分圆集合构造 上的两类 里 ,p 满足 1, 1) 4， 然后利用已求得的 考察当 ,p 互相关值能够接近 。 第四章，我们利用经典的三阶分圆数和六阶分圆数，分别得到 (3)的三阶和六阶分圆数，继而计算出 (3)的三阶和六阶 期，作为应用，计算两类 3 序列的线性复杂度。 第五章， 首先， 我们给出计算周期为11q ， ,p ( 1), ( 1)p e，的 义分圆序列的线性复杂度的一个计算方法；然后，当 4e ，具体计算出两类序列的线性复杂度。最后，设 5( ， ( 1), ( 1) 4pp ， g 是模 p 和模 们确定四阶广义分圆数选取分解式224b ， 4| 关键词： 高斯周期，分圆序列，自相关值，线性复杂度，码本。 Wesof ofasanof3 a ofasof1q,inp(p1),q(q1)=4.asinwesoftoa,p q ofiswesofto,p q ofisweofto 3 6. 3 weatoofasof1q ,p ( 1), ( 1)p e.Asaweof4e ,weofAt5( , ( 1), ( 1) 4pp ,ag ofp q,wes24b , 4|b. 录 第一章 绪论. 1 伪随机序列的研究背景、发展现状及构造原则 . 1 随机序列的研究背景 . 伪随机序列的发展历史 . 伪随机序列的研究现状 . 伪随机序列的构造 .研究背景及相关结果介绍 . 3 典分圆 . 义分圆 . 究背景 . 序列的线性复杂度 .本文的主要研究工作 . 7 第二章 四阶广义分圆序列的自相关值 . 16 相关理论 . 16 自相关值 . 16 第三章 四阶广义分圆集合的 期和 . 23 相关理论 . 23 期 . 23 . 29第四章 (3)六阶分圆序列的线性复杂度. 41 引言 . 41 三阶 期 . 42 六阶 期 . 46 第五章 周期为11的 义分圆序列的线性复杂度 . 60 引言 . 60 周期为11q 的广义分圆序列 . 62 四阶广义分圆集合的一点结果 . 67 应用 . 72 期为 的四阶广义分圆序列 . 周期为11 的四阶广义分圆序列 .六章 总结与展望 . 77 参考文献 . . 78致 谢 . . 81在学期间的研究成果及发表的学术论文 . 82 1)(1)/16 为偶数 .1)(1)/16 为奇数 . 阶分圆数表 . 有满足03 D 的素数 10000p .(f 且 64时六阶分圆数模三 .(f 且 61A a时六阶分圆数模三 . (f ，33 D . (f ，03 D .1第一章 绪论 随机序列的研究背景、发展现状及构造原则 随机序列的研究背景 在现如今计算机科学和数字通信飞速发展的时代，伪随机序列在信号模拟、软件测试、全球定位系统、测距系统、码分多址系统、雷达系统、扩频通信系统以及流密码学等领域都有着广泛的应用。 关于序列伪随机性的刻画指标包括：序列的周期，线性复杂度，相关性（自相关性与互相关性） ，平衡性，稳定性等等。不同的应用背景下对伪随机序列的要求有所不同。通常在测距、导航和一般通信系统中应用时重点考虑它的自相关性质，而在保密通信系统和流密码学上则需要重点考察它的线性复杂度。因此，构造具有低自相关值的序列和具有大线性复杂度的序列有着重要的现实意义。 密码学分为私钥密码学和公钥密码学，私钥密码学主要用于信息加密。序列密码作为一种私钥密码体制，它的安全性主要取决于密钥流序列的随机性，设计具有良好随机性的序列是序列密码的重要内容，一般的要求是具有长周期、大线性复杂度、平衡和易于实现等。现有的几乎所有的公钥密码体制中，如 钥交换协议、数字签名标准、椭圆曲线公钥密码体制等都需要随机数。钥算法在产生私钥时也需要随机数。而伪随机序列生成器可以作为伪随机数生成器，其基本要求是序列具有良好的串分布性质。因此，伪随机序列既可以作为序列密码体制的密钥流，又可作为公钥密码体制的伪随机数生成器。 随机序列的发展历史 如果一个序列，一方面它是可以预先确定的，并且是可以重复的生产和复制的；另一方面它又具有某种序列的随机特性（即统计特性） ，我们便称这种序列为伪随机序列。伪随机序列的理论研究与应用大约分为三个阶段： （1）纯粹理论研究阶段（大约 1948 年以前）;（2）m 序列研究的黄金阶段（1948； （3）非线性生成器的研究阶段（1969-） 。 1948 年以前，学者们研究伪随机序列的理论仅仅是因为其优美的数学结构。最早的序列可追溯到 1894 年，作为一个组合问题来研究所谓的 列；上世纪 30 年代，环上的线性递归序列则成为人们的研究重点。 1948 年，息论诞生后，这种情况发生了改变。伪随机序列已被广泛的应用在通信和密码学等重要的技术领域。明了“一次一密”是无条件安全的，无条件保密的2密码体制要求进行保密通信的密钥量至少与明文量一样大。因此在此后的很长一段时间内，学者们致力于具有足够长周期的伪随机序列。如何产生这样的序列是 20 世纪 50 年代早期的研究热点。线性反馈移位寄存器序列（这个时期研究最多的，因为一个 n 级 以产生周期为 21n 的最大长度序列，而且具有满足 机性假设的随机特性，通常称之为 段时期的研究奠定了 列的基本理论和一些经典结论。 但是，自 1969 年 表了“移位寄存器综合与 码”一文，便引发了序列研究方向的根本性变革，从此伪随机序列的研究进入了构造非线性序列生成器的阶段。法（简称 法）指出：如果序列的线性复杂度为 n，则只需 2n 个连续比特就可以恢复出全部的序列。从这个结论可以看出，m 序列是一种“极差”的序列，它的线性复杂度太小，因而不能够直接用来做流密码系统的密钥流序列。从这里还可以看到仅仅靠三个随机性假设来评测序列还是不够的，还需要其他的一些指标。从此，密码学界的学者们一直在努力寻找构造“好”的伪随机序列的方法。 随机序列的研究现状 迄今为止，人们获得的伪随机序列仍主要是 控）序列，移位寄存器序列（m 序列和 ，列，列，级联 列，列，列，列。 其中 m 序列是研究最透彻的序列。它是平衡序列，具有理想的自相关特性，m 序列的个数很少，且线性复杂度很小。M 序列虽拥有大量序列，但其生成困难，且互相关特性目前知之甚少。列互相关函数为 3 值，序列部分平衡，有良好的相关特性，族序列数相对较大，但它有致命的弱点， 线性复杂度很低， 仅是相同长度的 m 序列的两倍， 这制约了 列的广泛应用，特别市在抗干扰和密码学中的应用。列具有序列平衡，线性复杂度大，自相关性能良好（同 m 序列）等优点。它是非线性序列，且数量比 m 序列多。作为单个序列 列具有优势，但一族 列满足一定互相关条件的序列很少，一般不用于码分多址系统。级联 列的平衡性和自相关性同于 列，族数比 列多，一般情况下，线性复杂度比 列大。列分小集 列和大集 列。小集 列族数大，且互相关值达到 ，大集 列族序列数非常大，互相关性较小集 列为劣。他们都有共同的弱点：序列是不平衡且线性复杂度不大。列是 80 年代初构造出来的，具有序列平衡，相关值达 ，族序列数多，线性复杂度大等优点。它在整个 80 年代,90 年代大放光芒，也是目前综合性能最好的伪随机序列。但 列构造很难，未有满足一定条件的快速算法。列是 80 年代末构造出来的一种新型伪随机序列，它的突出优点的线性复杂度很大，且相关值可达 ，族序列数多，但有序列不平衡的缺点。 随机序列的构造 就目前而言，伪随机序列的构造方法可分为两大类：一是基于数学理论的构造，二是基于性移位寄存器）的构造。两种构造方法各有优缺点。前者在理论上容易分析序列的随机性质，但往往不容易实现或者实现的代价比较高；而后者则恰恰相反，易于实现，实现的成本低，但在某些情况下不容易分析其随机性质。 基于数学理论构造伪随机序列又可分为两类：基于数论的构造和基于有限域的构造。前者利用的数学工具主要是二次剩余理论和分圆理论，利用该方法构造的序列主要有：列，列，m 序列，差集序列和割圆序列等。后者利用的数学工具主要是迹函数，代表序列有：列，列和椭圆曲线序列等。利用分圆理论构造的伪随机序列，一般称为分圆序列。一般基于数学理论的构造着重于考察序列的自相关性及线性复杂度。本文主要着重数学理论的研究。相关文献有： 7- 20等等,主要利用分圆集合（或广义分圆集合）构造二元序列并计算序列的线性复杂度或自相关值。当然，还有其他的一些理论构造方法及研究，例如：文献21-26。关于序列线性复杂度的考察，与寻找差集是异曲同工的，找到差集即等价于找到最佳自相关值的序列，关于差集的文章有：27-29。 究背景及相关结果介绍 典分圆 分圆是基础数论中一个古老的话题，如今已经广泛应用于流密码学和编码理论中。 先在他的 (1)中介绍了经典分圆。迄今为止，直到 24 阶的经典分圆数已经给出（详细可参考 2,3,4,5） 。下面介绍经典分圆的相关概念。 令 ，其中 p 为奇素数，则*循环群，设生成元为 g 。令 :()表示 g 模 () 1p。设 1p ，其中 1e 和 f 为正整数。 定义 :0,1,1es f ， 0,1, 2, （ 则有 *01 1D D ， *0 （ 相应的 (, ) |( 1) | D ，对所有的 ,0,1,1ij e 。 义分圆 1962 年， 为寻找差集给出广义分圆的概念。并给出两类广义分圆数： 2e 与4e 。下面介绍广义分圆的相关概念，并给出 于分圆数的一些结果。 4设 ， ,p 足 1, 1)p 。尽管 N 不存在原根，但是由中国剩余定理，模 ,p g 。令 :()表示 g 模 N 的阶，则 (1)(1)() ( (), () ( 1, 1)g g g p 。 设 (x 且 1(x q 。 6）定义 : 0,1, , 1, 0,1, , d i e（ 若定义 0, ,2 , ,( 1) , ,2 , ,( 1) R （ 则有 *01 1,D 相应的 (, ) |( 1) | D ，对所有的 ,0,1,e 引理 设 ， ,p 足 1, 1)p 。当 2e 时，我们有以下两种情况的二阶分圆数： 1) 3() ，即 (1)(1)/4为奇数时， 2(2)(2)1(0,0)4 ，222(2)(2)3(0,1) (1,0) (1,1)4 ； 2) 2 3() ，即 (1)(1)/4为偶数时， 222(2)(2)1(0,0) (1,0) (1,1)4 ，2(2)(2)3(0,1)4 。 设 ， ,p 足 1, 1)p 。当 4e 时，由 一个经典的定理，我们有 N 的两个分解式： 22 2 24, 4Na b ， 1() （ 引理 设 ， ,p 足 1, 1)p 。当 4e 时，十六个四阶广义分圆数4(, ) ,0,1,2,3，唯一的取决于（ 中的一个分解式， 表 (1)(1)/16 为偶数 01230ABCD1 EEDB2 AEAE3EDBE5表 (1)(1)/16 为奇数 01230ABCD1 BDEE2CECE3DEEB若 (1)(1)/16 为偶数，则表一中， 823 ， 8421 ，832 1 ， 8421 ， 821 ，其中 ,，(2)(2)14 。 若 (1)(1)/16 为奇数，则表二中， 832 5， 8421 ，821 ， 8421 ， 821 ，其中 ,，(2)(2)14 。 注 ：在引理 ，分圆数与（ N 的表达式相关， g 的不同选取可能导致分圆数与 , 果我们固定 g ，至今我们不能确定引理 的分圆数与（ 的哪个分解式有关，本文将给出 5( ， ( 1), ( 1) 4pp 情形下，四阶广义分圆数取分解式224b ， 4|究背景 伪随机序列是密切相关的，并且在信息中也有着广泛的应用。例如 在直接扩频 统中，我们需要区分不同使用者的信号，此时我们就需要利用具有接近 的于 构造，如今已有颇多研究，丁存生教授 36利用 集构造了几类 些 很接近 ，其中利用上二阶广义分圆集合构造的： 定义 设 (,)G 为一个 N 阶交换群，01 1,N 表示 G 的所有加法特征。给定 G 的任何一个 K 元子集合12: , , , d ，我们都可以定义一个 6: : 0,1 , 1 ， （ 其中对每个 i (0 1) ,121: (),(),() 。 定理 设 3()p 和 4为素数， 则对于 (,) 的 集1 定义的 ( ( 4),( 3)( 1) / 2)pp p p我们有 。 列的线性复杂度 线性复杂度与线性移存器关系密切，如果在信道中截获了连续的一些二元信号，我们想猜出它是由何种线性移存器生成的，并且我们的问题是求出一个最小的线性移存器，使得它能够生成这个二元周期序列，这时我们就需要求出此序列的线性复杂度。对于周期序列的线性复杂度的研究，毫无疑问，历来研究颇多，但很多研究可能都局限于周期为素数 p 。但是在 2011年，V. 给出一类周期为1 （ 0n ）二元广义分圆序列的线性复杂度，其计算方法非常巧妙。 设 1为奇素数， 其中 ,且令 g 为模1原根。 设0()为*,0,1,1d ， | ， 0,1, , 。定义00 ，其中集合 0,1, , 1d 的任何一个子集。 定义序列为： 1, (m ,0, 若，否则（ 令0()为*子群， 为 (2)域中的一个 p 次本原单位根。0()x。对每个 0,1, , ，设 | | ( ) 0, 0,1, , 1|h d ，| | ( ) 1, 0,1, , 1|h d 。，以及对每个 0,1, , 1 ，定义711, | | 0(), | | 1()若若定理 设周期为1 的序列如（ 定义，那么对任意 0n ，它的线性复杂度为：10 ，其中000, | | 0(),1, | | 1()若若。 文的主要研究工作 本文在前人的基础上，结合 广义分圆集合以及前人的构造方法，得到了具有良好性质的两类可达到较好相关值的 类二元伪随机序列及一类三元分圆序列。本篇文章的核心是利用 得到两类接近 的 计算了一类周期为 p 的不平衡的三元分圆序列的线性复杂度，并且推广了 V. 于周期为1 （ 0n ）二元广义分圆序列的线性复杂度的计算，得到了周期为11 的二元序列线性复杂度的一般公式。下面我们将简要阐述本文的主要结果： 在第二章中，我们利用 阶广义分圆集合构造一类周期为 的二元序列，这里 ,p 且满足 1, 1) 4， 然后计算该序列的线性复杂度， 讨论 ,p 得该序列具有较好的自相关值。 在第三章中，设 ， ,p 1, 1) 4的不同奇素数， ,i 0,1, 2,3 的定义如（ 和（ 。 设21/ 为一个 N 次本原单位根。定义()为：对每个，有() 2 1/() 。则 (,) 的所有加法特征为：():0 1 。 定理 令13为 (,) 的一个子集合。则(): ， 01 ，为(,) 的所有加法特征。则对于由定义（ 参数为(1)(1)(, )2的 我们有 81, ) ,11| | , ) ,1|1 |, ) 1.(1)( 1)i j N 若若若此外，我们还得到 ()，若，若注： 我们知道一个参数为 (,( 1)( 1)/2)pq p q 的 为 1.( 1) ( 1)( 1)( 1)NK pq p q在定理 ，若 p ， |p q 足够小，即 p ， 将很接近 。若 4 ，由文献 10知道 时 将几乎达到 类似地，我们还可构造两类由（ 定义的 中 01 或123 ， 并计算出其相关值。 当我们适当选取参数 ,p 也可使其接近 在第四章中， 构造了两类非平衡的 3 序列并计算出其线性复杂度。 设 1()p ， p 的原根，60()为*子群，0， 0,1, ,5i 。003 ，114 ，225 。 定义三阶分圆 3 序列为01, ,若，否则（ 定理 设序列 （ 定义，适当选取 p 次单位根 ， （ 1）若03 C 且 1(p ，则13 ，2() ()sf 。 9（ 2）若03 C 且 4(p ，则 ， () 1 。 （ 3）若03 C 且 7(p ，则213 ，01()() 。 （ 4） 若03 C 且 1(p ， 则 1 ，012() () () ()sf ； 若03 C 且 9/| 1p 。则 ， () 1 。 其中 () ( )x， 0,1, 2i 。 定义六阶分圆 3 序列为01, ,0, 若否则（ 定理 设 61p f， f 为正整数，为奇素数且033 ，序列 （ 定义。 （ 1）若 19 (6)p ，则 ( 1) / 3, 2 0 ();2( 1) / 3, 2 1 ();2( 1) / 3, 2 2 () 若若若252503() (), 2 0(1() , 2 1() ()( 1)1,22() ()( 1) 若若若（ 2）若 31 (6)p ，则 ， () 1 。 （ 3）若 7(p ，则 ,20(2( 1) / 3 1, 2 1 ();2( 1) / 3 1, 2 2 () 若若若1003031 , 2 0 ();1() , 2 1() ()1,22() () 若若若（ 4）若 1(6)p ，则 ( 1) / 6, 2 0 ();2( 1) / 3, 2 1 ();2( 1) / 3, 2 2 () 若若若51403(), 2 0(1() , 2 1() ()( 1)1,22() ()( 1) 若若若（ 5）若 13 (6)p ，则 5( 1) / 6 1， 0121,20()1() , 2 1()1,22() 若若若（ 6）若 7(p ，则 ,20(1)/21, 21(1)/21, 22( 若若若110130231 , 2 0 ();1() , 2 1() () ()1,22() () () 若若若其中 () ( )x， 05i。 定理 设 61p f， f 为正整数，为奇素数且033 ，序列 s 由（ 定义。 （ 1）若243 ，则 03( 1) / 2, 1 (6) 2 ;1, .p 若且否则030241, 1 (6) 2 ;() () ()()1,.(1 ) 若且否则（ 2）若153 ，则 1，1()(1 )，其中 0, 1 ();1, 若否则。 第五章主要推广了 V. 于计算周期为1 （ 0n ）二元广义分圆序列的线性复杂度的结果，得到了周期为11 ，其中 ,p q 为奇素数且( 1), ( 1)p e，的二元 义分圆序列的线性复杂度的一般公式。继而，设 5( 为不同的奇素数，且满足 ( 1), ( 1) 4pp ， g 是模 p 和模 们给出 阶广义分圆数取决于 两个分解式224b 中 4|后，设 4e ，具体计算出两类序列的线性复杂度。 假设11 ， p ， ( 1), ( 1) 1, 1)pq e 的不同奇素数，(1)(1) 。 g 为模1模1公共原根。由文献 8，我们有下面的关系12式： 111*0，111*0，其中11*0 ，11*0 。 若 且 j n ，则*| ij qZ ， 0,1, 1 。因此 111* 1 *000 0 0m in m i jZ p ， 其中11*0 。为方便起见，我们定义 1*(, )1*,0 1,1,0,1,0, 1, 1, i m j n k i m j n im jn k 若若若若， 因此对任意的 ，(, 1) 1 *0in i ，对任意的 j n ，(1,) 1 *0mj m ，且(