有限域上(4,7)型高斯正规基及其对偶基的本原性

魏 杰, 廖群英, 周嘉骏

(四川师范大学 数学与软件科学学院, 四川 成都 610066)

有限域上(4,7)型高斯正规基及其对偶基的本原性

魏 杰, 廖群英*, 周嘉骏

(四川师范大学 数学与软件科学学院, 四川 成都 610066)

有限域上的正规基在编码理论、密码体制及信号传递等领域有着广泛的应用,本原正规基因其独特的本原性质更为重要.最近,文献(魏杰,李雪连,廖群英. 四川大学学报(自然科学版),2016,53(1):7-12.)由k-型高斯正规基构造定理,确定了Fq4在Fq上的7-型高斯正规基N及其对偶基B和迹基的准确复杂度.进一步研究N和B的本原性质,证明了有限域Fq特征为2或3时,N为本原正规基当且仅当q=2或q=3,此时B均不是本原正规基.

有限域; 高斯正规基; 对偶基; 本原元

1 主要结果

设q为素数p的方幂,n是正整数,Fqn是有限域Fq的n次扩域(n≥2),若N={α,αq,…,αqn-1}为Fqn在Fq上的正规基,则称α为Fqn在Fq上的一个正规元.进而令

则称T=(ti,j)n×n为N的乘法表,T中非零元素的个数称为N的复杂度,记为CN.由于T=(ti,j)中的非零元越少,Fqn中乘法运算的计算量也就越小.R. Mullin等[1]证明了CN≥(2n-1),且当CN=(2n-1)时,称N为最优正规基,进而给出了两类最优正规基的构造定理,分别为I型和II型最优正规基,并猜想最优正规基只有这2类.随后,S. H. Gao[2]证明了这个猜想.从而寻找次优的正规基也成了很重要的课题.A. Wassermann[3]将有限域Fqn在Fq上的最优正规基的概念推广到(n,k)-型高斯正规基,这正是一类低复杂度的正规基,并且(n,1)-型高斯正规基即为I型最优正规基,q=2时的(n,2)-型高斯正规基即为II型最优正规基.

定理 1.1[4]对任意正整数n≥1和素数方幂q,Fqn在Fq上均存在本原正规基.

定理 1.2[5]对任意的素数方幂q,任意的正整数n(n≥2)以及任意的非零元素a∈Fq,都存在一个本原正规多项式f(x)=xn+c1xn-1+…+cn∈Fq[x],而且c1=a.

定理 1.3[6]对任意的素数方幂q,任意的正整数n(n≥15),任意的正整数m(1≤m

定理 1.4[7]对任意素数方幂q,任意正整数n(n≥2),除(q,n)取值为(2,3),(2,4),(3,4),(4,3),(5,4)外,都存在a∈Fq,使得α和α-1都是Fq上的本原正规元.

定理 1.5[8]对任意的素数方幂q,任意的正整数n(n≥7)以及任意的非零元素a,b∈Fq且a≠0,都存在一个本原正规多项式f(x)=xn+c1xn-1+…+cn∈Fq[x],且c1=a,c2=b.

Q. Y. Liao[9]确定了所有的I型本原最优正规基,并给出II型本原最优正规基的一个充分条件.

另一方面,在有限域的众多基中,对偶基也是一个很重要的概念.对于Fqn在Fq上的任意两组基:B={βi=βqi|i=0,1,…,n-1}和N={αi=αqi|i=0,1,…,n-1},称B为N的对偶基,若对任意的i,j=0,1,…,n-1,都有

定理 1.6[11]设q为素数p的方幂,N={α,αq,…,αqn-1}为Fqn在Fq上的k-型高斯正规基(1≤k≤n),则N的对偶基的生成元为

但是,有限域上本原正规基的对偶基不一定是本原正规基.迄今为止,人们只确定了最优正规基的本原性,对于一般情形下的正规基,即使是性质非常好的高斯正规基,其本原性的讨论都很困难,可参考文献[12-14].最近,文献[15]给出了Fq4在Fq上的7-型高斯正规基及其对偶基和迹基的准确复杂度.本文继续文献[15]的研究,进一步完善文献[15]的结果,由此给出有限域上一些新的本原高斯正规基,即证明了如下主要结果:

定理 1.7 设p为素数,n为正整数且q=pn.设N={αi=αqi|i=0,…,3}为Fq4在Fq上的7-型高斯正规基,B={βi=βqi|1=0,…,3}为N的对偶基,其中α=α0,β=β0,则有:

1) 当p=2时,N为本原正规基当且仅当q=2.此时B不是本原正规基;

