徐玉春，王錦玲

（1.鄭州鐵路職業(yè)技術(shù)學(xué)院，河南 鄭州 451460；2.鄭州大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，河南，鄭州，450001）

0 引 言

信息時(shí)代中，偽隨機(jī)序列被廣泛應(yīng)用于通信領(lǐng)域，而序列密碼的設(shè)計(jì)準(zhǔn)則總是高度安全和簡(jiǎn)單結(jié)構(gòu)的統(tǒng)一。Willi Meier[1]提出的自縮序列因結(jié)構(gòu)簡(jiǎn)單而引人入勝，頗受關(guān)注；胡予璞等人在此基礎(chǔ)上又給出了廣義自縮序列的定義，并在GF（2）上研究并證明了此定義下廣義自縮序列的許多密碼學(xué)性質(zhì)，如0-1分布的均衡性等[2-6]。本文則在GF（3）上討論兩類廣義自縮序列的偽隨機(jī)性質(zhì)，得到這兩類序列的游程分布及其一致且近似相等，且最小周期都達(dá)到最大2·3n-2。

定義1：設(shè)a∞=a0a1a2……是GF（3）的n級(jí)m-序列，其周期為3n-1?，F(xiàn)定義兩類廣義自縮序列如下：

①如果ak=1，則輸出ak-2；如果ak=2，則輸出ak-2+ak+1；否則，不輸出；

②如果ak=1，則輸出ak-2；如果ak=2，則輸出ak-2+ak-1+ak+1；否則，不輸出；

把由①得到的序列記為b1∞，把由②得到的序列記為b2∞

?？梢钥吹剑俸廷谑莾深惒煌敵鲂蛄?。為了使文章更精煉而又不影響讀者理解，現(xiàn)只對(duì)①序列的1長(zhǎng)游程分布只列出1長(zhǎng)0-游程分布。記0m、0s分別為長(zhǎng)度m、s長(zhǎng)的0串，其中長(zhǎng)度m、s可以取0；“*”表示GF（3）上的任意值。

1 序列b∞的游程分布

首先考慮序列b1∞的長(zhǎng)度為1的0-游程。

引理1：設(shè)某個(gè)固定的t，使得at=at-2=0，此時(shí)對(duì)應(yīng)序列b∞的一個(gè)輸出比特bs=at-2=0，且要得到序列b∞的長(zhǎng)度為1的0-游程。

當(dāng)且僅當(dāng)，在以下17種情形下得到101：

（1）1*100m0100s021（2）1*100m0101

（3）1*100m01020（4）1*100m0121

（5）1*200m0100s021（6）1*200m0101

（7）1*200m01020（8）1*200m0121

（9）101100m021（10）101101（11）1011020

（12）10111（13）101120（14）002100m021

（15）002101（16）0021020（17）002122

當(dāng)且僅當(dāng)，在以下17種情形下得到201：

（1）2*100m0100s021（2）2*100m0101

（3）2*100m01020（4）2*100m0121

（5）2*200m0100s021（6）2*200m0101

（7）2*200m01020（8）2*200m0121

（9）201100m021（10）201101（11）2011020

（12）20111（13）201120（14）102100m021

（15）102101（16）1021020（17）102122

當(dāng)且僅當(dāng)，在以下13種情形下得到102：

（1）1*100m0100s022（2）1*100m01021

（3）1*100m0122（4）1*200m0100s022

（5）1*200m01021（6）1*200m0122

（7）101100m022（8）1011021（9）101121

（10）002100m022（11）0021021（12）00211

（13）002120

當(dāng)且僅當(dāng)，在以下13種情形下得到202：

（1）2*100m0100s022（2）2*100m01021

（3）2*100m0122（4）2*200m0100s022

（5）2*200m01021（6）2*200m0122

（7）201100m022（8）2011021（9）201121

（10）102100m022（11）1021021（12）10211

（13）102120

引理2：設(shè)某個(gè)固定的t，使得at=2，at-1+at+2=0。此時(shí)，對(duì)應(yīng)序列b∞的一個(gè)輸出比特bs=at-1+at+2=0，且要得到序列b∞的長(zhǎng)度為1的0-游程。

當(dāng)且僅當(dāng)，在以下12種情形下得到101：

（1）1*100m0200s021（2）1*100m02022

（3）1*200m0200s021（4）1*200m02022

（5）101200m021（6）1012022（7）202200m021

（8）2011022（9）1*10221（10）111220

（11）212222（12）12121

當(dāng)且僅當(dāng)，在以下12種情形下得到201：

（1）2*100m0200s021（2）2*100m02022

（3）2*200m020021（4）2*200m02022

（5）201200m021（6）2012022（7）002200m021

（8）0022022（9）2*0s10221（10）211220

（11）012222（12）22121

