關于有限域上特殊本原元的存在性

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

?

關于有限域上特殊本原元的存在性

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

設Fq為有限域,文獻(P. P. Wang, et al. Finite Fields and Their Applications,2012,18(4):800-813.)給出了特征為2的有限域Fq中存在α∈Fq使得α和α+α-1都是Fq中本原元的幾個充分條件,隨后,文獻(Q. Y. Liao, et al. Chin Annals Math,2015, in press.)將其結果推廣到任意特征的有限域上.討論任意特征的有限域Fq中存在2個本原元α,β,使得α+β亦為本原元的幾個充分條件,進而,利用特征和的方法得到一個滿足此條件的q的下界q0=4.98×1086.最后,利用計算機驗證了特征為2的有限域除F2與F4外均滿足此條件.

有限域; 本原元; 乘法特征; 特征和

有限域作為一種特殊的域,在編碼理論、組合設計、密碼學等許多實際領域都有著非常廣泛的應用[1-4].特別是20世紀中期以來,隨著計算機技術的發展,有限域的地位愈加重要,許多從事應用研究的數學家開始有限域的理論研究,有限域理論已經成為許多工程技術人員不可缺少的數學工具.另一方面,有限域理論本身也引起人們的廣泛興趣,其中許多問題推動著數學的發展[5].

設q是素數方冪,Fq是q元有限域.熟知,Fq*=Fq{0}為循環群,其生成元稱為有限域Fq的本原元.有限域上的本原元在有限域的代數結構中起著至關重要的作用,而且由于有限域理論在各個專業領域中的廣泛應用,有限域上的本原元已經成為一個熱點問題.1984年,S. W. Golomb[6]在研究Costas陣列的設計問題時,提出如下猜想:存在正整數q0,使得當素數方冪q>q0時,有限域Fq的任一非零元皆可表為其2個本原元的和.

對于此猜想,孫琦[7]給出了一個下界q0=260,常彥勛亦給出了當q>6.62×107,且q≠3.006 903 91×108時,Fq的任一非零元皆可表為其2個本原元的和[8],基本解決了此猜想.此外,文獻[9-10]研究了更一般的問題:存在正整數q0,當q>q0時,對任意a,b,α∈Fq,均存在Fq的2個本原元x和y使得ax+by=α并得到了與Golomb猜想類似的結果.賀龍斌等[11]解決了形如α+α-1的本原元存在的條件,P. P. Wang等[12]進一步研究了特征為2的有限域Fq中使得α和α+α-1都是Fq中本原元的元素α的存在性條件,隨后,Q. Y. Liao等[13]將其結果推廣到了一般的有限域.

本文在此基礎上進一步討論在什么條件下,有限域Fq中存在2個本原元α和β,使得α+β亦為Fq中的本原元,即尋找素數方冪q屬于集合

U={q|存在Fq中元素α,β使得α,β,

α+β均為Fq中的本原元}

的一些充分條件.

本文用特征和估計的方法得到如下主要結果.

定理 1 設Fq為q元有限域,若q滿足q>24ω(2ω-1)2,其中ω=ω(q-1)為q-1的不同素因子個數,則q∈U.

推論 2 設Fq為q元有限域,若ω(q-1)≥49,則q∈U.

推論 3 設Fq為q元有限域,若q>4.98×1086,則q∈U.

1 預備知識

關于有限域的基本性質可參見文獻[5].本節主要介紹有限域的乘法特征的相關性質,其他詳細性質可見文獻[14].

根據引理4,易知對任意η∈Fq,均有

從而有如下結果.

).

下面關于乘法特征和的估計是本文證明主要結果的關鍵.

引理 6[15]設fi(T)(i=1,2,…,n)是Fq[T]中兩兩互素的無平方因子的首1多項式,degfi=di(1≤i≤n).若χ1,χ2,…,χn為Fq的非平凡的乘法特征,則有

設ξ∈Fq,d為正整數.定義

這里μ為莫比烏斯函數,ord(χ)表示乘法特征χ的階.則有如下結論.

