偶特征有限域上一類高斯正規基的對偶基及跡基

李雪連, 廖群英(四川師范大學 數學與軟件科學學院, 四川 成都 610066)

?

偶特征有限域上一類高斯正規基的對偶基及跡基

李雪連, 廖群英*
(四川師范大學 數學與軟件科學學院, 四川 成都 610066)

設q為2的方冪,文獻(李波,廖群英. 數學進展,2015,44(3):394-404.)確定了Fqn在Fq上的一類特殊的高斯正規基及其對偶基的生成元.進一步完全確定了這類正規基的對偶基及跡基的乘法表和復雜度,從而完善了主要結果.并證明了這類正規基的跡基是最優正規基.

有限域; 高斯正規基; 對偶基; 跡正規基; 乘法表; 復雜度

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為最優正規基,進而給出了兩類最優正規基的構造定理,分別為Ⅰ型最優正規基和Ⅱ型最優正規基,并猜想最優正規基只有這2類.隨后,S. Gao等[2-3]證明了這個猜想.從而尋找次優的正規基也成了很重要的課題.1990年,A. Wassermann[4]把最優正規基推廣到高斯正規基,而這正是一類低復雜度的正規基.

k-型高斯正規基的構造定理[4]設q為素數p的方冪,k和n是正整數,滿足kn+1是素數且(kn+1,p)=1.假定δ∈Fqn是kn+1次本原單位根,s是q模kn+1的次數.若(kn/s,n)=1,l是Zkn+1中k次本原單位根,則

生成Fqn在Fq上的正規基N,且其復雜度滿足

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

注 1 當k=1時,1-型高斯正規基即是Ⅰ型最優正規基;當q=k=2時,2-型高斯正規基即是Ⅱ型最優正規基.

2005年,廖群英等[5]給出了有限域Fqn在Fq上Ⅰ型最優正規基和Ⅱ型最優正規基的乘法表;2012年,M. Christopoulou等[6]給出了k=3,4,5,6時,有限域Fqn在Fq上的k-型高斯正規基的乘法表和復雜度的準確公式;廖群英等[7]把文獻[6]的結果推廣到一般情形,給出了有限域Fqn在Fq上一類k-型高斯正規基的乘法表和復雜度的具體計算公式.

另一方面,在有限域的眾多基中,對偶基也是一個很重要的概念.對于Fqn在Fq上的任意2組基:

B={βi=βqi|i=0,1,…,n-1},

N={αi=αqi|i=0,1,…,n-1},

稱B為N的對偶基,若對任意的i,j=0,1,…,n-1,都有

其中

是γ∈Fqn在Fq上的跡映射.文獻[8]證明了有限域上正規基的存在性,對偶基的存在唯一性以及正規基的對偶基仍為正規基等.2012年,Q. Y. Liao等[9]給出了高斯正規基的對偶基,即證明了如下的結果:

引理 1.1 設q為素數p的方冪,N={α,αq,…,αqn-1}為Fqn在Fq上的k-型高斯正規基(1≤k≤n),則N的對偶基的生成元為

眾所周知,在編碼理論、密碼體制等領域,低復雜度的正規基得到廣泛應用[10-12].例如,域F2上元素乘法是實現橢圓曲線公鑰密碼體制(ECC)的核心運算.由文獻[13]可知有限域上的正規基特別是最優正規基更適用于硬件實現,可見尋找低復雜的正規基很重要.設Tr是γ∈F2n在F2上的跡映射,李波等[14]研究了F2n在F2上滿足條件

的高斯正規基N={αi=αqi|i=0,1,…,n-1}.證明了:當n=4,8,16時,N滿足條件P;但當n=32時,F2n在F2上不存在滿足條件P的正規基,并進一步給出偶特征有限域上滿足條件P的正規基的存在性條件,即證明了如下的結果.

引理 1.2[14]設n≥k>1,q為2的方冪,N為Fqn在Fq上的k-型高斯正規基,則

