M序列反饋函數多項式表示的快速構造方法

關杰，周琮偉

（解放軍信息工程大學三院，河南 鄭州 450001）

1 引言

一個n級移位寄存器至多產生周期為2n的序列，通常稱達到最大周期2n的序列為M序列，又叫De Bruijn序列。關于LFSR的圈結構已經可以完全刻畫，并且知道最大周期的2n-1的序列由其特征多項式為二元域上的本原多項式產生，此時，稱周期為2n-1的序列為m序列。相較于m序列，M序列有著更好的線性復雜度和自相關性質，一直以來其構造問題是序列密碼理論的研究熱點。由于NFSR的圈結構沒有較好的刻畫手段，故其構造的經典方法一直以來局限于圖論的反樹和因子關聯圖法[1]，小項表示的圈剪接篩法[2]和由一個M序列通過對稱[3]、派生[4]和遞歸[5]等得到一類M序列。近期，國外學者關于M序列的構造主要有“改進版”的Martin算法[6]以及關于D-同態遞歸構造的最新研究成果[7]。而國內學者關于M序列構造的新思路和研究主要有“編織法”[8]，利用復合函數所代表的寄存器因子關聯圖的研究構造M序列[9～13]以及針對大級數的并圈構造[14]。以上這些構造方法大致可以分為兩類，即同級直接生成的“并圈法”以及小級數遞歸生成大級數的“遞歸法”。但是“并圈法”生成的M序列往往需要大量的統計、判斷和檢驗，并且得到的M序列往往是以小項表示；而“遞歸法”往往得到的M序列個數較少且M序列往往與小級數的初始序列具有較大相關性。

因此，針對以上M序列在實際構造中存在的問題，本文提出了一類可以實際應用，且以多項式表示的M序列反饋函數的快速構造方法。

2 預備知識

以下是本文用到的定義和符號說明。

Gf：以f為反饋函數的n級移位寄存器的狀態圖。

對偶變換D：設為f產生的GF(2)上任意一條周期為T的序列，令“+”為GF(2)上的加法運算，則aT+1,…)。

對稱變換R：

組合變換RD：a1+1,… )。

Ai：f0(x2,…,xn)中所有i(0 ≤i≤n-1)次項的集合為Ai，特別地，零次項為 1以及最高次項為x2…xn。

常見的反饋函數有2種表示方法，即小項表示和多項式表示。在實際應用中，更實用的是用多項式表示的反饋函數，因為利用多項式表示的反饋函數其構造M序列無論從軟件和硬件實現的角度都更為方便快捷。文獻[15]給出了圈結構不含枝即非奇異的n級反饋函數，其用多項式表示3種函數變換的對應表達式。

定理 1[15]設非奇異n級反饋函數的多項式表示為f=x1+f0(x2,… ,xn)，若分別用Df、Rf和RDf表示以D(Gf)、R(Gf)和RD(Gf)為狀態圖的n級移位寄存器反饋反饋函數，則

1946年，De Bruijn從圖論的角度證明了產生M序列的非線性移位寄存器的個數等于而非奇異移位寄存器的個數恰好等于但是至今人們都無法證明M序列的非線性移位寄存器以2n的長度劃分了整個非奇異移位寄存器，即猜想若將整個非奇異移位寄存器對應的反饋函數看作一個群，而M序列的反饋函數可以看作是個數為2n的陪集的代表元。20世紀80年代，高鴻勛[16]在以圈剪接篩法的基礎上提出了一個非奇異反饋函數為M序列反饋函數的充要條件，但對于生成全部n(n≥ 5)級M序列來講沒有實際意義。

本文直接引用文獻[15]中關于M序列反饋函數多項式表示的一個必要條件來說明隨機尋找到一個M序列反饋函數的數據復雜度。

引理 1[15]在M序列反饋函數f0的多項式表示中，有以下性質。

1) 最高次項x2…xn這一項一定出現。

2) 項數一定是奇數。

3) 1這一項一定出現。

4) 一次項x2,…,xn不能全部出現。

由于考慮將1和x2…xn這2項排除，則剩余可能出現的項的個數即為 2n-1- 2 。在此基礎上將2n-1- 2 種可能出現的項進行一個分類，即定義Ai(1 ≤i≤n-2)，則可能產生M序列反饋函數的個數為 22n-1-2。又因為項數一定是奇數，則可能產生M序列的反饋函數的個數可以降到 22n-1-3。如果從線性項x2,…,xn不能全部出現的角度考慮，則可能產生M序列反饋函數的個數為假設M序列的反饋函數服從均勻分布，則實際利用引理 1尋找到一個M序列反饋函數的數據復雜度約為O(2n-3)。

