Magma在伪随机序列中的应用

2018-01-09刘龙飞

科教导刊·电子版 2017年32期

刘龙飞

摘要伪随机序列由于其在，常见的伪随机序列有m序列、legendre序列等，而广义割圆序列是Legendre序列的扩展，具有良好的线性复杂度和自相关性质。本文介绍了Magma在伪随机序列方面的测试与应用，可以使抽象的证明直观化，复杂的计算简单化，从而使验证广义割圆序列的正确性。

关键词 Magma 伪随机序

中图分类号：TN918.2 文献标识码：A

0前言

由于伪随机序列具备良好的随机性，目前已广泛应用于各个领域。特别是在密码学中，伪随机序列扮演着十分重要的角色。随机序列具有两个方面的特点：一是预先不可确定、不可重复实现。另一方面所有序列都具有某些共同的随机特性。能否产生真正的随机序列一直都处在激烈的争论中，如果一个二元序列，一方面它的结构是可以预先确定的，并且可以重复的产生和复制；另一方面又满足Golomb总结的三条随机性假设：R1 若序列的周期L为偶数，则0的个数与1的个数相等；若L为奇数，则0的个数比1的个数多1或少1。R2 长为的串占1/2，且0串和1串的个数相等或至多差一个。R3 序列的异相自相关函数为一个常数，即序列为二值自相关序列。便称这种序列为伪随机序列。简单的讲，伪随机序列就是具有某种随机特性的确定序列。它不是真正的随机序列，它是用确定的算法产生，可以由短的真随机序列扩展成较长的伪随机序列。

1 Magma在伪随机序列中的应用

使用Magma计算伪随机序列的线性复杂度和自相关函数，主要利用Magma的BerlekampMassey函数以及AutoCorrelation函数。

令p为奇素数，整数m≥1。若g是p2的本原元，并且g'≡g（modp）并且满足g'≡g（modp），则对于任意n≥2，g是pn的本原元，g'是p的本原元。则根据中国剩余定理可得，g模p的阶为p-1，g模pm的阶为pm-1（p-1）。

对于任意n，1≤n≤m，定义

D=（g2）（modpn），

D=gD（modpn），

R（n）={0，p，2p，…，（pn-1-1）p}=pZ，

则R（n）=Z＼Z*， Z*=D∪D。

对于任意n1，n2，（n1

D（modp）≡D，R（modp）≡R .

因此可得到剩余类环Z的一个分割为：

Z=D∪D∪pZ

。

1997年，Ding基于Whiteman-广义割圆类构造了一类具有良好伪机性质的序列，并证明了其具有很高的线性复杂度。1998年，Ding和Helleseth提出了新的广义割圆类，实现了对剩余类环最大乘法子群的分割，并定义了新的二元序列（简称Ding-广义割圆序列）。该类序列典型代表为周期为pq（p，q为素数）和周期为pm（p为奇素数，m为正整数）的情形。本文中，我们对经典的周期为p2的广义割圆序列进行验证。

例2：

//D-2

E：=GF（2）；

P：=PolynomialRing（GF（2））；

p：=x^12 + x^7 + x^6 + x^5 + x^3 + x + 1；

F：=ext；

F；

sum：=0；

s：=[]；

P：= [1， 4， 16， 17， 38， 46， 47， 62， 64， 68， 79， 83， 11， 13， 29， 44， 52， 71， 73， 74， 82， 86， 97， 103]；

Q：=[]；

for i in [1..21] do