陳 川,宓 玲

1.齊魯工業(yè)大學(xué)(山東省科學(xué)院) 山東省計(jì)算中心(國(guó)家超級(jí)計(jì)算濟(jì)南中心) 算力互聯(lián)網(wǎng)與信息安全教育部重點(diǎn)實(shí)驗(yàn)室,山東 濟(jì)南 250353; 2.山東省計(jì)算機(jī)網(wǎng)絡(luò)重點(diǎn)實(shí)驗(yàn)室 山東省基礎(chǔ)科學(xué)研究中心(計(jì)算機(jī)科學(xué)),山東 濟(jì)南 250014; 3.齊魯工業(yè)大學(xué)(山東省科學(xué)院) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,山東 濟(jì)南 250353

許多密碼算法都建立在大素?cái)?shù)的基礎(chǔ)上,比如RSA公鑰密碼算法、ElGamal公鑰密碼算法、Rabin公鑰密碼算法、Diffie-Hellman密鑰交換協(xié)議、Shamir門限密鑰共享方案等[1]。特別地,在RSA、ElGamal和Rabin等公鑰密碼算法中,大素?cái)?shù)或者是公鑰的一部分,或者可用于生成公鑰,每個(gè)用戶擁有的大素?cái)?shù)應(yīng)各不相同,還需要定期更換。因此,密碼學(xué)中對(duì)素?cái)?shù)的需求量是非常大的?？紤]到密碼學(xué)的應(yīng)用范圍越來(lái)越廣泛,因此有必要對(duì)素?cái)?shù)個(gè)數(shù)和素?cái)?shù)分布進(jìn)行深入研究。

已知素?cái)?shù)有無(wú)窮多個(gè)。若使用反證法,不難證明這個(gè)結(jié)論。另一方面,素?cái)?shù)有非常多的分類方式。比如說(shuō),素?cái)?shù)可以分為3種類型:2,形如4k+1的素?cái)?shù)(5、13、17等),形如4k-1的素?cái)?shù)(3、7、11等),其中k∈Z+。那么,形如4k-1和4k+1的素?cái)?shù)是否分別有無(wú)窮多個(gè)?對(duì)該問(wèn)題的研究具有現(xiàn)實(shí)意義:在Rabin公鑰密碼算法中,為保證順利解密,只能使用形如4k-1的素?cái)?shù);在RSA公鑰密碼算法中,所使用的大素?cái)?shù)一般都應(yīng)是安全素?cái)?shù),大的安全素?cái)?shù)也屬于形如4k-1的素?cái)?shù)。再比如說(shuō),素?cái)?shù)還可以分為4種類型:2,3,形如6k+1的素?cái)?shù)(7、17、19等),形如6k-1的素?cái)?shù)(5、11、17等),其中k∈Z+。那么,形如6k-1和6k+1的素?cái)?shù)是否分別有無(wú)窮多個(gè)?

“形如4k-1的素?cái)?shù)有無(wú)窮多個(gè)”,該結(jié)論曾作為例題出現(xiàn)在教材中[2],然而例題的證明邏輯性不強(qiáng),說(shuō)服力不夠?！靶稳?k+1的素?cái)?shù)有無(wú)窮多個(gè)”和“形如6k-1的素?cái)?shù)有無(wú)窮多個(gè)”,這兩個(gè)結(jié)論曾作為課后習(xí)題出現(xiàn)在教材中[2-4],截至目前,筆者尚未見(jiàn)到這兩個(gè)結(jié)論的證明。“形如6k+1的素?cái)?shù)有無(wú)窮多個(gè)”,該結(jié)論的證明難度要更大一些,在證明該結(jié)論之前,本文先給出了一個(gè)有用的引理。

1 預(yù)備知識(shí)

定義1[5]已知p為素?cái)?shù),若(a,p)=1且同余式x2≡a(modp)有解,則稱a為模p的平方剩余,否則稱a為模p的平方非剩余。

定義2[5]設(shè)m>1是整數(shù),a為正整數(shù)且(a,m)=1,則使得ax≡1(modm)成立的最小正整數(shù)x叫做a模m的階,記為ordm(a)。

引理1(Euler判定法則)[5]設(shè)p是奇素?cái)?shù),(a,p)=1,則

引理2[5]設(shè)m>1是整數(shù),a為整數(shù)且(a,m)=1,若整數(shù)d使得ad≡1(modm),則有ordm(a)|d。