文獻[15]給出了利用對偶變換D、對稱變換R和組合變換RD構造M序列的結論。如引理2所示。

引理2[15]f是M序列的反饋函數，則Df、Rf和RDf也是M序列的反饋函數。當n≥ 3 時，f≠Df、f≠Rf；當n為偶數時，f、Df、Rf、RDf這4個函數兩兩互異。

由于在實際應用中并不需要生成全部的M序列反饋函數，更多的時候是需要生成具有某些構造特點的多項式表示的反饋函數。本文的工作即是利用由m序列構造M序列反饋函數的結構特性，經上述 3種函數變換得到一類M序列反饋函數多項式表示的快速構造方法，為了更好地說明對偶變換D、對稱變換R以及組合變換RD在構造M序列反饋函數中的應用，接下來，給出2個關于m序列的結論。

3 由函數變換證明的2個結論

本文由函數變換發現了m序列個數及其特征多項式的一些性質，并從另外一個角度證明了如下結論。

引理3[17]當n≥ 3 ，總為偶數。

證明 當n≥ 3 時，由引理 2知，Rf形成的必然是一條新的m序列，則f≠Rf，因此，由Rf形成的特征多項式必然異于f的本原多項式，而二元域上的本原多項式的總數為因此，當必然為偶數，證畢。

定理2 當n為偶數且n≥ 3 時，不存在形式為的本原三項式。

證明 當n為偶數且n≥ 3 時，對于特征多項式

4 函數變換及函數派生在構造M序列反饋函數中的應用

4.1 函數變換在構造M序列反饋函數中的應用

在實際構造M序列的過程中，人們很自然地考慮從m序列出發，即考慮在m序列長度為n-1的0游程中添加一個0得到M序列，這也符合對M序列的游程統計。這種情況構造的M序列反饋函數其實是在m序列的反饋函數表達式中添加一個小項當然將小項表示轉化為多項式表示中，發現得到的M序列反饋函數滿足引理1的性質，考慮該M序列反饋函數的對偶函數時，其對偶函數也應該為M序列的反饋函數，據此給出了一類M序列反饋函數f快速構造的多項式表示的形式，即形式1。

形式 1 在m序列的反饋函數q的基礎上添加這2項，即

容易看出，具有形式1的多項式表示的反饋函數f滿足引理1，從而可以推出m序列的項數為偶數項，否則與f中出現1這一項相矛盾。

同時考慮對稱函數Rf和RDf，當n≥ 3 ，由f對稱所形成的必然是新的一條M序列，所以勢必由f可以得到一個新的滿足M序列的反饋函數Rf，觀察其結構可知，仍然是在m序列的反饋函數上添加 1,x2…xn這2項，其與引理3的結論是相對應的，同理可得RDf與Df具有相同結構。據此，可以快速構造個M序列反饋函數。

如果本文將x1,1,x2…xn這3項單列，指出任意由形式1構造的M序列反饋函數的對偶函數Df具有定理3的形式。

定理3 任意由形式1構造的M序列反饋函數f的對偶函數Df具有以下形式。

1) 包含x1,1,x2…xn這3項。

2) 包含f在集合Ai(1 ≤i≤n-2)中所有未出現的項。

證明 由于f=q+1+x2…xn=x1+f0(x2,…,xn)，則由定理1知，Df包含項，其多項式展開式中包含f0(x2,…,xn)中所有i(1 ≤i≤n-2)次項的集合為Ai以及 1,x2…xn。

由于f0(x2,…,xn)中的線性項共有奇數項，故Df一定包含x1,1,x2…xn這3項，且其余項為f在集合Ai(1 ≤i≤n-2)中所有未出現的項，故式(1)和式(2)得證。證畢。

為方便理解，本文給出定理3的一個實例。

例1 當n= 4時，f=x1+1+x2x3x4+x4，下面給出Df。

由于原函數在Ai(1 ≤i≤2)中未出現的項有

x2,x3,x2x3,x2x4,x3x4，因此

同時，發現Df+f中的函數項即是集合Ai(1 ≤i≤n-2)中所有出現的 2n-1- 2 項，因此，可以立即得到推論1。

推論1對于任意由形式1構造的M序列反饋函數f和Df，g為任意M序列反饋函數，則f+Df+g具有如下形式。

1) 包含x1,1,x2…xn這3項。

2) 包含g在集合Ai(1 ≤i≤n-2)中所有未出現的項。

4.2 函數派生在M構造序列反饋函數中的應用