1) 當k≡0(mod 2)時,N不滿足條件P.

2) 當k≡1(mod 2)時,N滿足條件P當且僅當n=4且k=1或者k=3.

本文進一步研究偶特征有限域上滿足條件P的高斯正規基,給出了其對偶基與跡基的乘法表和復雜度等,即證明了如下主要結果.

定理 1.3 設n≥k>1,q為2的方冪,N為Fqn在Fq上滿足條件P的k-型高斯正規基,B為N的對偶基,CB為B的復雜度,則B滿足條件P,且

定理 1.4 設q為2的方冪,N為Fqn在Fq上滿足條件P的k-型高斯正規基,M為N的跡正規基,則M是Fq2在Fq上的最優正規基.

2 主要結果的證明

為證明定理1.3和1.4,需要如下幾個引理.

引理 2.1[15]設q為素數p的方冪,

N={α,αq,…,αqn-1}

是Fqn在Fq上的k-型高斯正規基,

是α∈Fqn在Fq上的跡映射,則Tr(α)=-1.

引理 2.3[16]設q為素數p的方冪,n是正整數,Fqn是有限域Fq的n次擴張(n≥2).若正整數m為n的因數,且N={α,αq,…,αqn-1}為Fqn在Fq上的正規基,則

生成Fqm在Fq上的正規基M={γ,γq,…,γqm-1},稱為N的跡正規基.

定理1.3的證明 設N={αi=αqi|i=0,1,2,3}是Fq4在Fq上滿足條件P的k-高斯正規基,則由引理1.2可知q為2的方冪且k=1或3.設

B={βi=βqi|i=0,1,2,3}

為N的對偶基,注意到q為2的方冪且k=1或3,故由引理1.1可得

于是相應地有

β1=βq=1+α3,

β2=β1q=1+α0,

β3=β2q=1+α1.

(1)

從而由αi=αqi(i=0,1,2,3)可得

ββ0=(1+α2)2=

1+α2α2=1+(αα0)q2,

(2)

ββ1=(1+α2)(1+α3)=

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

(3)

ββ2=(1+α2)(1+α)=

1+α2+α+α2α,

(4)

ββ3=(1+α2)(1+α1)=

1+α2+α1+α1α2.

(5)

情形一 當k=1時,N是Ⅰ型最優正規基,于是由文獻[5]的定理1可知N的乘法表T=(tij)4×4滿足:當j=0,1,2,3時,有t2,j=-1;當i=0,1,3時,

又由k=1,n=4以及k-型高斯正規基的構造定理可知,q模5的階為4,從而

或

進而由q是2的方冪,可知N的乘法表T=(tij)4×4形如

(6)

或

(7)

1) 若N的乘法表為(6)式,則

αα0=α1,αα1=α3,

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

(8)

又由引理2.1知1=Tr(α)=α+α1+α2+α3,其中Tr是Fq4到Fq上的跡映射.從而由(2)～(5)式及(8)式可得

ββ0=1+(αα0)q2=

1+(α1)q2=1+α3=β1,

(9)

ββ1=1+α2+α3+α2α3=

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

(10)

ββ2=1+α2+α+α2α=

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

(11)

以及

ββ3=1+α2+α1+α0=β+β2+β3.

(12)

故此時B的乘法表為

且CB=9.進而由引理2.1,以及(1)、(9)～(12)式可知

即B也滿足條件P.

2) 若N的乘法表為(7)式,則

αα0=α3,αα1=α2,

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

(13)

于是由(2)～(5)以及(13)式得到:

ββ0=1+(α3)q2=1+α1=β3,

(14)

ββ1=1+α2+α3+α2α3=

1+α2+α3+α0=β+β1+β2,

(15)

ββ2=1+α2+α+α2α=

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

β+β2,

(16)

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

(17)

從而相應的B的乘法表為

即CB=9.進而由引理2.1,以及(1)、(14)～(17)式有