引理3(Euler定理)[5]設(shè)m>1是整數(shù),a為整數(shù)且(a,m)=1,則aφ(m)≡1(modm),其中φ(m)表示m的Euler函數(shù)。

2 主要結(jié)果

定理1 形如4k-1(k∈Z+)的素?cái)?shù)有無(wú)窮多個(gè)。

證明：(反證法)假設(shè)形如4k-1的素?cái)?shù)僅有有限多個(gè),不妨設(shè)有n個(gè),分別為:p1,p2,…,pn,其中n為某個(gè)正整數(shù)。

構(gòu)造一個(gè)新的整數(shù):M=4p1p2…pn-1。

首先證明M不是素?cái)?shù)。已知素?cái)?shù)僅有3種類型:2,形如4k+1的素?cái)?shù),形如4k-1的素?cái)?shù),其中k∈Z+。(1)由于M是一個(gè)外在形式如4k-1的數(shù),所以它不可能是2、形如4k+1的素?cái)?shù)。(2)根據(jù)假設(shè),形如4k-1的素?cái)?shù)僅有p1,p2,…,pn,且M?{p1,p2,…,pn},所以M也不可能是個(gè)形如4k-1的素?cái)?shù)。綜上,M不是素?cái)?shù),它是合數(shù)。

M既然是合數(shù),它肯定存在素因子。M的素因子只可能屬于3種類型:2,形如4k+1的素?cái)?shù),形如4k-1的素?cái)?shù),其中k∈Z+。顯然,2M。另一方面,已假設(shè)形如4k-1的素?cái)?shù)僅有p1,p2,…,pn,且易知p1M,p2M,…,pnM。由此可得,合數(shù)M的所有素因子不包括2,也不包括形如4k-1的素?cái)?shù),即M的所有素因子都是形如4k+1的素?cái)?shù)。因此,M所有素因子的乘積與1模4同余。然而,M是與-1模4同余。矛盾。

所以,形如4k-1的素?cái)?shù)有無(wú)窮多個(gè)。

引理4已知素?cái)?shù)p>2,若-1是模p的平方剩余,則p≡1(mod 4)。

定理2形如4k+1(k∈Z+)的素?cái)?shù)有無(wú)窮多個(gè)。

證明：(反證法)假設(shè)形如4k+1的素?cái)?shù)僅有有限多個(gè),不妨設(shè)有n個(gè),分別為:p1,p2,…,pn,其中n為某個(gè)正整數(shù)。

構(gòu)造一個(gè)新的整數(shù):M=4(p1p2…pn)2+1。

首先證明M不是素?cái)?shù)。已知素?cái)?shù)僅有3種類型:2,形如4k+1的素?cái)?shù),形如4k-1的素?cái)?shù),其中k∈Z+。(1)由于M是一個(gè)外在形式如4k+1的數(shù),所以它不可能是2、形如4k-1的素?cái)?shù)。(2)根據(jù)假設(shè),形如4k+1的素?cái)?shù)僅有p1,p2,…,pn,且M?{p1,p2,…,pn},所以M也不可能是個(gè)形如4k+1的素?cái)?shù)。綜上,M不是素?cái)?shù),它是合數(shù)。

M既然是合數(shù),它肯定存在素因子。由于2M,可知M肯定存在大于2的素因子。

設(shè)q>2是M的一個(gè)素因子,則有M≡4(p1p2…pn)2+1≡0(modq),可得(2p1p2…pn)2≡-1(modq)。所以存在x≡2p1p2…pn(modq)且x∈{1,2,…,q-1},使得x2≡-1(modq),即-1是模q的平方剩余。由引理4可知,q≡1(mod 4)。這意味著M存在形如4k+1的素因子q。然而根據(jù)假設(shè),形如4k+1的素?cái)?shù)僅有p1,p2,…,pn,且易知p1M,p2M,…,pnM。矛盾。

所以,形如4k+1的素?cái)?shù)有無(wú)窮多個(gè)。

定理3形如6k-1(k∈Z+)的素?cái)?shù)有無(wú)窮多個(gè)。

證明：(反證法)假設(shè)形如6k-1的素?cái)?shù)僅有有限多個(gè),不妨設(shè)有n個(gè),分別為:p1,p2,…,pn,其中n為某個(gè)正整數(shù)。

構(gòu)造一個(gè)新的整數(shù):M=(p1p2…pn)2-2。

