有限域上一类自对偶正规基的乘法表与复杂度

廖群英, 李 威, 汤建刚

(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.