引理 7[16]設ξ∈Fq,d|q-1.P(ξ)的定義如上所示,則有

2 主要結果的證明

N1+N2+…+N8,

(1)

其中

P(b,β)P(c,α+β).

下面分別計算Ni(1≤i≤8),易知

(2)

對于N2有

N2=0.

(3)

對于N3有

N3=0.

(4)

對于N4,類似于N3的計算,同理可知

N4=0.

(5)

對于N5有

(6)

對于N6有

(7)

對于N7,與N6的計算類似的有

(8)

最后,對于N8有

(9)

由(1)～(9)式可知

|N(q)-N1|≤|N6|+|N7|+|N8|.

因此,欲使N(q)>0,只需N1>|N6|+|N7|+|N8|,即

(10)

易知,(10)式成立的一個充分條件為

此式等價于

(11)

又由定理1可知,若

則q∈U.

通過計算可知,當ω<49時,I(ω)<0,且I(49)>0.

以下證明:對任意n≥49,均有I(n)>0.對n作歸納證明.

當n=49時,結論成立.

現設n≥49且I(n)>0,則有

Pn24n(2n-1)2-24(n+1)(2n+1-1)2=

Pn24n(2n-1)2-16·24n(2·2n-1)2.

由于n≥49,所以Pn>144,從而

I(n+1)>144·24n(2n-1)2-

16·24n(2·2n-1)2=

16·24n·[9(2n-1)2-(2·2n-1)2].

又由3(2n-1)≥2·2n-1,可知I(n+1)>0.

這就證明了推論2.

推論3的證明.由定理1及推論2可知:若q?U,則ω(q-1)<49且q≤24ω(2ω-1)2.容易看到24ω(2ω-1)2是關于ω的增函數,所以當q>24·48(248-1)2時,q∈U.而24·48(248-1)2≈4.97×1086,故當q>4.98×1086時,q∈U.

3 特征為2的情形

推論3給出了q滿足條件q∈U的一個下界q0=4.98×1086,對所有的q=2s≤q0,用數學軟件maple進行逐一篩選與計算,得到如下結論.

定理 8 除去F2、F4外,所有特征為2的有限域Fq(q=2s)均滿足q∈U.

證明 對于F2,其單位元1是唯一的本原元.而對于F4={0,1,θ,1+θ},其中θ為F2上不可約多項式T2+T+1的根,其全部本原元為θ,1+θ.所以2,4均不屬于U.

以下考慮F2s,其中s≥3.由于q0=4.98×1086,故[log2q0]=288,其中[·]為高斯取整函數.因此3≤s≤288.此時由定理1及推論2知,要確定集合

S={s|s<288,ω(2s-1)<49,

q>24ω(2s-1)(2ω(2s-1)-1)2}.

由如下的程序1計算可知

S={2,3,4,6,8,9,10,11,12,14,15,16,

18,20,22,24,28,30,36,40,48,60}.

其次,對所有s∈S,利用如下的程序2來實際查找F2s中滿足條件的本原元α和β.經計算與驗證可知定理8成立.

程序 1

restart

with(numtheory)

w:=x->nops(factorset(x))

w0:=48

i:=1

q:=2i

exception:=NULL

while q

if w(q-1)<49 and q-24*w(q-1)(2w(q-1)-1)2<=0 then

exception:=exception,i

end if

i:=i+1

q:=2i

end do

print(exception)

程序 2

Lastexception:=NULL

for s in exception do

G:=GF(2,s)

PE:=G:-PrimitiveElement()

N:=0

for i from 1 to 2s-2 do

for j from i+1 to 2s-1 do

if igcd(i,2s-1)=1 and igcd(j,2s-1)=1 then

PEI:=G:-`'(PE,i)

PEJ:=G:-`'(PE,j)

SUM:=G:-`+`(PEI,PEJ)

if G:-isPrimitiveElement(SUM)=true then

N:=1

break

end if

end if

end do

if N=1 then

break

end if

end do

if N=0 then

Lastexception:=Lastexception,s