首先證明M不是素?cái)?shù)。已知素?cái)?shù)包括4種類型:2,3,形如6k+1的素?cái)?shù),形如6k-1的素?cái)?shù),其中k∈Z+。(1)由于M是一個(gè)外在形式如6k-1的數(shù),所以它不可能是2、3、形如6k+1的素?cái)?shù)。(2)根據(jù)假設(shè),形如6k-1的素?cái)?shù)僅有p1,p2,…,pn,且M?{p1,p2,…,pn},所以M也不可能是個(gè)形如6k-1的素?cái)?shù)。綜上可知,M不是素?cái)?shù),它是合數(shù)。

M既然是合數(shù),它肯定存在素因子。由于M是一個(gè)外在形式如6k-1的數(shù),因此2M且3M,可知M肯定存在大于3的素因子。設(shè)q>3是M的一個(gè)素因子,則q是形如6k+1或6k-1的素?cái)?shù)。所以,M的素因子或者形如6k+1,或者形如6k-1。

接下來(lái)證明:M的素因子不可能全都形如6k+1。若M的素因子全都形如6k+1,則M所有素因子的乘積與1模6同余,而M是與-1模6同余,矛盾。

綜上可得,M至少存在一個(gè)形如6k-1的素因子。然而根據(jù)假設(shè),形如6k-1的素?cái)?shù)僅有p1,p2,…,pn,且易知p1M,p2M,…,pnM。矛盾。

所以,形如6k-1的素?cái)?shù)有無(wú)窮多個(gè)。

引理5設(shè)素?cái)?shù)p>3是x2-x+1(x∈Z)的因子,則p≡1(mod 6)。

證明：首先證明(x,p)=1。若(x,p)≠1,則p|x,因此x≡0(modp),所以x2-x+1≡0-0+1≡1(modp)。然而,根據(jù)已知條件x2-x+1≡0(modp)。矛盾。

(1)證明ordp(x)≠1。若ordp(x)=1,則x1≡1(modp),所以x2-x+1≡1-1+1≡1(modp)。然而,根據(jù)已知條件x2-x+1≡0(modp)。矛盾。

(2)證明ordp(x)≠2。若ordp(x)=2,則x1?1(modp)且x2≡1(modp)。由x2≡1(modp)可知,x≡±1(modp),又因x?1(modp),可得x≡-1(modp),因此x2-x+1≡1+1+1≡3(modp)。然而,根據(jù)已知條件x2-x+1≡0(modp)。矛盾。

綜上可知,ordp(x)=6。

因?yàn)?x,p)=1,由引理3可知xφ(p)≡xp-1≡1(modp)。根據(jù)引理2,ordp(x)|p-1,即6|p-1。因此,p≡1(mod 6)。

定理4形如6k+1(k∈Z+)的素?cái)?shù)有無(wú)窮多個(gè)。

證明：(反證法)假設(shè)形如6k+1的素?cái)?shù)僅有有限多個(gè),不妨設(shè)有n個(gè),分別為:p1,p2,…,pn,其中n為某個(gè)正整數(shù)。

由p1≡1(mod 6),p2≡1(mod 6),…,pn≡1(mod 6)可知,p1p2…pn≡1(mod 6),所以M≡1-1+1≡1(mod 6)。

首先證明M不是素?cái)?shù)。已知素?cái)?shù)包括4種類型:2,3,形如6k+1的素?cái)?shù),形如6k-1的素?cái)?shù),其中k∈Z+。(1)由于M是一個(gè)外在形式如6k+1的數(shù),所以它不可能是2、3、形如6k-1的素?cái)?shù)。(2)根據(jù)假設(shè),形如6k+1的素?cái)?shù)僅有p1,p2,…,pn,且M?{p1,p2,…,pn},所以M也不可能是個(gè)形如6k+1的素?cái)?shù)。綜上可知,M不是素?cái)?shù),它是合數(shù)。

M既然是合數(shù),它肯定存在素因子。由于M是一個(gè)外在形式如6k+1的數(shù),因此2M且3M,可知M肯定存在大于3的素因子。設(shè)q>3是M的一個(gè)素因子。根據(jù)引理5,q≡1(mod 6),即M存在一個(gè)形如6k+1的素因子q。然而根據(jù)假設(shè),形如6k+1的素?cái)?shù)僅有p1,p2,…,pn,且易知p1M,p2M,…,pnM。矛盾。

所以,形如6k+1的素?cái)?shù)有無(wú)窮多個(gè)。