林柏鋼

(1. 福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院，福建 福州 350116；2. 網(wǎng)絡(luò)系統(tǒng)信息安全福建省高校重點實驗室，福建 福州 350116)

快速檢驗梅森素數(shù)的一種新方法

林柏鋼1,2

(1. 福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院，福建 福州 350116；2. 網(wǎng)絡(luò)系統(tǒng)信息安全福建省高校重點實驗室，福建 福州 350116)

研究梅森素數(shù)與偶完全數(shù)的內(nèi)在聯(lián)系，分析偶完全數(shù)因子分解的結(jié)構(gòu)特點，分別得到一個準(zhǔn)偶完全數(shù)序列的通項公式：Sn=22n-2·(22n-1-1)，和一個準(zhǔn)梅森素數(shù)序列的通項公式：SMn=(22n-1-1). 最后給出快速檢驗梅森素數(shù)新方法的算法思路.

準(zhǔn)偶完全數(shù)序列； 通項公式； 梅森素數(shù)； 快速檢驗算法

0 引言

公鑰密碼的特點之一就是與素數(shù)緊密相關(guān)，判定素數(shù)、大數(shù)分解以及尋找最大的素數(shù)，始終是人們關(guān)注的課題[1-2]. 在我們所知道的梅森素數(shù)尋找過程中，如果說至今為止已找到的第48個梅森素數(shù)(對應(yīng)確定的第48個偶完全數(shù))，那可是花了九牛二虎之力才取得的成果[3-4]. 也就是說，從尋找第35個梅森素數(shù)開始，靠的是現(xiàn)代互聯(lián)網(wǎng)技術(shù)才得以取得突破進展. 20世紀(jì)90年代中后期，在美國程序設(shè)計師沃特曼和庫爾沃斯基等人的共同努力下，成立了世界上第一個基于互聯(lián)網(wǎng)的分布式計算項目——因特網(wǎng)梅森素數(shù)大搜尋(GIMPS)計劃[5-6]. 人們只要在GIMPS的主頁上下載一個計算梅森素數(shù)的免費程序，就可以立即參加該項目來搜尋新的梅森素數(shù). 1996年11月13日，Joel Armengaud基于GIMPS平臺，找到了第35位梅森素數(shù)，對應(yīng)p=1 398 269，Mp= 814 717 564…451 315 711，素數(shù)有420 921位. 2013年1月25日，美國中央密蘇里大學(xué)柯蒂斯·庫珀(Curtis Cooper)教授的研究小組發(fā)現(xiàn)了最大的素數(shù)Mp=257 885 161-1=58 188 726 623 224 644 217…46 141 988 071 724 285 951，是第48個梅森素數(shù)，對應(yīng)p=57 885 161，該素數(shù)有17 425 170位. 由此可見尋找和發(fā)現(xiàn)更大梅森素數(shù)是多么的艱難.

盡管尋找梅森素數(shù)困難重重，但人們還是想盡各種辦法解決[7-8]，包括梅森素數(shù)和偶完全數(shù)的研究歷來備受人們關(guān)注，因為偶完全數(shù)的存在總是伴隨和依賴著梅森素數(shù)的發(fā)現(xiàn)而確定，兩者之間不是孿生兄弟關(guān)系，而是連體嬰兒關(guān)系. 只要發(fā)現(xiàn)一個新梅森素數(shù)，偶完全數(shù)就是它的副產(chǎn)品. 本文從研究偶完全數(shù)的分布特征入手，研究偶完全數(shù)的因子展開存在規(guī)律，進而確定對應(yīng)的梅森素數(shù)的存在，并給出梅森素數(shù)的定位內(nèi)在聯(lián)系，最后給出判定梅森素數(shù)的新方法.

1 梅森素數(shù)與偶完全數(shù)的內(nèi)在聯(lián)系

定義1 幾個符號約定：Mp表示由正整數(shù)p所形成的梅森素數(shù)，記為Mp=2p-1；Ep表示由正整數(shù)p所形成的偶完全數(shù)，記為EP=2p-1·(2p-1)；φEp表示偶完全數(shù)的因子分解總項數(shù);KEp表示分解因子成鏡像對稱兩兩相乘等于自身偶完全數(shù)的本數(shù)數(shù)目.

定義2 稱準(zhǔn)偶完全數(shù)序列(sequenceofpseudo-evenperfectnumber,SPEPN)是指除偶完全數(shù)6外，序列形如： 1,28*,496*,8 128*,130 816,2 096 128,33 550 336*,536 854 528,8 589 869 056*,137 438 691 328*，… . 其中帶星號的整數(shù)為大于6的偶完全數(shù).

