張大雷，陳磊

（淮南師范學(xué)院計(jì)算機(jī)學(xué)院，安徽淮南232038）

2ip+1型素?cái)?shù)及其原根

張大雷，陳磊

（淮南師范學(xué)院計(jì)算機(jī)學(xué)院，安徽淮南232038）

費(fèi)馬素?cái)?shù)作為2ip+1型素?cái)?shù)的特例，首先證明了3是除3以外的費(fèi)馬素?cái)?shù)的原根，接著研究了2ip+1型素?cái)?shù)的另外一種特例，證明了-2是安全素?cái)?shù)Q7的原根；并進(jìn)一步證明對(duì)于q=8p+1型素?cái)?shù)，當(dāng)q≠41時(shí)，3是模q的原根。

費(fèi)馬素?cái)?shù)；安全素?cái)?shù)；原根；二次剩余

原根是數(shù)論中的一個(gè)重要概念①潘承洞，潘承彪：《初等數(shù)論》，北京：北京大學(xué)出版社，1992年，第198-214頁。，在密碼學(xué)等領(lǐng)域中有著大量的應(yīng)用，是很多密碼學(xué)協(xié)議的基礎(chǔ)②Niederreiter H,"A survey of some applications of finite fields'',Designs,Codes and Cryptography,Vol.78.No.1,2016,pp.129-139.,有關(guān)原根的求解問題一直以來沒有一種通用的確定性算法③④⑤⑥Sun Z W,''On functions taking only prime values'',Journal of Number Theory,Vol.133,No.8,2013,pp.2794-2812.，但是，對(duì)于一些特殊類型的素?cái)?shù)，已有關(guān)于原根求解算法的相關(guān)研究。

2001年，文獻(xiàn)⑦Kek M,Somer L,''A necessary and sufficient condition for the primality of Fermatnumbers'',Mathematica Bohemica,Vol.126,No.3,2001,pp.541-549.提出費(fèi)馬數(shù)素性判定的一個(gè)充要條件，即原根之集合等價(jià)于二次非剩余之集合。2009年，文獻(xiàn)⑧周娟，周尚超：《素?cái)?shù)原根的兩個(gè)猜想》，《華東交通大學(xué)學(xué)報(bào)》2009年第6期，第98-100、130頁。通過編程計(jì)算的方法，提出兩個(gè)有關(guān)原根的猜想，2是所有q=4p+1型素?cái)?shù)的原根，其中p為素?cái)?shù)；當(dāng)安全素?cái)?shù)q=8p+3時(shí)，2是q的最小原根；當(dāng)安全素?cái)?shù)q=8p+7時(shí)，2不是q的最小原根。2012年，文獻(xiàn)⑨Sorin Iftene,''Some connections between primitive roots and quadratic non-residuesmodulo a prime'',IACR Cryptology ePrint Archive.給出了求解安全素?cái)?shù)原根的確定性算法，算法時(shí)間復(fù)雜度為Ο((log2(p))2)，改進(jìn)了以往求解原根的概率算法。2013年，文獻(xiàn)⑩藺冰：《關(guān)于2ipj+1型素?cái)?shù)及其原根》，《蘭州大學(xué)學(xué)報(bào)》（自然科學(xué)版）2013年第5期，第719-721頁。證明了文獻(xiàn)[11]同⑧。提出的兩個(gè)猜想，并進(jìn)一步證明當(dāng)q=2ip+1,i≥3，其中p為素?cái)?shù)，2不是q的最小原根。

本文中沿用文獻(xiàn)[12]同⑩。對(duì)符號(hào)的約定：P表示奇素?cái)?shù)集合。Qi,j={q|q=2ipj+1,p∈P},Q1,1={q|q=2p+1,p∈P}，Q1,1=Q3∪Q7，其中Q3={q|q∈Q1,1,q=3(mod8)},Q7={q|q∈Q1,1,q=7(mod8)}。

本文在文獻(xiàn)[13]同⑩。的基礎(chǔ)上，對(duì)2ip+1類型的素?cái)?shù)及其原根做進(jìn)一步研究，證明了：當(dāng)費(fèi)馬素?cái)?shù)Fn〉3時(shí)，3是模Fn的原根；設(shè)安全素?cái)?shù)q∈Q7，則-2是模q的原根；設(shè)q∈Q3,1，則當(dāng)q≠41時(shí)，3是模q的原根。

