GF（3）上兩類廣義自縮序列的偽隨機性*

徐玉春，王錦玲

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

0 引 言

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

定義1：設(shè)a∞=a0a1a2……是GF（3）的n級m-序列，其周期為3n-1。現(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)只對①序列的1長游程分布只列出1長0-游程分布。記0m、0s分別為長度m、s長的0串，其中長度m、s可以取0；“*”表示GF（3）上的任意值。

1 序列b∞的游程分布

首先考慮序列b1∞的長度為1的0-游程。

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

當且僅當，在以下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

當且僅當，在以下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

當且僅當，在以下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

當且僅當，在以下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è)某個固定的t，使得at=2，at-1+at+2=0。此時，對應(yīng)序列b∞的一個輸出比特bs=at-1+at+2=0，且要得到序列b∞的長度為1的0-游程。

當且僅當，在以下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

當且僅當，在以下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

當且僅當，在以下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

當且僅當，在以下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∞的長度為1的0-游程的個數(shù)為u，則：

以同樣的分析方法，得：

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

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

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

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

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

2 序列b∞的最小周期

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

證明：參見文獻[7]。

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

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

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

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

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

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

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

3 結(jié) 語

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

表1 本文游程分布情況與其他文獻游程分布情況

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