定義3 稱偶完全數(shù)序列(sequenceofevenperfectnumber,SEPN)是指包含偶完全數(shù)6在內(nèi)的可能存在都是偶完全數(shù)的序列. 即： 6*，28*,496*,8 128*,33 550 336*,8 589 869 056*,137 438 691 328*，….

根據(jù)偶完全數(shù)的定義： 若p與(2p-1)為素數(shù)，則2p-1.(2p-1)為偶完全數(shù). 同理，根據(jù)梅森素數(shù)定義，也只有當(dāng)(2p-1)為素數(shù)時才稱為梅森素數(shù). 由Ep的相關(guān)性質(zhì)特點，我們知道: ① 偶完全數(shù)的構(gòu)造滿足公式EP=2p-1·(2p-1)； ② 偶完全數(shù)的表達結(jié)果具有2p-1～22p-2范圍的連續(xù)方冪之和； ③ 偶完全數(shù)的展開表達式呈三角形排列，等等.

由偶完全數(shù)性質(zhì)不難得到：

定理1 準(zhǔn)偶完全數(shù)序列的通項公式為：

Spepn=22n-2·(22n-1-1) (n≥1)

證明 根據(jù)偶完全數(shù)的性質(zhì)②，準(zhǔn)偶完全數(shù)序列的每個數(shù)也可以按一定范圍的連續(xù)方冪之和展開排列，具體如下(其中n≥1為順序號)：

根據(jù)上述展開表達式，不失一般性可以給出基本表達式：

an=22n-2+2(2n-2)+1+2(2n-2)+2+…+2(2n-2)+(2n-4)+2(2n-2)+(2n-3)+2(2n-2)+(2n-2)

定理2 除偶完全數(shù)6外，偶完全數(shù)的序列SEPN是準(zhǔn)偶完全數(shù)序列SPEPN的特列.

證明 由偶完全數(shù)的構(gòu)造公式： (2p-1)·(2p-1)可知： 令p=2n-1，則有

根據(jù)偶完全數(shù)性質(zhì)②可知，偶完全數(shù)具有2p-1～22p-2范圍的連續(xù)方冪之和. 考慮p?2n-1,當(dāng)p=2n-1時，而準(zhǔn)偶完全數(shù)序列SPEPN具有22n-2～24(n-1)范圍的連續(xù)方冪之和. 除偶完全數(shù)6外，兩者方冪個數(shù)均為奇數(shù).

又因為連續(xù)方冪之和： 2p-1～22p-2? 22n-2～24(n-1)，所以定理2得證.

推論1 任一偶完全數(shù)Ep一定存在準(zhǔn)偶完全數(shù)序列SPEPN中.

證明 由定理2易得本推論成立.

定理3 偶完全數(shù)的因子分解項排列結(jié)構(gòu)為： 首項k0=20=1，k1項之后各因子按2n規(guī)律升冪展開，典型中項因子(包括左右兩項)分別為：kml=22(n-1)，kmr=(2(2n-1)-1)； 之后各因子按對稱鏡像映射遞減2n規(guī)律分布，尾項kend=24(n-1)-22n-3.

證明 根據(jù)偶完全數(shù)的因子展開分布，其各因子排列結(jié)構(gòu)形式如下(其中p為素數(shù))：

由偶完全數(shù)的因子展開式知道，它的一般表達式為：

令p=2n-1時，則有：

展開結(jié)果就有首項k0=20=1，前半部分大括弧中k1項之后按2n規(guī)律展開，中括弧中典型中項(包括左右兩項)分別為：kml=22(n-1)，kmr=(2(2n-1)-1)； 后半部分大括弧中各因子則按對稱鏡像映射遞減2n規(guī)律分布，結(jié)果就有尾項kend=24n-4-22n-3=24(n-1)-22n-3.

定理4 偶完全數(shù)的因子分解項恒為奇數(shù)，總項數(shù)φEp=4n-3； 滿足偶完全數(shù)自身數(shù)項目數(shù)為KEp=2(n-1).

證明 因為偶完全數(shù)的因子分解特點是首項必為20=1，其余分解因子成鏡像對稱兩兩相乘等于各偶完全數(shù)，結(jié)果必為偶數(shù)，加上首項總項數(shù)恒為奇數(shù). 另由偶完全數(shù)的因子展開式可以看出，n=1，φEp(1)=1；n=2，φEp(28)=5；n=3，φEp(496)=9； …； 以此類推，當(dāng)n≥1時，每個偶完全數(shù)的因子分解總項數(shù)恒為φEp=4n-3.

另證KEp，因為分解因子首項恒為1，其余分解因子成鏡像對稱兩兩相乘等于自身偶完全數(shù)，故有本數(shù)數(shù)目KEp=[(4n-3)-1]/2=2(n-1).