2) 当p=3时,N为本原正规基当且仅当q=3.此时B不是本原正规基.

2 主要结果的证明

以下引理2.2～2.4的证明可参见文献[15]中定理1.2的证明.

引理 2.2[15]Fq4在Fq上的7-型高斯正规基N={αi=αqi|i=0,…,3}满足:

αα=2α+3α1+2α3;

(1)

αα1=α+α1+2α2+3α3;

(2)

αα2=7+2α+α1+2α2+α3;

(3)

αα3=α+2α1+3α2+α3.

(4)

其中α=α0.

引理 2.3[15]设q为素数2的方幂,N={αi=αqi|i=0,…,3}为Fq4在Fq上的7-型高斯正规基,则N的对偶基B={βi=βqi|1=0,…,3}且

ββ=β1,ββ1=β3,

ββ2=β+β1+β2+β3,ββ3=β2,

其中β=β0.

引理 2.4[15]设q为素数3的方幂,N={αi=αqi|i=0,…,3}为Fq4在Fq上的7-型高斯正规基,则N的对偶基B={βi=βqi|1=0,…,3}且

ββ=β3,ββ1=β2,

ββ2=2β+2β1+2β2+2β3,ββ3=β1,

其中β=β0.

定理1.7的证明 1) 当p=2时,由引理2.2知,此时(1)～(4)式等价于

αα=α1,αα1=α+α1+α3,

αα2=1+α1+α3=α+α2,

αα3=α+α2+α3.

因此可以得到

α2=α1,α3=αα1=α+α1+α3,

α5=α2α3=αα1+α1α1+α1α3=

αα1+(αα)q+(αα2)q=α+α2,

类似地

α8=α3α5=α3,

α16=α3α3=(αα)q3=α,

进而,再由引理2.3可知

β2=β1,β3=β3,β4=β2,

β5=β+β1+β2+β3=Tr(β)=1.

β的乘法阶为5≠q4-1=15,即B不是本原正规基,这就证明了1).

2) 当p=3时,由引理2.2可知,此时(1)～(4)式等价于

αα=2α+2α3,αα1=α+α1+2α2,

αα2=1+2α+α1+2α2+α3=α+α2,

αα3=α+2α1+α3,

此时有

α2=2α+2α3,

α4=(2α+2α3)2=

αα+(αα)q3+2αα3=α+α1+2α2,

α5=2α+α1+α2+2α3,

α8=α+α1+2α2+α3,

α16=2α+α1+2α2+2α3,

α9=α2,α10=α+α2,

α20=α+2α1+α2+2α3,

α40=α+α1+α2+α3=Tr(α)=-1,

α80=1.

进而,由引理2.4有

β2=β3,β3=β1,β4=β2,

β5=2β+2β1+2β2+2β3=2Tr(β)=1.

β的乘法阶为5≠q4-1,B不是本原正规基.故定理1.7得证.

注 1 很多关于有限域上高斯正规基的复杂度和本原性的研究也只限于k值较小的情形,当k≥8时问题就变得很困难.与文献[15]讨论具体(n,k)取值时相应的高斯正规基的复杂度一样,本文继续讨论该类型高斯正规基及其对偶基的本原性,给出了具体(n,k)值时的分类计算方式.但和复杂度不同的是,特征p≠2,3时,该类正规基的本原性的确定尚未得以解决.

[1] MULLIN R, ONYSZCHUK I, VANSTONE S, et al. Optimal bases in GF(pm)[J]. Disc Appl Math,1988/1989,22(2):149-161.

[2] GAO S H. Nomal bases over finite fields[D]. Ontario:Waterloo University,1993.

[3] WASSERMANN A. Konstruktion von normal basen[J]. Bayreuther Mathematische Schriften,1990,31:155-164.

[4] LENSTRA Jr II W, SCHOOF R J. Primitive normal bases for finite fields[J]. Math Comput,1987,48(177):217-231.