根據之前對基于由m序列構造M序列的分析可知，如果僅從A1選擇奇數項，只能是形式1構造出的個M序列反饋函數f，于是，設想以此為基礎加上若干偶數項可以構造新的M序列反饋函數。本先給出文獻[15]中一個關于函數派生的結論，文獻[15]中的證明比較煩瑣，下面，利用文獻[18]中狀態圖的連線與交點的賦值定義給出簡化證明。

定理4[15]若f是n級M序列的反饋函數，則以下2個式子也是M序列的反饋函數。

證明 文獻[18]指出，對于Gf狀態圖，任一2對共軛狀態的連線的交點的賦值和指的是加上2個n- 1 維的小項其中，與分別是2對共軛狀態。由圈剪接的思想[15]可知，f加上賦值和也是M序列的反饋函數。而2對共軛狀態的連線要相交，必然在Gf中一對共軛狀態之間有另一對共軛狀態的其中一個。對于狀態(0,0,1,…,1,1)來說，若其后繼狀態為(0,1,1,…,1,0)，由于((0,1,1,… ,1),(1,1,… ,1 ,1))這條弧必然存在，則狀態(0,1,1,…,1)的先導必然為(1,0,1,1,…,1)，且同時(1,1,…,1,1)的后繼必然為(1,1,…,1,0)，故形成這樣一條長弧((0,0,1,…,1,1),(0,1,1,…,1 ,0),…,(1 ,0,1,1,…,1),(0,1,1,…,1),(1,1,…,1,1),(1,1,…,1,0))，則說明共軛狀態(0,0,1,…,1,1),(1,0,1,1,…,1)和(0,1,1,…,1,0),(1,1,…,1,0)的連線必然相交；若其后繼狀態為(0,1,1,…,1)，則狀態(0,1,1,…,1,0)的先導必然為(1,0,1,1,…,1)，故形成這樣一條長弧((1,0,1,1,…,1),(0,1,1,…,1,0),…,(0,0,1,…,1,1),(0,1,1,… ,1),(1,1,…,1,1),(1,1,…,1,0))，則說明共軛狀態(0,0,1,…,1,1),(1,0,1,1,…,1)和(0,1,1,…,1,0),(1,1,…,1,0)的連線必然相交。綜上可知也是M序列的反饋函數。同理可證也是M序列的反饋函數，證畢。

下面，利用定理4的結論，給出了新的M序列反饋函數的4種形式

本文首先利用定理4的式(1)，即f是任意以形式 1構造的M序列反饋函數，則也是M序列反饋函數。

由此，可將f′描述成以下多項式表示的形式，即形式2。

形式 2 在形式 1生成的f基礎上添加這2項，即

而此時的f′正好滿足從A1選擇奇數項，An-2選擇偶數項。同時，考慮Rf′和Df′，易知Rf′還是屬于與f′相同的一類M序列反饋函數，而

因此，Df′還可以描述成以下多項式表示的形式，即形式3。

形式 3 在m序列的反饋函數的基礎上添加轉化成多項式表示后，即在形式1生成的f基礎上添加Aj(1 ≤j≤n-2)中排除后剩余的項。

易知，當n＞ 3 時，Df′與f,Df不同。據此可以快速構造個M序列反饋函數，分別是f,Df,f′,Df′。

接下來，再次利用定理4的式(2)，即f是M序列反饋函數，則

也是M序列反饋函數。若考慮此時的Rf′和Df′，則由f′的結構可知，Rf′還是屬于與f′相同的一類M序列反饋函數。當n≥ 5 時，以及f′就與f,Df,f′,Df′不同。此時根據推論1，f′,Df′還可以描述成以下多項式表示的形式，即形式4。

形式4 除了有公共的x1,1,x2…xn這3項外，其余項為Df′,f′在集合Ai(1≤i≤n-2)中所有未出現的項。

對于這類M序列反饋函數考慮函數之間相等的情況時，僅可能是f+X2=Df+X1與f+X1=Df+X2，此時的f與Df的小項表示必然是僅有一項不同，且不同的項為X2和X1，剩余的項必然是成對的互為對偶的項。因此，考慮到函數之間相等的情況是可能存在的，但出現的概率和個數較少，所以實際上這類方法可以構造約個M序列反饋函數。最后，可以用圖1來總結這類快速構造方法生成的M序列反饋函數，其中，

4.3 一類M序列反饋函數的快速構造算法

為了說明這類M序列的構造方法可以在實際中快速生成以多項式表示的反饋函數，本文給出算法形式，如算法1所示。該算法分為離線和在線階段，并且為了存儲以多項式表示的反饋函數，將Ai(0 ≤i≤n-1)中的每一元素對應到n-1維的二元數組向量構成的集合

