Magma在偽隨機(jī)序列中的應(yīng)用

劉龍飛

摘 要 偽隨機(jī)序列由于其在，常見的偽隨機(jī)序列有m序列、legendre序列等，而廣義割圓序列是Legendre序列的擴(kuò)展，具有良好的線性復(fù)雜度和自相關(guān)性質(zhì)。本文介紹了Magma在偽隨機(jī)序列方面的測(cè)試與應(yīng)用，可以使抽象的證明直觀化，復(fù)雜的計(jì)算簡單化，從而使驗(yàn)證廣義割圓序列的正確性。

關(guān)鍵詞 Magma 偽隨機(jī)序

中圖分類號(hào)：TN918.2 文獻(xiàn)標(biāo)識(shí)碼：A

0前言

由于偽隨機(jī)序列具備良好的隨機(jī)性，目前已廣泛應(yīng)用于各個(gè)領(lǐng)域。特別是在密碼學(xué)中，偽隨機(jī)序列扮演著十分重要的角色。隨機(jī)序列具有兩個(gè)方面的特點(diǎn)：一是預(yù)先不可確定、不可重復(fù)實(shí)現(xiàn)。另一方面所有序列都具有某些共同的隨機(jī)特性。能否產(chǎn)生真正的隨機(jī)序列一直都處在激烈的爭論中，如果一個(gè)二元序列，一方面它的結(jié)構(gòu)是可以預(yù)先確定的，并且可以重復(fù)的產(chǎn)生和復(fù)制；另一方面又滿足Golomb總結(jié)的三條隨機(jī)性假設(shè)：R1 若序列的周期L為偶數(shù)，則0的個(gè)數(shù)與1的個(gè)數(shù)相等；若L為奇數(shù)，則0的個(gè)數(shù)比1的個(gè)數(shù)多1或少1。R2 長為的串占1/2，且0串和1串的個(gè)數(shù)相等或至多差一個(gè)。R3 序列的異相自相關(guān)函數(shù)為一個(gè)常數(shù)，即序列為二值自相關(guān)序列。便稱這種序列為偽隨機(jī)序列。簡單的講，偽隨機(jī)序列就是具有某種隨機(jī)特性的確定序列。它不是真正的隨機(jī)序列，它是用確定的算法產(chǎn)生，可以由短的真隨機(jī)序列擴(kuò)展成較長的偽隨機(jī)序列。

1 Magma在偽隨機(jī)序列中的應(yīng)用

使用Magma計(jì)算偽隨機(jī)序列的線性復(fù)雜度和自相關(guān)函數(shù)，主要利用Magma的BerlekampMassey函數(shù)以及AutoCorrelation函數(shù)。

令p為奇素?cái)?shù)，整數(shù)m≥1。若g是p2的本原元，并且g'≡g（modp）并且滿足g'≡g（modp），則對(duì)于任意n≥2，g是pn的本原元，g'是p的本原元。則根據(jù)中國剩余定理可得，g模p的階為p-1，g模pm的階為pm-1（p-1）。

對(duì)于任意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。

對(duì)于任意n1，n2，（n1

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

因此可得到剩余類環(huán)Z的一個(gè)分割為：

Z=D∪D∪pZ

Z

。

1997年，Ding基于Whiteman-廣義割圓類構(gòu)造了一類具有良好偽機(jī)性質(zhì)的序列，并證明了其具有很高的線性復(fù)雜度。1998年，Ding和Helleseth提出了新的廣義割圓類，實(shí)現(xiàn)了對(duì)剩余類環(huán)最大乘法子群的分割，并定義了新的二元序列（簡稱Ding-廣義割圓序列）。該類序列典型代表為周期為pq（p，q為素?cái)?shù)）和周期為pm（p為奇素?cái)?shù)，m為正整數(shù)）的情形。本文中，我們對(duì)經(jīng)典的周期為p2的廣義割圓序列進(jìn)行驗(yàn)證。

例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；

通過測(cè)試可得最后的sum值為0，與數(shù)學(xué)證明的結(jié)果相符。

2總結(jié)

本文通過對(duì)Magma進(jìn)行學(xué)習(xí)，可以看到利用Magma來進(jìn)行偽隨機(jī)序列的實(shí)驗(yàn)結(jié)果，仿真測(cè)試抽象的數(shù)學(xué)結(jié)論，使其更加直觀化，使繁瑣的計(jì)算簡單化。最后，針對(duì)當(dāng)前的熱點(diǎn)方向廣義割圓序列進(jìn)行仿真驗(yàn)證。

參考文獻(xiàn)

[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在近世代數(shù)中的應(yīng)用[J].山西大同大學(xué)學(xué)報(bào)，2015，31（01）：6-8.

[5] 金桂梅，李永冰.偽隨機(jī)序列的仿真與分析[J].現(xiàn)代電子技術(shù)，2009， 301（14）：103-106.