定理5 在偶完全數(shù)的因子分解總項數(shù)中，第2n項位置一定是梅森素數(shù)： (2p-1).

證明 根據(jù)定理4和偶完全數(shù)分解特點可知，除首項Ep(1)=1外，其余各項因子成鏡像對稱兩兩相乘等于給定偶完全數(shù)本數(shù). 因此有(4n-3)-1=4(n-1)個因子構(gòu)成兩兩相乘等于給定偶完全數(shù)本數(shù)，且KEp=2(n-1). 在所有這樣本數(shù)鏡像相乘組合對存在中，唯有中間左右兩項展開式因子能夠滿足鏡像相乘結(jié)果，符合2p-1×(2p-1)=Ep條件，即：

{Ep(2n-1)=22(n-1),Ep(2n)=22n-1-1} ? {(22(n-1)×(22n-1-1))=Ep}

當(dāng)p=2n-1時，則有下式成立：

{Ep(2n-1)=2p-1,Ep(2n)=2p-1}? {(2p-1×(2p-1))=Ep}

其余各項鏡像相乘結(jié)果雖然也滿足偶完全數(shù)的本數(shù)存在，但不符合偶完全數(shù)條件. 另根據(jù)偶完全數(shù)定義，若Ep為偶完全數(shù)，則p與(2p-1 )必定為素數(shù). 反之，若p為素數(shù)，(2p-1)為非素數(shù)，則偶完全數(shù)不成立. 又因為Ep中的(2p-1)項加上首項，剛好落在分解展開式(2n-1)+1=2n項位置，故可確定第2n項位置一定是梅森素數(shù)： (2p-1).

推論2 任一梅森素數(shù)也一定存在準(zhǔn)偶完全數(shù)序列SPEPN中.

證明 由偶完全數(shù)和梅森素數(shù)的關(guān)系，以及定理5易證本推論成立.

引理1 當(dāng)n≥1時，序列：bn=20+21+22+23+…+22n-3+22n-2的前(2n-1)項和為：

證明 根據(jù)準(zhǔn)偶完全數(shù)特點，還可將其各因子展開如下形式排列(其中p為素數(shù)，*表示偶完全數(shù))：

npSpepn展開形式1?120·(20)2328*22·(20+21+22)35496*24·(20+21+22+23+24)478128*26·(20+21+22+23+24+25+26)5?13081628·(20+21+22+23+24+25+26+27+28)????

由展開式可知，對應(yīng)每個n，展開式的左邊恒為22n-2，右邊括弧中的序列形式為：

bn=20+21+22+23+…+22n-3+22n-2

定義4 形如： 1,7*,31*,127*,511，2 047，8 191*，32 767，131 071*，524 287*，2 097 151，8 388 607，33 554 431，134 217 727，536 870 911，2 147 483 647*，…，稱為準(zhǔn)梅森素數(shù)序列，記為SMn，(其中除3外，帶*號數(shù)全為梅森素數(shù)).

證明 當(dāng)n≥1時，序列Mn中的每個數(shù)展開形式均為： 20+21+22+23+…+22n-3+22n-2

證明 由展開式易證推論3成立.

定理9 (ⅰ)若(22n-1-1)為已知數(shù)，則(2n-1)=log2(22n-1)；

(ⅱ)若2n-1=p，則有p=log2(22n-1).

證明 (ⅰ)已知(22n-1-1)數(shù)值給定，根據(jù)對數(shù)公式，則有下式成立：

(2n-1)=log2[(22n-1-1)+1]=log2(22n-1)

(ⅱ)同理，若令2n-1=p，由(ⅰ)可證(ⅱ)成立.

2 梅森素數(shù)的快速判定算法思路

算法1 根據(jù)準(zhǔn)偶完全數(shù)序列SPEPN，檢驗梅森素數(shù).

1) 從準(zhǔn)偶完全數(shù)序列SPEPN中確定偶完全數(shù)Ep；

2) 由偶完全數(shù)Ep的展開形式，判定梅森素數(shù)存在.

算法2 根據(jù)準(zhǔn)梅森素數(shù)序列SMn，檢驗梅森素數(shù)存在.

算例分析 根據(jù)算法1檢驗梅森素數(shù)存在. 由準(zhǔn)偶完全數(shù)序列SPEPN中檢驗n=10時，Spepn=137 438 691 328的數(shù)確信是梅森素數(shù)的結(jié)果.

