2ip+1型素數及其原根

張大雷，陳磊

（淮南師范學院計算機學院，安徽淮南232038）

2ip+1型素數及其原根

張大雷，陳磊

（淮南師范學院計算機學院，安徽淮南232038）

費馬素數作為2ip+1型素數的特例，首先證明了3是除3以外的費馬素數的原根，接著研究了2ip+1型素數的另外一種特例，證明了-2是安全素數Q7的原根；并進一步證明對于q=8p+1型素數，當q≠41時，3是模q的原根。

費馬素數；安全素數；原根；二次剩余

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

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

本文中沿用文獻[12]同⑩。對符號的約定：P表示奇素數集合。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)}。……