有限域上一類自對(duì)偶正規(guī)基的乘法表與復(fù)雜度

廖群英, 李 威, 湯建剛

(1. 伊犁師范學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 新疆 伊寧 835000; 2. 四川師范大學(xué) 數(shù)學(xué)與軟件科學(xué)學(xué)院, 四川 成都 610066)

1 預(yù)備知識(shí)及主要結(jié)果

設(shè)q是素?cái)?shù)p的方冪,Fqn為q元有限域Fq的n次擴(kuò)域(n≥2).若N={α,αq,…,αqn-1}為Fqn在Fq上的正規(guī)基,則稱α為Fqn在Fq上的一個(gè)正規(guī)基生成元(或正規(guī)元).令

正規(guī)基N的復(fù)雜度定義為(ti,j)n×n中非零元的個(gè)數(shù),記為CN.R. Mullin等[1]證明了CN≥2n-1.當(dāng)CN=2n-1時(shí),稱N為最優(yōu)正規(guī)基.熟知,關(guān)于最優(yōu)正規(guī)基有I型和II型兩類[2].

眾所周知,正規(guī)基(特別是最優(yōu)正規(guī)基)在編碼理論、密碼體制以及信號(hào)傳遞等領(lǐng)域有著廣泛的應(yīng)用[1,3-4].然而,并不是所有的有限域上都存在最優(yōu)正規(guī)基.對(duì)于這些有限域,尋找低復(fù)雜度的正規(guī)基具有現(xiàn)實(shí)的意義.1990年,A. Wassermann[5]把最優(yōu)正規(guī)基推廣到k(k≥1)-型高斯正規(guī)基,k-型高斯正規(guī)基正是一類低復(fù)雜度的正規(guī)基.

稱N為Fqn在Fq上的k-型高斯正規(guī)基.

注11) 由定義易知:高斯正規(guī)基的生成元α在Fq上的跡函數(shù)[3-4]為

2) 1-型高斯正規(guī)基即為I型最優(yōu)正規(guī)基;q=2時(shí),2-型高斯正規(guī)基即為II型最優(yōu)正規(guī)基.

另一方面,對(duì)偶基也是有限域中一個(gè)十分重要的概念.設(shè)A={αi|0≤i≤n-1}和B={βi|0≤i≤n-1}為Fqn在Fq上的2個(gè)基.如果對(duì)于?i,j=0,1,2,…,n-1,均有

則稱B為A的對(duì)偶基,其中

表示Fqn在Fq上的跡函數(shù).熟知,任意基的對(duì)偶基存在唯一,且正規(guī)基的對(duì)偶基仍為正規(guī)基.特別地,如果B=A,則稱A是自對(duì)偶基.

早在1988年,A. Lempel等[6]就給出了Fqn在Fq上存在自對(duì)偶正規(guī)基的等價(jià)條件.1993年,S. Gao[7]給出了特征為奇數(shù)時(shí),Fqn在Fq上高斯正規(guī)基的乘法表和復(fù)雜度.對(duì)于k=1以及k=2的情形,Q. Y. Liao等[8]在2006年確定了全部的自對(duì)偶最優(yōu)正規(guī)基,即證明了命題1.3.

命題1.3[8]Fqn在Fq上的最優(yōu)正規(guī)基N是自對(duì)偶的當(dāng)且僅當(dāng)n=q=2或者q=2且N為II型最優(yōu)正規(guī)基.

文獻(xiàn)[9]對(duì)于特征為奇數(shù)的有限域,給出了一種構(gòu)作自對(duì)偶正規(guī)基的方法.2012年,Q. Y. Liao[10]給出了Fqn在Fq上的k型高斯正規(guī)基的對(duì)偶基,以及全部的自對(duì)偶高斯正規(guī)基.

命題1.4[10]設(shè)1≤k≤n,N為Fqn在Fq上的正規(guī)元α生成的k-型高斯正規(guī)基,則有

生成N的對(duì)偶基.進(jìn)而,N為自對(duì)偶正規(guī)基當(dāng)且僅當(dāng)以下3條之一成立:

