Magma在伪随机序列中的应用 Magma在伪随机序列中的应用 刘龙飞摘 要 伪随机序列由于其在，常见的伪随机序列有m序列、legendre序列等，而广义割圆序列是Legendre序列的扩展，具有良好的线性复杂度和自相关性质。本文介绍了Magma在伪随机序列方面的测试与应用，可以使抽象的证明直观化，复杂的计算简单化，从而使验证广义割圆序列的正确性。Key Magma 伪随机序：TN918.2 ：A0前言由于伪随机序列具备良好的随机性，目前已广泛应用于各个领域。特别是在密码学中，伪随机序列扮演着...
刘龙飞
摘 要 伪随机序列由于其在，常见的伪随机序列有m序列、legendre序列等，而广义割圆序列是Legendre序列的扩展，具有良好的线性复杂度和自相关性质。本文介绍了Magma在伪随机序列方面的测试与应用，可以使抽象的证明直观化，复杂的计算简单化，从而使验证广义割圆序列的正确性。
Key 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
Z
。
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
Q[i]：=17*i；
end for；
Q；
for i in [1..#Q] do
s[i]：=w^Q[i]；
sum：=sum+s[i]；
end for；
printf "sum=%o"，sum；
通過测试可得最后的sum值为0，与数学证明的结果相符。
2总结
本文通过对Magma进行学习，可以看到利用Magma来进行伪随机序列的实验结果，仿真测试抽象的数学结论，使其更加直观化，使繁琐的计算简单化。最后，针对当前的热点方向广义割圆序列进行仿真验证。
Reference
[1] Ding，C.Linear complexity of generalized cyclotomic binary sequences of order 2[J]. Finite Fields and Their Applications，1997，3（02）：159-174.
[2] Ding，C&T.Helleseth .New generalized cyclotomy and its applications[J]. Finite Fields and Their Applications，1998，4（02）：140-166.
[3] Cusick，T.W.&C.Ding&A.Renvall.Stream Ciphers and Number Theory[M].Elsevier Science Pub. Co，1998.
[4] 宋蔷薇，李录苹. Magma在近世代数中的应用[J].山西大同大学学报，2015，31（01）：6-8.
[5] 金桂梅，李永冰.伪随机序列的仿真与分析[J].现代电子技术，2009， 301（14）：103-106.
-全文完-
浙公网安备 33021202002483