二元域上一類正規基與q-循環*

李 波

(重慶郵電大學移通學院，重慶401520)

1 基礎知識

設q為素數p的方冪，n(≥2)為正整數，Fqn是 q元域 Fq的 n(≥2)次擴張.若 N={αi=αqi|i=0，1，…，n－1}是Fqn到Fq的一個正規基，則稱α是Fqn到Fq的一個正規元.設

則(ti，j)n×n中非零元的個數稱為 N 的復雜度，記為 CN.R Mullin 等［1］證明了 CN≥2n－1，當 CN=2n－1 時，稱 N為最優正規基.以最優正規基為代表的低復雜度正規基已經有許多結果［2－11］.R Mullin等給出了Ⅰ型和Ⅱ型最優正規基的構造定理之后;高緒洪［12］證明了只存在這兩類最優正規基;1990年，A Wassermann［13］把最優正規基推廣為k－型高斯正規基.

定義1［13］設q為素數p的方冪，k和n為正整數，且滿足 kn+1為素數，(kn+1，p)=1.假定 γ∈Fqkn是kn+1次本原單位根，s是q模kn+1的次數.若(kn/s，n)=1，l是Zkn+1的一個k本原的單位根，則

生成Fqn到Fq的一個正規基，稱N為Fqn到Fq的一個k－型高斯正規基.

注1 設N為Fqn到Fq的一個k－型高斯正規基，由Ⅰ型和Ⅱ型最優正規基的定義可知，當k=1時，N為Ⅰ型最優正規基;當k=q=2時，N為Ⅱ型最優正規基.

熟知，最優正規基(特別是低復雜度正規基)在編碼理論、密碼學、數字通信等領域有著廣泛的應用.通過計算發現，當擴張次數 n=4，8，16 時，存在 F2n到 F2的正規基 N，使得序列 ti=Tr(ααi)(i=0，1，…，n－1)中t0=t1=tn－1=1，ti=0(i≠0，1，n－1)，其中 Tr表示 Fqn到 Fq的跡映射.這類正規基在編碼中有著很好的應用.自然的問題是:擴張次數 n滿足什么條件，才存在 F2n到 F2的正規基滿足 t0=t1=tn－1=1，ti=0(i≠0，1，n－1).

由有限域上正規基的性質可知，ti=tn－i.Perlis［14］給出了如下結論:設 q=ps，p 為素數，n=pm，m≥1.若 α∈Fqn，則 α 為 Fqn到 Fq的一個正規元?Tr(α)≠0.從而當 n=2t(t≥1)時，t0=1.故此時只需考慮 i≠0 的情形.對于k－型高斯正規基，文獻［7］得到了如下結論:若α生成Fqn到Fq的一個k－型高斯正規基，則Tr(α)=－1.

下面給出q－循環的定義.

定義 2［15］設 a0，a1，…，al－1為{0，1，…，m－1}中 l個不同的元素，q 為素數的方冪，若滿足

則稱序列(a0，a1，…，al－1)為一個模 m 的 q－循環，l為該 q－循環的長度.

以下用 li表示 i模 qn－1 的 q－循環的長度.由定義 2，iqli≡i(mod qn－1).

2 主要結果及證明

這里先給出一個引理.

引理 1［12］設 k，n 是正整數，kn+1 為素數，q 模 kn+1 的階是 e.如果(kn/e，n)=1，T 是 Zkn+1的一個 k－次本原單位根，則Zkn+1中任意非零元r都能唯一表示成如下形式:

定理1 設q為素數的方冪，n(≥2)是正整數，則li|n，其中0≤i≤qn－1.

證明 由文獻［15］知若ξ是Fqn的一個本原元，且存在k個不同的q－循環，令i1，i2，…，ik分別來自這k個不同的q－循環，則xn－1在Fq上的完全分解式為

形如 Fe=22e+1(e≥0)的數被稱為費馬數.對于任意給定的兩個費馬數 Fe1，Fe2;若 e1≠e2，則(Fe1，Fe2)=1.下面運用這個性質給出一種特殊情形下2i+1模2n－1的2－循環的長度的計算公式.