(i)p=2且k≡0(mod 2);

(ii)n≡p≡1(mod 2)且k≡0(mod 2p);

(iii)k≡1(mod 2)且n=p=2.

命題1.5[11]設(shè)k為奇數(shù),N為Fqn在Fq上的正規(guī)元α生成的k-型高斯正規(guī)基,則?a,b∈Fq使得β=a+bα生成Fqn在Fq上的自對(duì)偶正規(guī)基,當(dāng)且僅當(dāng)n=p=2,此時(shí)b=1,a在Fq中任取.

關(guān)于正規(guī)基元的線性組合也為正規(guī)基元,近年來有一些好的結(jié)果,如文獻(xiàn)[12]中給出了有限域Fqn在Fq上的正規(guī)基N={αi=αqi|i=0,1,2,…,n-1}的對(duì)偶基B={βi=βqi|i=0,1,2,…,n-1}的生成元β形如a+bα=a+bα0(a,b∈Fq)的2個(gè)充分必要條件,以及在該假設(shè)之下2組基的乘法表之間的運(yùn)算關(guān)系;文獻(xiàn)[13]對(duì)上述結(jié)果進(jìn)行了推廣,得到了正規(guī)基N的對(duì)偶基B的生成元形如β=a+bαr(a,b∈Fq,r=0,1,2,…,n-1)的充分必要條件以及在該假設(shè)之下2個(gè)基的乘法表之間的運(yùn)算關(guān)系;最近,文獻(xiàn)[14]給出了有限域Fqn在Fq上高斯正規(guī)基的對(duì)偶基及其乘法表與復(fù)雜度的對(duì)應(yīng)關(guān)系,文獻(xiàn)[11]給出了有限域Fqn在Fq上高斯正規(guī)基N的生成元α的線性組合β=a+bα(a,b∈Fq)生成Fqn在Fq上自對(duì)偶正規(guī)基B的等價(jià)刻畫.本文繼續(xù)該問題的研究,給出了N和B的乘法表之間的運(yùn)算關(guān)系,以及N為最優(yōu)正規(guī)基時(shí)B的準(zhǔn)確復(fù)雜度.

定理1.6設(shè)q為素?cái)?shù)p的方冪,Fqn為有限域Fq的n次擴(kuò)張,N={αi=αqi|i=0,1,2,…,n-1}是Fqn在Fq上的k-型高斯正規(guī)基.設(shè)a,b∈Fq,并且β=a+bα生成Fqn在Fq上的自對(duì)偶正規(guī)基B={βi=βqi|i=0,1,2,…,n-1}.T=(ti,j)和H=(hi,j)分別為N與B的乘法表,則H與T中元的對(duì)應(yīng)關(guān)系如下:

h0,0=-a2b-1+bt0,0+ab-1(na-b)-1+2a,

h0,l=-a2b-1+bt0,l+ab-1(na-b)-1,

l=1,2,…,n-1,

hi,0=-a2b-1+bti,0+a,

i=1,2,…,n-1,

hi,i=-a2b-1+bti,i+a,

i=1,2,…,n-1,

hi,l=-a2b-1+bti,l,

1≤i≤n-1,l≠0,i.

(1)

推論1.7設(shè)q為素?cái)?shù)p的方冪,N={αi=αqi|i=0,1,2,…n-1}為Fqn在Fq上的I型最優(yōu)正規(guī)基,則?a,b∈Fq,使得β=a+bα生成Fqn在Fq上的自對(duì)偶正規(guī)基B={βi=βqi|i=0,1,2,…n-1}當(dāng)且僅當(dāng)n=p=2,b=1,a(a+1)≠1,此時(shí)

定理1.8若N={αi=αqi|i=0,1,2,…,n-1}為F2n在F2上的II型最優(yōu)正規(guī)基,

1) ?a,b∈F2,使得β=a+bα生成F2n在F2上自對(duì)偶正規(guī)基B的充分必要條件是