例如，常數1對應向量(0,…,0)，x2對應向量(1,0,…,0)，x2…xn對應向量(1,…,1)，CBA表示集合A在B中的補集。

算法1 一類M序列反饋函數的快速構造算法

離線階段

對于給定級數n(n≥ 5)時，以向量形式存儲Ai(0 ≤i≤n-1)中所有元素，并記全體n-1維的二元向量集合為U。對于給定的m序列的反饋函數，給出其線性項在A1中的向量集合Q，則在在線階段只需求出M序列反饋函數中f0的對應向量集合，將集合中元素相加再加上x1，即可得到M序列反饋函數。

在線階段

Step1 輸入n級m序列的反饋函數中線性項的向量集合Q。

Step2 以形式1表示的M序列反饋函數中f0的對應向量集合F0為

Step3 以定理 3表示的M序列反饋函數中Df0的對應向量集合DF0為

Step4 以形式2表示的M序列反饋函數中f0′的對應向量集合F0′為

Step5 以形式 3表示的M序列反饋函數中Df0′的對應向量集合DF0′為

Step6 以形式 4表示的M序列反饋函數中f0′,Df0′的對應向量集合F0′,DF0′為

Step7M序列反饋函數中f0+X1+X2,Df0+X1+X2的對應向量集合為

圖1 一類M序列反饋函數的快速構造算法

分析該算法可知，由于離線階段存儲了所有多項式以次數為序的項數集合，存儲復雜度即為則在線階段，對于求一個給定集合在有序集合中的補集，只需要遍歷輸出該有序集合的部分元素即可，因此，時間復雜度為O(2n-1)。對比直接利用“并圈法”得到的以小項表示的M序列反饋函數，在其轉化成多項式表示上所需要的時間復雜度將大大降低。同時，本文也是首次給出以多項式表示的M序列反饋函數的構造算法，下面，本文將簡要分析該算法給出的這類M序列反饋函數的重量性質。

5 新的M序列反饋函數的重量性質

由于M序列反饋函數的結構總可以表示成，因此，M序列反饋函數的重量指的是f0的重量或f0小項表示的項數，即為w(f0)。在文獻[15]給出了M序列小項表示的反饋函數的一個必要條件，有以下結論。

定理5[15]當n≥ 3 時，對于Z(n)- 1 與

之間的一切奇數都有以這奇數為重量的M序列反饋函數存在，其中，

根據定理5，實際上，本文限制了w(f0)的取值，并且w(f0)的取值是M序列反饋函數在實際應用中的重要參考指標，因此，接下來，考慮快速構造方法生成的M序列反饋函數的重量w(f0)。

首先，可以合理限定m序列的反饋函數為二項式，即表示為x1+xi，則通過形式1生成的M序列反饋函數f0=xi+1+x2…xn轉化成小項表示后，其項數為w(f0)=2n-2+1 。當n較大時，Z(n)和Z?(n)都遠遠小于2n-2，因此，w(f0) 的取值大概在重量區間的中間。由于函數變換不改變w(f0)的取值，以及這種函數派生方式重量的增減幅度為2或4，因此，新的M序列反饋函數w(f0)為以下取值之一：

其次，考慮m序列的反饋函數為四項式，即在二項式的基礎上添加2個線性項。由于w(f0)從另一個角度可以看成f0=1的n-1維向量個數，新添加的2個線性項的取值（即該線性項等于0或1）使f0=1的情況個數與原有二項式比較不變，因此，此時n-1維向量滿足f0=1的個數不變，即此時通過形式 1生成的M序列反饋函數的w(f0)取值為以此類推，通過形式1生成的M序列反饋函數w(f0) 取值為 2n-2+1[19]，此時，新的M序列反饋函數w(f0)為以下取值之一：

綜上所述，可以得到以下結論。

結論M序列反饋函數f（其中，f為圖 1所示的8類M序列反饋函數）的重量w(f0)的取值必然在以下集合中：

6 結束語

由m序列構造M序列反饋函數一直以來是實際應用中常見的構造方法，本文充分利用m序列構造M序列反饋函數的結構特性，結合函數變換以及函數派生，得到了一類個數較多且多項式表示和小項表示的重量都可以確定的M序列反饋函數。這種構造豐富了由m序列構造M序列反饋函數的方法，并且給出了其他項數和重量條件的反饋函數，克服了單一由m序列構造M序列反饋函數的構造缺陷，在實際應用中有更多可供選擇的以多項式表示的M序列反饋函數。由于在構造過程中，多項式表示的方法還過于煩瑣，是否還存在類似形式1的項數較少的M序列反饋函數的構造方法，是下一步研究的目標。

