有限域上一類自對偶正規基的乘法表與復雜度

廖群英, 李 威, 湯建剛

(1. 伊犁師范學院 數學與統計學院, 新疆 伊寧 835000; 2. 四川師范大學 數學與軟件科學學院, 四川 成都 610066)

1 預備知識及主要結果

設q是素數p的方冪,Fqn為q元有限域Fq的n次擴域(n≥2).若N={α,αq,…,αqn-1}為Fqn在Fq上的正規基,則稱α為Fqn在Fq上的一個正規基生成元(或正規元).令

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

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

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

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

2) 1-型高斯正規基即為I型最優正規基;q=2時,2-型高斯正規基即為II型最優正規基.

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

則稱B為A的對偶基,其中

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

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

命題1.3[8]Fqn在Fq上的最優正規基N是自對偶的當且僅當n=q=2或者q=2且N為II型最優正規基.

文獻[9]對于特征為奇數的有限域,給出了一種構作自對偶正規基的方法.2012年,Q. Y. Liao[10]給出了Fqn在Fq上的k型高斯正規基的對偶基,以及全部的自對偶高斯正規基.

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

生成N的對偶基.進而,N為自對偶正規基當且僅當以下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]設k為奇數,N為Fqn在Fq上的正規元α生成的k-型高斯正規基,則?a,b∈Fq使得β=a+bα生成Fqn在Fq上的自對偶正規基,當且僅當n=p=2,此時b=1,a在Fq中任取.

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

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

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設q為素數p的方冪,N={αi=αqi|i=0,1,2,…n-1}為Fqn在Fq上的I型最優正規基,則?a,b∈Fq,使得β=a+bα生成Fqn在Fq上的自對偶正規基B={βi=βqi|i=0,1,2,…n-1}當且僅當n=p=2,b=1,a(a+1)≠1,此時

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

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

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

2 主要結果的證明

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

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

而當i=1,2,…,n-2時有

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

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

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

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

故

當i=0時,對比兩邊αl(0≤l≤n-1)的系數可得

l=0(因為α=α0),

1≤l≤n-1.

(2)

當i≠0時,對比兩邊αl(0≤l≤n-1)的系數可得

l=0,i,

l≠0,i.

(3)

又β=a+bα(a,b∈Fq)生成Fqn在Fq上的自對偶正規基,故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的證明設T=(ti,j)和H=(hi,j)分別為N與B的乘法表,由注1的1)知:I型最優正規基即為1-型高斯正規基,即k=1為奇數.從而由命題1.5,B為自對偶正規基當且僅當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,當n=p=2時,I型最優正規基的乘法表為

代入(7)式可得

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

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

此時B的乘法表為

類似的

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

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

此時B的乘法表為

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

定理1.8的證明1) 先證明必要性.因α生成II型高斯正規基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)式可得

因此,若β生成自對偶正規基,則有

即

na2+b2=1,na2=0,

從而

即

這就證明了必要性.

反過來,若β滿足條件

則當β=α時,即B=N為II型最優正規基,由命題1.3知β=0+1×α生成Fqn在Fq上的自對偶正規基.

現在假設n≡0(mod 2)并且β=1+α.注意到α=α0生成F2n在F2上的II型最優正規基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上線性無關,從而形成F2n在F2上的一個正規基.事實上,若

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

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

從而

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

進而,由β=β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上的自對偶正規基.

這就證明了充分性.

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

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型最優正規基從而為高斯正規基,以及高斯正規基的構造定理知2n+1為素數,故由n≥2為偶數可知

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

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

2n+1=5?n=2.

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

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

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

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

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

(12)

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

H的首行中恰有1個非零元素.

(13)

現在考慮H的第i(1≤1≤n-2)行中的非零元素個數.易知2i≠2i±1(mod 2n+1).注意到II最優正規基即是q=2的2-型高斯正規基,由k-型高斯正規基的構造定理可知: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)式,對?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)式,對?i(1≤i≤n-2)有

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

(14)

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

(15)

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

CB=1+3(n-2)+

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

這就證明了定理1.8.

致謝四川師范大學科研基金重點培育項目(13ZDL06)對本文給予了資助,謹致謝意.

[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-型高斯正規基相關的自對偶正規基[J]. 四川師范大學學報:自然科學版,2013,36(5):663-668.

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

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

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

[15] 廖群英,孫琦. 有限域上最優正規基的乘法表[J]. 數學學報:中文版,2005,48(5):948-954.