2) 若β=a+bα生成F2n在F2上自對(duì)偶正規(guī)基B,則B的復(fù)雜度為

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

引理2.1[15]設(shè)N={α,αq,…,αqn-1}為Fqn在Fq上的I型最優(yōu)正規(guī)基,T=(ti,j)為其乘法表,則有

引理2.2[15]設(shè)N={α,α2,…,α2n-1}為F2n在F2上的II型最優(yōu)正規(guī)基,T=(ti,j)為其乘法表,則有

而當(dāng)i=1,2,…,n-2時(shí)有

定理1.6的證明由T=(ti,j),H=(hi,j)分別為N和B的乘法表,即

而對(duì)?a,b∈Fq以及β=a+bα,有βi=a+bαi(0≤i≤n-1).因此對(duì)?i=0,1,2,…,n-1有

另一方面,對(duì)?i=0,1,2,…,n-1有

ββi=a2+ab(α+αi)+b2ααi=

故

當(dāng)i=0時(shí),對(duì)比兩邊αl(0≤l≤n-1)的系數(shù)可得

l=0(因?yàn)棣?α0),

1≤l≤n-1.

(2)

當(dāng)i≠0時(shí),對(duì)比兩邊αl(0≤l≤n-1)的系數(shù)可得

l=0,i,

l≠0,i.

(3)

又β=a+bα(a,b∈Fq)生成Fqn在Fq上的自對(duì)偶正規(guī)基,故Tr(β)≠0,即na+bTr(α)=na-b≠0,以及

而

故

(4)

另一方面,由β=a+bα可知

βi=βqi=a+bαi, 0≤i≤n-1,

從而

ββi=na+b(α+αi)+ααi, 0≤i≤n-1.

因此由

以及Tr(αj)=Tr(α)=-1(0≤j≤n-1)可得

Tr(ββi)=na2-2ab+b2Tr(ααi)=

(5)

于是由(4)和(5)式有

1≤i≤n-1.

注意到na≠b,故

(6)

將(6)式代入(2)和(3)式可得

-a(na-b)-1+bh0,0=-a2+2ab+b2t0,0,

-a(na-b)-1+bh0,l=-a2+b2t0,l,

1≤l≤n-1,

bhi,0=-a2+ab+b2ti,0,

1≤i≤n-1,

bhi,i=-a2+ab+b2ti,i,

1≤i≤n-1,

bhi,l=-a2+b2ti,l,

1≤i≤n-1,l≠0,i.

這就完成了定理1.6的證明.

推論1.7的證明設(shè)T=(ti,j)和H=(hi,j)分別為N與B的乘法表,由注1的1)知:I型最優(yōu)正規(guī)基即為1-型高斯正規(guī)基,即k=1為奇數(shù).從而由命題1.5,B為自對(duì)偶正規(guī)基當(dāng)且僅當(dāng)n=p=2,b=1,a在Fq中任取.故再由定理1.6可得

h0,0=-a2+t0,0-a=t0,0+a2+a,

h0,1=-a2+t0,1-a=t0,1+a2+a,

h1,0=-a2+t1,0+a=t1,0+a2+a,

h1,1=-a2+t1,1+a=t1,1+a2+a.

(7)

由引理2.1,當(dāng)n=p=2時(shí),I型最優(yōu)正規(guī)基的乘法表為

代入(7)式可得

注意到B為正規(guī)基,CB≥2n-1=2×2-1=3,因此CB=3或者4,故a2+a+1≠0,從而

CB=3?a2+a=0?a=0,1.

此時(shí)B的乘法表為

類似的

CB=4?a2+a≠0,1?

a≠0,1并且a(a+1)≠1.

此時(shí)B的乘法表為

這就完成了推論1.7的證明.

定理1.8的證明1) 先證明必要性.因α生成II型高斯正規(guī)基N,由理引2.2以及注1的1)有

Tr(αα0)=Tr(α)=-1=1,

(8)

以及

1≤i≤n-1.

(9)

又

βi=β2i=(a+bα)2i=a+bαi,