參考文獻：

[1]中國科學院數學研究所代數組. 關于M序列反饋函數的構造方法[J].應用數學學報,1977,4:11-22.Institute of Mathematics,Chinese Academy of Sciences. The methods of constructingM-sequence feedback functions[J]. Acta Mathematicae Applicatae Sinica,1977,4:11-22.

[2]康慶德. GF(2)上M序列的構造方法[J]. 通信學報,1983(4): 2-10.KANG Q D. The methods of constructingM-sequence over GF(2)[J].Journal on Communications,1983(4): 2-10.

[3]熊榮華.M序列反饋函數的構造方法Ⅰ[J]. 應用數學學報,1986(2):227-236.XIONG R H. On methods of constructing the feedback functions ofMsequences I[J]. Acta Mathematicae Applicatae Sinica,1986(2): 227-236.

[4]朱士信.M序列反饋函數的派生方法[J]. 合肥工業大學學報(自然科學版),1991(4): 138-144.ZHU S X. Methods for the derivation of feedback functions ofMse-quences[J]. Journal of Hefei University of Technology,1991(4):138-144.

[5]章照止,羅喬林. 產生M序列的一個遞推算法[J]. 系統科學與數學,1987(4): 335-343.ZHANG Z Z,LUO Q L. A recursive algorithm for the generation of De Bruijn sequences[J]. Journal of System Science and Mathematical Science Chinese Series,1987(4): 335-343.

[6]SAWADA J,WILLIAMS A,WONG D. A surprisingly simple de Bruijn sequence construction[J]. Discrete Mathematics,2016,339(1):127-131.

[7]ABBAS A. Stretching De Bruijn sequences[J]. Designs Codes &Cryptography,2017,85(2):381-394.

[8]高楊,劉松華,王中孝. 一種基于“編織法”的De Bruijn序列構造算法[J]. 電子學報,2018,46(1): 48-54.GAO Y,LIU S H,WANG Z X. A De Bruijn sequence construction algorithm based on “interleaving” construction method[J]. Acta Electronica Sinica,2018,46(1): 48-54.

[9]LI C,ZENG X,LI C,et al. Construction of De Bruijn sequences from LFSRs with reducible characteristic polynomials[J]. IEEE Transactions on Information Theory,2015,62(1):610-624.

[10]CHANG Z,EZERMAN M F,LING S,et al. Construction of De Bruijn sequences from product of two irreducible polynomials[J].Cryptography & Communications,2018,10(2):251-275.

[11]LI M,JIANG Y,LIN D. The adjacency graphs of some feedback shift registers[J]. Designs Codes & Cryptography,2016,82(3):1-19.

[12]LI M,LIN D. The adjacency graphs of LFSRs with primitive-like characteristic polynomials[J]. IEEE Transactions on Information Theory,2017,63(2):1325-1335.

[13]LI M,LIN D. De Bruijn sequences,adjacency graphs and cyclotomy[J].IEEE Transactions on Information Theory,2017,PP(99): 1.

[14]DONG J,PEI D. Construction for De Bruijn sequences with large stage[J]. Designs Codes & Cryptography,2016:1-16.

[15]萬哲先,代宗鐸,劉木蘭,等. 非線性移位寄存器[M]. 北京:科學出版社,1978.WAN Z X,DAY Z D,LIU M L,et al. Non-linear shift register[M].Beijing: Science Press,1978.

[16]高鴻勛. 非奇函數是 M 序列反饋函數的一個充要條件[J]. 應用數學學報,1984(1): 9-10.GAO H X. A necessary and sufficient condition for nonsingular function to be feedback function of M-sequences[J]. Acta Mathematicae Applicatae Sinica,1984(1): 9-10.

[17]萬哲先. 代數與編碼[M]. 北京:科學出版社,1976.WAN Z X. Algebra and coding[M]. Beijing: Science Press,1976.

[18]高鴻勛. 求全部n級M序列及其反饋函數的一個方法與證明[J]. 應用數學學報,1979(4): 316-324.GAO H X. A method and proof of finding all n-stage of M-sequences and their feedback functions[J]. Acta Mathematicae Applicatae Sinica,1979(4): 316-324.

[19]許軍進,尹克震. M序列反饋函數重量與項數的分析[J]. 杭州電子科技大學學報,2007(1): 24-28.XU J J,YI K Z. Analysis on weights and terms of feedback functions for Sequences[J]. Journal of Hangzhou Dianzi University,2007(1):24-28.