end if

end do

print(Lastexception)

實際上,對每一個s∈S,均利用程序2具體的給出相應的F2s中滿足α+β為本原元的2個本原元α和β.但由于當s較大時,其表達式較為繁復,在此僅給出其中2例.

例 2 對于s=8的情形,即F28=F2(θ),其中θ為不可約多項式T8+T7+T5+T3+1的根.取兩本原元α=T7+T5+T4+T3+T2,β=T6+T4+T3+1.則容易驗證α+β=T7+T6+T5+T2+1亦為本原元,所以28∈U.

[1] 馮克勤. 糾錯碼的代數理論[M]. 北京:清華大學出版社,2005.

[2] 周玉潔,馮登國. 公開密鑰密碼算法及其快速實現[M]. 北京:國防工業出版社,2002.

[3] 李欣妍,蘆殿軍. 基于橢圓曲線密碼體制的代理多重盲簽名[J]. 計算機工程與科學,2010,32(11):58-59.

[4] 陳家琪,馮俊,郝妍. 無證書密鑰協商協議對跨域Kerberos的改進[J]. 計算機工程,2010,36(20):150-152.

[5] 林東岱. 代數學基礎與有限域[M]. 北京:高等教育出版社,2006.

[6] Golomb S W. Algebraic constructions for Costas arrays[J]. J Combinatorial Theory,1984,A37(1):13-21.

[7] 孫琦. 關于有限域中的元根[J]. 四川大學學報:自然科學版,1988,25(2):133-139.

[8] 常彥勛,康慶德. 有限域中非零元表為兩本原元和的問題[J]. 中國科學,1990,A11:1146-1153.

[9] 常彥勛. 有限域的本原元性質[J]. 數學雜志,1993,13(1):59-63.

[10] 王巨平. Golomb猜想[J]. 中國科學,1987,A9:927-935.

[11] 賀龍斌,韓文報. 有限域上形如α+α-1的本原元的研究[J]. 信息工程大學學報,2003,4(2):97-98.

[12] Wang P P, Cao X W, Feng R Q. On the existence of some specific elements in finite fields of characteristic 2[J]. Finite Fields and Their Applications,2012,18(4):800-813.

[13] Liao Q Y, Li J Y, Pu K L. On the existence for some special primitive elements in finite fields[J]. Chinese Annals of Mathematics,2015, in press.

[14] 馮克勤,廖群英. 有限域及其應用[M]. 大連:大連理工大學出版社,2011.

[15] Wan D Q. Generators and irreducible polynomials over finite fields[J]. Mathematics of Computation of the American Mathematical Society,1997,66(219):1195-1212.

[16] Cohen S D. Primitive roots in the quadratic extension of a finite field[J]. J London Mathematical Society,1983,2(2):221-228.

2010 MSC：11T30

(編輯 鄭月蓉)

On the Existence for Specific Primitive Elements over Finite Fields

LIAO Huan, LIAO Qunying
(CollegeofMathematicsandSoftwareScience,SichuanNormalUniversity,Chengdu610066,Sichuan)

Let Fqbe theqelements finite field. The literature(P. P. Wang, et al. Finite Fields and Their Applications,2012,18(4):800-813.) obtains several sufficient conditions for the existence ofα∈ Fqsuch thatαandα+α-1are both primitive elements in Fq. Recently, the work(Q. Y. Liao, et al. Chin Annals Math,2015, in press.) generalizes their main results to the finite field with arbitrary characteristics. In this paper, we obtain a sufficient condition for the existence of the finite field Fqin which there exist two primitive elementsα,β∈ Fq, such that α+β is also a primitive element of Fq. Furthermore, for finite fields satisfying this condition, by using character sums, we get a lower bound of the correspondingq. Finally, we verify that the condition is true for all finite fields with characteristic 2 except F2and F4.

finite field; primitive element; multiplicative character; character sum

2013-12-19

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

O153.4

A

1001-8395(2015)06-0797-05

10.3969/j.issn.1001-8395.2015.06.002

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