0≤i≤n-1,

從而

ββi=a2+b(α+αi)+b2ααi,

0≤i≤n-1.

于是

Tr(ββi)=na2-2ab+b2Tr(ααi)=

na2+b2Tr(ααi), 0≤i≤n-1.

從而由(8)和(9)式可得

因此,若β生成自對(duì)偶正規(guī)基,則有

即

na2+b2=1,na2=0,

從而

即

這就證明了必要性.

反過來,若β滿足條件

則當(dāng)β=α?xí)r,即B=N為II型最優(yōu)正規(guī)基,由命題1.3知β=0+1×α生成Fqn在Fq上的自對(duì)偶正規(guī)基.

現(xiàn)在假設(shè)n≡0(mod 2)并且β=1+α.注意到α=α0生成F2n在F2上的II型最優(yōu)正規(guī)基N={αi=α2i|i=0,1,2,…,n-1},因此

0≤i≤n-1,

以及

βi=β2i=1+α2i=1+αi,

0≤i≤n-1.

(10)

下面證明βi(i=0,1,2,…,n-1)在F2上線性無關(guān),從而形成F2n在F2上的一個(gè)正規(guī)基.事實(shí)上,若

由注1的1)以及(10)式有

由α=α0生成F2n在F2上的正規(guī)基,即α0,α1,…,αn-1在F2上線性無關(guān),故

從而

故(n-1)c=0.注意到n≡0(mod 2),因此cj=c=0(0≤j≤n-1),從而β=1+α生成F2n在F2上的正規(guī)基B.

進(jìn)而,由β=β0=1+α0知βi=β2i=1+αi(0≤i≤n-1).再由n≡0(mod 2)以及(8)和(9)式可得

Tr(ββi)=Tr(1+α+αi+ααi)=

即B為F2n在F2上的自對(duì)偶正規(guī)基.

這就證明了充分性.

2) 若β滿足定理1.8的1)中的條件,即β=α或β=1+α生成F2n在F2上的自對(duì)偶正規(guī)基,則當(dāng)β=α?xí)r,B=N為II型最優(yōu)正規(guī)基,此時(shí)復(fù)雜度CB=CN=2n-1.而當(dāng)β=1+α?xí)r,即a=b=1,由定理1.6,此時(shí)N和B的乘法表T=(ti,j)以及H=(hi,j)之間有如下對(duì)應(yīng)關(guān)系:

h0,0=t0,0,

h0,l=t0,l,l=1,2,…,n-1,

hi,0=ti,0,i=1,2,…,n-1,

hi,i=ti,i,i=1,2,…,n-1,

hi,l=ti,l+1,

1≤i≤n-1,l≠0,i,

即

h0,l=t0,l, 0≤l≤n-1,

hi,l=ti,l,

1≤i≤n-1,l=0,i,

hi,l=ti,l+1,

1≤i≤n-1,l≠0,i.

(11)

另一方面,因N為II型最優(yōu)正規(guī)基從而為高斯正規(guī)基,以及高斯正規(guī)基的構(gòu)造定理知2n+1為素?cái)?shù),故由n≥2為偶數(shù)可知

2≡±3(mod 2n+1)?

2≡-3(mod 2n+1)?

2n+1=5?n=2.

此時(shí)N={α,α2},β=1+α=α2.因此B=N,CB=CN=2n-1=3.

因此,由引理2.2,當(dāng)n≥4為偶數(shù)時(shí),tn-1,0=0.再由引理2.2以及(11)式可知

hn-1,n-1=tn-1,n-1=1,hn-1,0=0,

并且對(duì)?j=1,…,n-2,hn-1,j中恰有1個(gè)取值為0,n-3個(gè)取值為1.因此

H的末行中恰有n-2個(gè)非零元素.

(12)

進(jìn)而,再由(11)式以及引理2.2知恰有一個(gè)h0,j=t0,j=1(0≤j≤n-1),從而

H的首行中恰有1個(gè)非零元素.

(13)

