Magma在偽隨機序列中的應用

劉龍飛

摘 要 偽隨機序列由于其在，常見的偽隨機序列有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

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來進行偽隨機序列的實驗結果，仿真測試抽象的數學結論，使其更加直觀化，使繁瑣的計算簡單化。最后，針對當前的熱點方向廣義割圓序列進行仿真驗證。

參考文獻

[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.