李 波

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

1 基礎(chǔ)知識

設(shè)q為素?cái)?shù)p的方冪，n(≥2)為正整數(shù)，F(xiàn)qn是 q元域 Fq的 n(≥2)次擴(kuò)張.若 N={αi=αqi|i=0，1，…，n－1}是Fqn到Fq的一個(gè)正規(guī)基，則稱α是Fqn到Fq的一個(gè)正規(guī)元.設(shè)

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

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

生成Fqn到Fq的一個(gè)正規(guī)基，稱N為Fqn到Fq的一個(gè)k－型高斯正規(guī)基.

注1 設(shè)N為Fqn到Fq的一個(gè)k－型高斯正規(guī)基，由Ⅰ型和Ⅱ型最優(yōu)正規(guī)基的定義可知，當(dāng)k=1時(shí)，N為Ⅰ型最優(yōu)正規(guī)基;當(dāng)k=q=2時(shí)，N為Ⅱ型最優(yōu)正規(guī)基.

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

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

下面給出q－循環(huán)的定義.

定義 2［15］設(shè) a0，a1，…，al－1為{0，1，…，m－1}中 l個(gè)不同的元素，q 為素?cái)?shù)的方冪，若滿足

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

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

2 主要結(jié)果及證明

這里先給出一個(gè)引理.

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

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

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

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

證明 易知，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).于是

由于不同的費(fèi)馬數(shù)必定互素，則 t－2≤t1－1，即 t－1≤t1.從而，t－1≤t1≤t.當(dāng) t1=t時(shí)，m≠t－1，此時(shí) l2i+1=n;當(dāng)t=t－1 時(shí)，m=t－1，此時(shí)

例1 條件同推論2，

當(dāng) i=1 時(shí)，m=0，有若 t≥2，則 m＜t－1，此時(shí) l=n;若 t=1，則 m=t－1，此時(shí)

當(dāng) i=2 時(shí)，m=1，有若 t≠2，則 m≠t－1，此時(shí) l=n;若 t=2，則 m=t－1，此時(shí)

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

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

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

由定義1知，當(dāng)n=4時(shí)，不存在F2n到F2上的Ⅱ型最優(yōu)正規(guī)基.

注 2 通過定義可以驗(yàn)證，當(dāng) n=4 時(shí)，F(xiàn)2n到 F2上的Ⅰ型最優(yōu)正規(guī)基滿足 t0=t1=tn－1=1，ti=0(i≠0，1，n－1).

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

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

1)當(dāng)n=4時(shí)，N可為Ⅰ型最優(yōu)正規(guī)基;

2)當(dāng)n≠4時(shí)，N一定不是最優(yōu)正規(guī)基.

［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］廖群英，孫琦.有限域上最優(yōu)正規(guī)基的乘法表［J］.數(shù)學(xué)學(xué)報(bào)，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型高斯正規(guī)基及其對偶基［J］.四川大學(xué)學(xué)報(bào):自然科學(xué)版，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-型高斯正規(guī)基及其對偶基［J］.四川師范大學(xué)學(xué)報(bào):自然科學(xué)版，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-型高斯正規(guī)基的對偶基及其乘法表［J］.四川師范大學(xué)學(xué)報(bào):自然科學(xué)版，2013，36(6):824-829