現(xiàn)在考慮H的第i(1≤1≤n-2)行中的非零元素個(gè)數(shù).易知2i≠2i±1(mod 2n+1).注意到II最優(yōu)正規(guī)基即是q=2的2-型高斯正規(guī)基,由k-型高斯正規(guī)基的構(gòu)造定理可知:2模2n+1的階為n或2n,因此

2i≡-(2i+1)(mod 2n+1)?

2i+1≡1(mod 2n+1)?

i=n-1或i=2n-1,

2i≡-(2i-1)(mod 2n+1)?

2i+1≡-1(mod 2n+1)?

因此由引理2.2以及(11)式,對(duì)?i(1≤i≤n-2)有

同理

20≡±(2i±1)(mod 2n+1)?2i≡0,

±2(mod 2n+1)?

2i-1≡±1(mod 2n+1).

又2模2n+1的階為n或2n,故

20≡±(2i±1)(mod 2n+1)?

由引理2.2以及(11)式,對(duì)?i(1≤i≤n-2)有

H的第i行中恰有n-2個(gè)非零元素.

(14)

H的第i行中恰有n-4個(gè)非零元素.

(15)

因此由(12)～(15)式,B的復(fù)雜度為

CB=1+3(n-2)+

(n-4)(n-4)=n2-5n+11.

這就證明了定理1.8.

致謝四川師范大學(xué)科研基金重點(diǎn)培育項(xiàng)目(13ZDL06)對(duì)本文給予了資助,謹(jǐn)致謝意.

[1] Mullin R, Onyszchuk I, Vanstone S, et al. Optimal normal bases inGF(pm)[J]. Discrete Appl Math,1988/1989,22:149-161.

[2] Gao S, Lenstra H W. Optimal normal bases[J]. Des Codes Cryptogr,1992,2:315-323.

[3] Lidl R, Niederreiter H. Finite Fields[M]. Cambridge:Cambridge University Press,1987.

[4] Lidl R, Niederreiter H. Finite Fields and Their Applications[M]. 2nd Ed. Cambrige:Cambrige University Press,1994.

[5] Wassermann A. Konstruktion von normalbasen[J]. Bayreuther Math Scriften,1990,31:155-164.

[6] Lempel A, Weinberger M. Self-complementary normal basis in finite fields SIAM[J]. Discrete Math,1988,1:193-198.

[7] Gao S. Normal Bases over Finite Fields[D]. Ontario:University of Waterloo,1993.

[8] Liao Q Y, Sun Q. Normal bases and their dual-bases over finite fields[J]. Acta Mat Sinica:English Ser,2006,22(3):845-848.

[9] Nogami Y, Nasu H, Morikawa Y, et al. A method for constructing a self-dual normal basis in odd characteristic extension fields[J]. Finite Fields and Their Appl,2008,14:867-876.

[10] Liao Q Y. The Gaussian period normal basis and its trace basis over finite fields[J]. J Number Theory,2012,132:1507-1518.

[11] 廖群英,李威,湯建剛,等. 有限域上與k-型高斯正規(guī)基相關(guān)的自對(duì)偶正規(guī)基[J]. 四川師范大學(xué)學(xué)報(bào):自然科學(xué)版,2013,36(5):663-668.

[12] 廖群英. 關(guān)于有限域上一類特殊的正規(guī)基[J]. 四川大學(xué)學(xué)報(bào):自然科學(xué)版,2005,42(1):41-46.

[13] 蘇丹丹,廖群英. 有限域上一類特殊對(duì)偶基的推廣[J]. 四川大學(xué)學(xué)報(bào):自然科學(xué)版,2011,48(3):499-504.

[14] 李波,廖群英. 有限域上k-型高斯正規(guī)基及其對(duì)偶基的乘法表[J]. 四川師范大學(xué)學(xué)報(bào):自然科學(xué)版,2013,36(6).

[15] 廖群英,孫琦. 有限域上最優(yōu)正規(guī)基的乘法表[J]. 數(shù)學(xué)學(xué)報(bào):中文版,2005,48(5):948-954.