1) 從準(zhǔn)偶完全數(shù)序列SPEPN中確定偶完全數(shù)Ep.根據(jù)定理3分解規(guī)則，從第1項開始到2n-1項之前，按2n升冪展開(簡單算法就是： 從第2項開始，2×前項到(2n-1)項為止)，2n項之后到結(jié)束項kend=24(n-1)-22n-3為止，偶完全數(shù)Ep對應(yīng)分解各項按對稱映射遞減2n規(guī)律展開(簡單算法就是： 從(2n+1)項開始，2×前項到結(jié)束項(kend=24(n-1)-22n-3)為止). 檢驗判定若Ep確定為偶完全數(shù)，最后可得到n=10時，偶完全數(shù)Ep=137 438 691 328的展開形式為：

2) 由偶完全數(shù)Ep的展開式，判定梅森素數(shù)存在. 根據(jù)定理5，處于展開式中第2n=20項位置一定是梅森素數(shù)：Mp=2p-1= 524 287. 另據(jù)定理9(ⅱ)，其對應(yīng)素數(shù)p=log2(22n-1)=log2(22×10-1)=19.

必須指出，對于p為素數(shù)，但不是梅森素數(shù)情形時，檢驗是否為偶完全數(shù)Ep也很簡便，只要找到一個因子不滿足偶完全數(shù)要求計算就停止. 這里不再贅述.

3 結(jié)語

在網(wǎng)絡(luò)安全日益突出的今天，在GIMPS計劃平臺上尋找更大的梅森素數(shù)，不僅反映計算機網(wǎng)絡(luò)硬件的數(shù)據(jù)處理能力，同時也是綜合各種計算方法的準(zhǔn)確運用和水平的真實體現(xiàn)，它對基礎(chǔ)數(shù)論研究，對計算機學(xué)科發(fā)展，尤其對密碼學(xué)領(lǐng)域的大數(shù)分解和安全素數(shù)聯(lián)系緊密的應(yīng)用方面有著極其深刻的影響. 本文通過分析梅森素數(shù)和偶完全數(shù)的相關(guān)內(nèi)在聯(lián)系，從中找出偶完全數(shù)的基本展開規(guī)律，給出了準(zhǔn)偶完全數(shù)序列SPEPN的通項公式和準(zhǔn)梅森素數(shù)序列SMn的公式，最后給出快速檢驗梅森素數(shù)新方法的算法思路，無疑對快速尋找更大的梅森素數(shù)是一個新的研究途徑.

[1] 蓋伊RK.數(shù)論中未解決的問題[M].2版.張明堯，譯.北京： 科學(xué)出版社，2003: 12-17.

[2]CrandallR，PomeranceC.Primenumbers:acomputationalperspective[M]. 2nded.NewYork：Springer，2005.

[3]Knowprimes:listofknownMersenneprimenumbers[EB/OL]. [2015-07-08].http://www.mersenne.org/primes/greatInternetMersenneprimesearchGIMPS/current progress/

[4] 周海中.梅森素數(shù)的分布規(guī)律[J].中山大學(xué)學(xué)報:自然科學(xué)版，1992，31(4)，121-122.

[5] Website. PrimeNet CPU benchmarks (GIMPS)[EB/OL]. (2014-01-01)[2015-07-08].http://www.mersenne.org/report_benchmarks/get started/CPU benchmarks.

[6] 高全泉.大互聯(lián)網(wǎng)梅森素數(shù)尋求(GIMPS)研究計劃進展[J]. 數(shù)學(xué)的實踐與認(rèn)識，2006，36 (1)： 232 -238.

[7] Thall A. Fast Mersenne prime testing on the GPU[EB/OL]. (2011-05)[2015-07].http:// www.researchgate.net/

[8] 張四保.關(guān)于完全數(shù)的研究[D].成都： 成都理工大學(xué)，2008.

(責(zé)任編輯： 鄭美鶯)

A new method of quick test Mersenne prime

LIN Bogang1,2

(1. College of Mathematics and Computer Science,Fuzhou University,Fuzhou,Fujian 350116,China;2. Key Lab of Information Security of Network System in Fujian Province,Fuzhou,Fujian 350116,China)

The relation about Mersenne prime and even perfect number is researched,the structure feature of factorization for even perfect number is analysis. The study obtain two important result: a general formula of sequence of pseudo-even perfect number (SPEPN) isSn=22n-2·(22n-1-1),another general formula of sequence of pseudo-Mersenne prime (SPMP )isSMn=(22n-1-1). And a new method of quick test Mersenne prime is given.

sequence of pseudo-even perfect number; general formula; Mersenne prime; quick testing method

2015-08-20

林柏鋼(1953-)，教授，博導(dǎo)，主要從事網(wǎng)絡(luò)與信息安全、編碼與密碼、云計算與物聯(lián)網(wǎng)安全、可信計算等研究，linbg@fzu.edu.cn

國家自然科學(xué)基金資助項目(61402112)

10.7631/issn.1000-2243.2015.05.0577

1000-2243(2015)05-0577-05

O156

A