引理1假定p是奇素?cái)?shù)，α是模p的原根，那么α是模p的二次非剩余。

證明由文獻(xiàn)①潘承洞，潘承彪：《初等數(shù)論》，北京：北京大學(xué)出版社，1992年，第249頁。中的定理4，α是模p的原根，那么對(duì)于(p-1)的任意素因子r，都有(mod p)。令r=2,那么(mod p)。根據(jù)費(fèi)馬小定理,只有和兩個(gè)模的11-1p平方根，所以。因此，α是模p的二次非剩余。

引理2假定p是奇素?cái)?shù)，α是模p的二次非剩余，那么α是模p的原根，當(dāng)且僅當(dāng)p)，r是(p-1)的任意奇素因子。

證明由文獻(xiàn)②同①。中的定理4，歐拉判定準(zhǔn)則(Euler's criterion)，可以直接得到引理2。

證明由引理1和引理2，可以直接得到引理3。

當(dāng)Fn〉3時(shí)，有Fn=1（mod 4）

由于22=1（mod3），因此Fn=2（mod 3），即3是模Fn的二次非剩余，由引理3可得，3是模Fn的原根，證畢。

定理2設(shè)q∈Q3，則2是模q的原根。

證明見文獻(xiàn)③藺冰：《關(guān)于2ipj+1型素?cái)?shù)及其原根》，《蘭州大學(xué)學(xué)報(bào)》（自然科學(xué)版）2013年第5期，第719-721頁。。

引理4對(duì)于奇素?cái)?shù)p，2是模p的二次剩余，當(dāng)且僅當(dāng)p=±1(mod 8)。2是模p的二次非剩余，當(dāng)且僅當(dāng)p±3(mod8)。

引理5對(duì)于安全素?cái)?shù)p=2q+1,若α是模p的二次非剩余，并且α∈{2,3,···，p-2},那么α是模p的原根。

定理3設(shè)q∈Q7，則-2是模q的原根。

證明根據(jù)引理4，由于2是模q的二次剩余，-1是模q的二次非剩余，所以-2也是模q的二次非剩余。

由于-2=p-2∈{2,3,···,p-2}，由引理5可得，-2是模q的原根。

定理4設(shè)q∈Q2,1，則2是q模的原根。

證明見文獻(xiàn)④同③。。

定理5設(shè)q∈Q3,1，則當(dāng)q≠41時(shí)，3是模q的原根。

證明Q3,1={q|q=8p+1,p∈P}，由二次互反律，

由于p是素?cái)?shù)，故p模3只有兩種可能：p=1(mod 3)或p=2(mod 3)。當(dāng)p=3k+1時(shí)，8p+1=8(3k+1)+1=24k+9不可能為素?cái)?shù)，所以只能是p=2(mod 3)，因此8p=1(mod 3)，所以有q=2(mod 3)=-1，，即3是模q的二次非剩余，令R={r|r=38modq,p∈P&(q=8p+1)〈(38=6561)},則|R|=28，其中僅當(dāng)q=41時(shí)，r=1，q取其它值時(shí)，均有r≠1。而當(dāng)q〉6561時(shí)，顯然38mod q=6561。因此，當(dāng)q≠41時(shí)

綜上，由于q=8p+1僅有{2,p}兩個(gè)素?cái)?shù)因子，由文獻(xiàn)⑤同①。中的定理4，當(dāng)q≠41，3是模q的原根。

On primitive roots modulo primes of the form 2ip+1

ZHANG Dalei,CHEN Lei

Two special cases of the primes of the form 2ip+1 were discussed.First,we proved that 3 is a primitive root modulo Fermat primes except 3.Then,it was proved that for safe primes of the form 8k+7,-2 is their primitive roots.At last,we proved that for primes of theform q=8p+1,when,q≠41,3 is a primitive root modulo q.

Fermat primes;safe primes;primitive roots;quadratic residue

O156.2

A

1009-9530（2017）05-0092-02

2017-04-22

安徽高校自然科學(xué)研究重點(diǎn)項(xiàng)目“關(guān)聯(lián)數(shù)據(jù)的訪問控制機(jī)制研究”（KJ2016A664）

張大雷(1980-)，男，淮南師范學(xué)院計(jì)算機(jī)學(xué)院講師，碩士，研究方向?yàn)榫W(wǎng)絡(luò)與信息安全。

（責(zé)任編輯：孫妍姑）