因此B也滿足條件P.綜上可知,CB=9且B也滿足條件P,即定理1.3的第一種情形成立.

(18)

同理

(19)

和

(20)

以及

(21)

于是由(1)～(5)式可知,相應地

(22)

(23)

(24)

注 2 由正規基的概念可知ββ2=0的情形是不存在的,所以ββ2只可能有以下5種情形

ββ2=1+α2+α+α2α=

(25)

以及

ββ3=1+α2+α1+α1α2=

(26)

于是由正規基的乘法表及復雜度的定義可知,B的復雜度CB滿足

7=2n-1≤CB≤1+3+4+3=11.

又由引理2.1,以及(22)～(23)、(25)～(26)式可得

故此時B也滿足條件P.這就證明了定理1.3的第二種情形.

定理1.4的證明 由N滿足條件P,及引理1.2知q為2的方冪且n=4,k=1或k=3.于是由引理2.3可知N的跡正規基M={γ,γq},其中Tr是Fq4到Fq2上的跡映射,且

γ=Tr(α)=α+αq2=α+α2∈Fq2/Fq, (27)

γq=Tr(αq)=αq+αq3=α1+α3∈Fq2/Fq. (28)

情形一 當n=4且k=1時,由定理1.3第一種情形的證明,可知有如下2種情形.

1) 當N的乘法表為(6)式時,即

αα0=α1,αα1=α3,

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

故

γγ=(α+αq2)(α+αq2)=αα+α2α2=

αα+(αα)q2=α1+(α1)q2=α1+α3=γq,

γγq=(α+αq2)(α+αq3)=

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

α3+α2+(αα1)q+(αα1)q2=

α3+α2+(α3)q+(α3)q2=

α3+α2+α+α1=γ+γq.

因此M的乘法表

故CM=3.

2) 當N的乘法表為(7)式時,類似可得

故CM=3=2×2-1.

綜上可知,當n=4,且k=1時,N的跡正規基M是Fq2在Fq上的最優正規基.

情形二 當n=4,k=3時,由(27)～(28)式可知:

γγ=(α+αq2)(α+αq2)=

αα+α2α2=αα+(αα)q2,

γγq=(α+α2)(α1+α3)=

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

αα1+αα3+(αα1)q+(αα1)q2.

故γγ,γγq的取值決定于αα,αα1,αα3.而由(18)～(21)式知αα有3種取法,αα1有4種取法,αα3有4種取法,且αα1≠αα3.故有以下22種情形.

情形1:當αα=α1,αα1=α+α1+α2,αα3=α+α1+α3時,

γγ=αα+(αα)q2=α1+α3=γq,

γγq=αα1+αα3+(αα1)q+(αα1)q2=

α+α2+α1+α3=γ+γq.

于是

故CM=3.

情形2:當αα=α1,αα1=α+α1+α2,αα3=α1+α2+α3時.

情形3:當αα=α1,αα1=α+α2+α3,αα3=α1+α2+α3時.

情形4:當αα=α1,αα1=α+α1+α3,αα3=α+α2+α3時.

情形5:當αα=α1,αα1=α1+α2+α3,αα3=α+α1+α2時.

情形6:當αα=α3,αα1=α+α1+α2,αα3=α+α1+α3時.

情形7:當αα=α3,αα1=α+α1+α2,αα3=α1+α2+α3時.

情形8:當αα=α3,αα1=α+α2+α3,αα3=α1+α2+α3時.

情形9:當αα=α3,αα1=α+α1+α3,αα3=α+α2+α3時.類似都可以得到

故CM=3.

情形10:當αα=α1,αα1=α+α1+α2,αα3=α+α2+α3時,

γγ=αα+(αα)q2=α1+α3=γq,

γγq=αα1+αα3+(αα1)q+(αα1)q2=

α+α1+α2+α+α2+α3+

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

α+α3.