證明 易知，2n－1=22t－1=Ft－1Ft－2…F0，2i+1=Fm.令 2l2i+1－1=Ft－1Ft－2…F0.由定理 1，l2i+1|n，則 t1－1≤t－1，即 t1≤t.又 2i+1≡(2i+1)2l2i+1(mod(2n－1))，即 2n－1|(2i+1)(2l2i+1－1).于是

由于不同的費馬數必定互素，則 t－2≤t1－1，即 t－1≤t1.從而，t－1≤t1≤t.當 t1=t時，m≠t－1，此時 l2i+1=n;當t=t－1 時，m=t－1，此時

例1 條件同推論2，

當 i=1 時，m=0，有若 t≥2，則 m＜t－1，此時 l=n;若 t=1，則 m=t－1，此時

當 i=2 時，m=1，有若 t≠2，則 m≠t－1，此時 l=n;若 t=2，則 m=t－1，此時

關于是否存在 F2n到 F2的正規基滿足 t0=t1=tn－1=1，ti=0(i≠0，1，n－1)，有

定理2 設 N={αi|i=0，1，…，n－1}是 F2n到 F2上的一個 k－型高斯正規基，則

1)若 k為偶數，或 k為奇數且 n≠4，則 N 不滿足 t0=t1=tn－1=1，ti=0(i≠0，1，n－1);

由定義1知，當n=4時，不存在F2n到F2上的Ⅱ型最優正規基.

注 2 通過定義可以驗證，當 n=4 時，F2n到 F2上的Ⅰ型最優正規基滿足 t0=t1=tn－1=1，ti=0(i≠0，1，n－1).

由定理2和注1，注2，有

推論 3 設 N={αi|i=0，1，…，n－1}是 F2n到 F2上的一個正規基，且滿足 t0=t1=tn－1=1，ti=0(i≠0，1，n－1)，則

1)當n=4時，N可為Ⅰ型最優正規基;

2)當n≠4時，N一定不是最優正規基.

［1］MNLLIN R，ONYSZCHUK I，VANSTONE S，et al.Optimal Normal Bases Over Fpn［J］.Discrete Applied Math，1999(22):149-161

［2］LIAO Q Y，SUN Q.Normal Bases and Their Dual-bases Over Finite Fields［J］.Acta Mathematics Sinica，2006，22(3):845-848

［3］LIAO Q Y.On the Distribution of Normal Bases Over Finite Fields［J］.Advances in Mathmatics，2010，39(2):207-211

［4］廖群英，孫琦.有限域上最優正規基的乘法表［J］.數學學報，2005，48(5):947-954

［5］WAN Z X，ZHOU K.On the Complexity of the Dual Bases of a Type I Optimal Normal Bases［J］.Finite Fields and Their Applications，2007，13(4):411-417

［6］GAO SH.Abelian Groups，Gauss Periods，and Normal Bases［J］.Finite Fields and Their Applications，2001，7(1):149-161

［7］廖群英，蘇丹丹，付萍.有限域上的2型高斯正規基及其對偶基［J］.四川大學學報:自然科學版，2010，47(6):1221-1224

［8］ASH D，BLAKE I F，VANSTONE S.Low Complexity Normal Bases［J］.Discrete Applied Math，1999(25):191-210

［9］NOGAMI Y，NASU H，MORIKAWA Y，et al.A Method of Constructing a Self-dual Normal Bases in Odd Characteristic Extention Fields［J］.Finite Fields and Their Applications，2008，14(2):867-876

［10］李俊，黃琴，李波，等.有限域上的k-型高斯正規基及其對偶基［J］.四川師范大學學報:自然科學版，2011，34(3)，289-295

［11］YOUNG B，PANARIO D.Low Complexity Normal Bases［J］.Finite Fields and Their Applications，2004，10(1):53-64

［12］GAO SH.Normal Bases Over Finite Fields［D］.Waterloo:Waterloo University，1993

［13］WASSERMANN A.Konstruktion Von Normalbasen［J］.Bayreuther Mathmatische Schriften，1990(31):155-164

［14］PERLISS.Normal Bases of Cyclic Fields of Prime Power Degree［J］.Duke Math，1942(9):507-519

［15］WAN Z X.Lectures on Finite Fields and Galois Rings［M］.Singapore:World Science Publishers，2003

［16］李波，廖群英.有限域上k-型高斯正規基的對偶基及其乘法表［J］.四川師范大學學報:自然科學版，2013，36(6):824-829