當(dāng)且僅當(dāng)，在以下16種情形下得到102：

（1）1*100m0200s022（2）1*100m0201

（3）1*100m02020（4）1*200m0200s022

（5）1*200m0201（6）1*200m02020

（7）101200m022（8）101201（9）1012020

（10）202200m022（11）202201（12）2022020

（13）1*10222（14）111221（15）212220

（16）22221

當(dāng)且僅當(dāng)，在以下16種情形下得到202：

（1）2*100m0200s022（2）2*100m0201

（3）2*100m02020（4）2*200m0200s022

（5）2*200m0201（6）2*200m02020

（7）201200m022（8）201201（9）101200m20

（10）002200m022（11）002201（12）0022020

（13）2*10222（14）211221（15）012220

（16）02221

定理1：設(shè)序列b1∞的長(zhǎng)度為1的0-游程的個(gè)數(shù)為u，則：

以同樣的分析方法，得：

定理2：設(shè)序列b1∞的長(zhǎng)度為1的1-游程的個(gè)數(shù)為u，則：

定理3：設(shè)序列b1∞的長(zhǎng)度為1的2-游程的個(gè)數(shù)為u，則：

定理4：設(shè)序列b2∞的長(zhǎng)度為1的0-游程的個(gè)數(shù)為u，則：

定理5：設(shè)序列b2∞的長(zhǎng)度為1的1-游程的個(gè)數(shù)為u，則：

定理6：設(shè)序列b2∞的長(zhǎng)度為1的2-游程的個(gè)數(shù)為u，則：

2 序列b∞的最小周期

引理3：在輸出序列b∞的一個(gè)周期P內(nèi)，若有k長(zhǎng)1-游程出現(xiàn)的次數(shù)為N，且滿足gcd(N,P)=1，則P是序列b∞的最小周期。

證明：參見文獻(xiàn)[7]。

為了得到序列b1∞的最小周期，由序列b1∞游程分布可得：

引理4：輸出序列b1∞中出現(xiàn)n+1長(zhǎng)的1-游程時(shí)，m-序列a∞中有以下一種情況出現(xiàn)：

引理5：輸出序列b1∞中出現(xiàn)n長(zhǎng)的1-游程時(shí)，m-序列a∞中有以下一種情況出現(xiàn)：

定理7：m-序列a∞控制輸出的序列b1∞有最小周期2×3n-1。

證明：由輸出序列的形式可知，2×3n-1是輸出序列b1∞的一個(gè)周期。又由m-序列a∞中沒有大于n長(zhǎng)的1-游程，故考慮以下幾種情況。若序列b1∞在一個(gè)周期2×3n-1中出現(xiàn)了n+1長(zhǎng)的1-游程，則一定是在引理4中m-序列a∞控制輸出的比特串中出現(xiàn)，因m-序列a∞中n長(zhǎng)1-游程僅出現(xiàn)一次，故比特串在m-序列a∞中有且僅有其中之一出現(xiàn)；若序列b1∞在一個(gè)周期2×3n-1中出現(xiàn)了n長(zhǎng)的1-游程，則一定是在引理5中m-序列a∞控制輸出的比特串中出現(xiàn)。由m-序列性質(zhì)知，（1）（2）與（3）（4）不能同時(shí)出現(xiàn)。由線性遞歸序列的表達(dá)式知，（1）（2）在m-序列a∞中有且僅有其中之一出現(xiàn)；同理，（3）（4）也如此。于是，可知序列b1∞中出現(xiàn)的n長(zhǎng)的1-游程僅出現(xiàn)一次。再由引理3可知，2×3n-1是輸出序列b∞的最小周期。

定理8：m-序列a∞控制輸出的序列b2∞有最小周期2×3n-1。

證明：同定理7的證明方法，要先分析序列b2∞中最長(zhǎng)的1-游程，根據(jù)1-游程的個(gè)數(shù)與2×3n-1互素得序列b2∞的最小周期為2×3n-1。

3 結(jié) 語

先列出GF（3）上幾類廣義自縮序列的輸出序列與本文的一類廣義自縮序列在最小周期都達(dá)到2×3n-1內(nèi)的游程分布情況表，如表1所示。

表1 本文游程分布情況與其他文獻(xiàn)游程分布情況

從表1可以看到，本文構(gòu)造的兩類廣義自縮序列長(zhǎng)游程少，0、1、2游程分布均勻。研究表明，這兩類廣義自縮序列b∞暴露的驅(qū)動(dòng)信息少，對(duì)驅(qū)動(dòng)序列a∞有很高的保護(hù)強(qiáng)度，適合在通信和計(jì)算機(jī)編碼系統(tǒng)中應(yīng)用,并與GF（3）上其他廣義自縮序列相比具有更好的密碼學(xué)特性[8-11]。