又由引理2.1知:α+α2+α1+α3=-1,即γ+γq=-1=1,q≡0(mod2).注意到:(α+α3)q2=α1+α2且α+α3=γγq∈Fq2,于是(α+α3)q2=α+α3,故α1+α2=α+α3,從而α1+α2+α+α3=0,與引理2.1矛盾,故此情形不成立.

情形11:當αα=α1,αα1=α+α2+α3,αα3=α+α1+α3時.

情形12:當αα=α1,αα1=α+α2+α3,αα3=α+α1+α2時.

情形13:當αα=α1,αα1=α+α1+α3,αα3=α+α1+α2時.

情形14:當αα=α1,αα1=α+α1+α3,αα3=α1+α2+α3時.

情形15:當αα=α1,αα1=α1+α2+α3,αα3=α+α2+α3時.

情形16:當αα=α1,αα1=α1+α2+α3,αα3=α+α1+α3時.

情形17:當αα=α3,αα1=α+α1+α2,αα3=α+α2+α3時.

情形18:當αα=α3,αα1=α+α2+α3,αα3=α+α1+α3時.

情形19:當αα=α3,αα1=α+α2+α3,αα3=α+α1+α2時.

情形20:當αα=α3,αα1=α+α1+α3,αα3=α+α1+α2時.

情形21:當αα=α3,αα1=α+α1+α3,αα3=α1+α2+α3時.

類似可得到這些情形都有:α1+α2+α+α3=0,與引理2.1矛盾.

情形22:即αα=α2時,γγ=αα+(αα)q2=α+α2=γ,從而γ=1或0,這與γ生成跡正規基N相矛盾.

綜上所述M的乘法表為

且CM=3,故M是Fq2在Fq上的最優正規基.這就證明了定理1.4.

3 舉例

本節考慮q=2和q=8時,Fq4在Fq上滿足條件P的3-型高斯正規基的對偶基及跡基的乘法表和復雜度.

生成F24在F2上的3-型高斯正規基N,并且

α1=α2=(δ+δ3+δ9)2=

δ2+δ6+δ18=δ2+δ6+δ5,

α2=α12=(δ2+δ6+δ5)2=δ4+δ12+δ10,

α3=α22=(δ4+δ12+δ10)2=

δ8+δ20+δ24=δ8+δ7+δ11.

從而

αα0=α2=α1,

αα1=(δ+δ3+δ9)(δ2+δ6+δ5)=α+α1+α3,

αα2=(δ+δ3+δ9)(δ4+δ10+δ12)=α+α2,

αα3=(δ+δ3+δ9)(δ7+δ8+δ9)=α+α2+α3.

故由α生成的F24在F2上的3-型高斯正規基N的乘法表為

從而N的復雜度CN=9.進而設N的對偶基

B={βi=β2i|0≤i≤3},

則由引理1.1以及(1)～(5)式可知

ββ0=1+α22=1+α3=β1,

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

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

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

即B的乘法表為

從而B的復雜度CB=9.又設N的跡正規基M={γ,γ2},則由引理2.3知

γ=Tr(α)=α+α22=α+α2,

γ2=Tr(α2)=α2+α23=α1+α3.

故

γγ=αα+(αα)22=α1+α3=γ2,

γγ2=αα1+αα3+(αα1)2+(αα1)22=

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

于是

且CM=3.

生成F84在F8上的3-型高斯正規基N,并且

α1=α8=(δ+δ3+δ9)8=

δ8+δ24+δ72=δ8+δ11+δ7,

α2=α18=(δ8+δ11+δ7)8=

δ64+δ88+δ56=δ12+δ10+δ4,

α3=α28=(δ12+δ10+δ4)8=

δ96+δ80+δ32=δ5+δ2+δ6.

從而

αα0=(δ+δ3+δ9)2=δ2+δ6+δ5=α3,

αα1=(δ+δ3+δ9)(δ7+δ8+δ11)=α+α1+α2,