[5] COHEN S D, HACHENBERGER D. Primitive normal bases with prescribed trace[J]. Appl Algebra Engrg Commun Comput,1999,9(5):383-403.

[6] FAN S, WANG X. Primitive normal polynomials with a prescribed coefficient[J]. Finite Fields Appl,2009,15:682-730.

[7] COHEN S D, HUCZYNSKA. The strong primitive normal basis theorem[J]. Acta Arith,2010,143(4):299-332.

[8] FAN S Q, HAN W B, ZHANG X Y. Primitive normal polynomials with the first two coefficients prescribed:a revisedp-adic method[J]. Finite Fields Appl,2007,13:577-604.

[9] LIAO Q Y. On primitive optimal normal elements of finite fields[J]. J Math Res Exp,2010,30(5):869-875.

[10] MENEZES A J, BLAKE I F, GAO S H, et al. Applications of Finite Fields[M]. New York:Kluwer Academic Publishers,1993.

[11] LIAO Q Y. The gaussian normal basis and its trace basis over finite fields[J]. J Number Theory,2012,132(7):1507-1518.

[12] 李俊,黄琴,李波,等. 有限域上的k-型高斯正规基及其对偶基[J]. 四川师范大学学报(自然科学版),2011,34(3):289-295.

[13] 廖群英,胡晓兰. 有限域上一类高斯正规基的复杂度的准确计算公式[J]. 数学学报,2014,57(5):863-874.

[14] 苏丹丹,廖群英. 有限域上一类特殊对偶基的推广[J]. 四川大学学报(自然科学版),2011,48(1):27-32.

[15] 魏杰,李雪连,廖群英. 有限域上的(4,7)型高斯正规基及其对偶基和迹基[J]. 四川大学学报(自然科学版),2016,53(1):7-12.

[16] 廖群英,苏丹丹,付萍. 有限域上2-型高斯正规基及其对偶基[J]. 四川大学学报(自然科学版),2010,47(6):1221-1224.

[17] 廖群英,李雪连. 有限域上(n,k) (k≥3)型高斯正规基的对偶基的复杂度(英)[J]. 四川大学学报(自然科学版),2016,53(2):235-246.

[18] 李雪连,廖群英. 偶特征有限域上一类高斯正规基的对偶基及迹基[J]. 四川师范大学学报(自然科学版),2015,38(6):802-809.

[19] 李波,廖群英. 有限域上的k-型高斯正规基的对偶基及其乘法表[J]. 四川师范大学学报(自然科学版),2013,36(6):824-829.

[20] 廖群英,胡晓兰. 有限域上高斯正规基的一个注记[J]. 四川师范大学学报(自然科学版),2015,38(2):159-163.

[21] 廖群英,李威,汤建刚. 有限域上一类自对偶正规基的乘法表与复杂度[J]. 四川师范大学学报(自然科学版),2014,37(1):31-36.

2010 MSC：12E20; 12E30; 11T99

(编辑 周 俊)

The Primitive Properties for the Type (4,7) Gauss Normal Basisand Its Dual Basis over Finite Fields

WEI Jie, LIAO Qunying, ZHOU Jiajun

(Institute of Mathematics and Software Science, Sichuan Normal University, Chengdu 610066, Sichuan)

Normal bases over finite fields are important in many efficient arithmetic implementations, such as coding theory and cryptography. In particular, primitive normal bases over finite fields have better properties and then are very important for applications. Recently, the explicit formula for the complexity of 7 type Gauss normal basesNofFq4overFqhas been obtained. The present paper continues to study the primitive properties forNand its dual basisB. Particularly, when the finite fieldFqhas characteristic 2 or 3, it proves thatNis a primitive normal basis if and only ifq=2 orq=3, in these case,Bis not primitive.

finite field; Gauss normal basis; dual basis; primitive element

2015-09-22

国家自然科学基金(11401408)和四川省教育厅重点科研项目(14ZA0034)

O156.1; O156.2

A

1001-8395(2016)06-0790-04

10.3969/j.issn.1001-8395.2016.06.002

*通信作者简介：廖群英(1974—),女,教授,主要从事编码与密码学的研究,Email:qunyingliao@sicnu.edu.cn