αα2=(δ+δ3+δ9)(δ4+δ10+δ12)=α+α2,

αα3=(δ+δ3+δ9)(δ5+δ2+δ6)=α+α1+α3.

故由α生成的F84在F8上的3-型高斯正規基N的乘法表為

且N的復雜度CN=9.進而設N的對偶基

B={βi=β8i|0≤i≤3},

則由引理1.1以及(1)～(5)式可知:

ββ0=1+α22=1+α1=β3,

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

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

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

從而B的乘法表為

且B的復雜度CB=7.可見此對偶基B是F84在F8上的最優正規基.又設N的跡正規基M={γ,γ8},則由引理2.3知

γ=Tr(α)=α+α82=α+α2,

γ8=Tr(α8)=α8+α83=α1+α3.

故

γγ=αα+(αα)82=α1+α3=γ8,

γγ8=αα1+αα3+(αα1)8+(αα1)82=

α+α2+α1+α3=γ+γ8.

于是

且CM=3.

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

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

[2] Gao S, Lenstra H Jr. Optimal normal bases[J]. Design,Codes and Cryptography,1992,2:315-323.

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

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

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

[6] Christopoulou M, Garefalakis T, Panario D, et al. Gauss periods as constructions of low complexity normal bases[J]. Designs,Codes Cryptography,2012,62(1):43-62.

[7] 廖群英,胡曉蘭. 有限域上一類高斯正規基的復雜度的準確計算公式[J]. 數學學報,2014,57(5):863-874.

[8] Menezes A J, Blake I F, Gao X H, et al. Applications of Finite Fields[M]. New York:Kluwer Academic Publishers,1993.

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

[10] Beth T. Generalizing the discrete fourier transform[J]. Discrete Math,1985,56:95-100.

[11] Diffie W, Hellman M. New directions in cryptography[J]. IEEE Trans Inform Theory,1976,22:644-654.

[12] Fumy W. orthogonal transform encoding of cyclic codes[C]//Algebraic Algorithms and Error-Correcting Codes. Lecture Notes Comput Sci. Berlin:Spring-Verlag,1986,229:131-134.

[13] Dahab R, Hankerson D. Software multiplication using gaussian normal basis[J]. IEEE Transaction on Computers,2006,55(8):974-984.

[14] 李波,廖群英. 偶特征有限域上一類正規基及其對偶基[J]. 數學進展,2015,44(3):394-404.

[15] 李俊,黃琴,李波,等. 有限域上k-型高斯正規基及其對偶基[J]. 四川師范大學學報:自然科學版,2011,34(3):289-295.

[16] Christopoulou M, Garefalakis T, Panario D, et al. The trace of an optimal normal element and low complexity normal bases[J]. Designs,Codes Cryptography,2008,49(1/2/3):199-215.

2010 MSC：12E20

(編輯 陶志寧)

The Trace and Dual Bases of Some Special Gaussian Normal Bases over Finite Fields with Even Characteristic

LI Xuelian, LIAO Qunying
(CollegeofMathematicsandSoftwareScience,SichuanNormalUniversity,Chengdu610066,Sichuan)

Letqbe a power of 2. Recently, the dual basis of some special Gaussian normal base of the finite filedFqnoverFqis determined in literature(Li B, Liao Q Y. Adv Math(China),2015,44(3):394-404.). The present paper continues the study and determines the complexity of the dual and trace basis for the above Gaussian normal bases completely, and it is proved that the trace basis is optimal.

finite field; Gauss normal basis; dual basis; trace normal basis; multiplication table; complexity

2014-08-22

國家自然科學基金(11401408)和四川省教育廳重點項目基金(14ZA0034)

O156.2; O157.4

A

1001-8395(2015)06-0802-08

10.3969/j.issn.1001-8395.2015.06.003

*通信作者簡介：廖群英(1974—),女,教授,主要從事編碼與密碼學理論的研究,E-mail:qunyingliao@sicnu.edu.cn.