快速檢驗(yàn)梅森素?cái)?shù)的一種新方法

林柏鋼

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

快速檢驗(yàn)梅森素?cái)?shù)的一種新方法

林柏鋼1,2

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

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

準(zhǔn)偶完全數(shù)序列； 通項(xiàng)公式； 梅森素?cái)?shù)； 快速檢驗(yàn)算法

0 引言

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

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

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

定義1 幾個(gè)符號(hào)約定：Mp表示由正整數(shù)p所形成的梅森素?cái)?shù)，記為Mp=2p-1；Ep表示由正整數(shù)p所形成的偶完全數(shù)，記為EP=2p-1·(2p-1)；φEp表示偶完全數(shù)的因子分解總項(xiàng)數(shù);KEp表示分解因子成鏡像對(duì)稱兩兩相乘等于自身偶完全數(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*，… . 其中帶星號(hào)的整數(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)為素?cái)?shù)，則2p-1.(2p-1)為偶完全數(shù). 同理，根據(jù)梅森素?cái)?shù)定義，也只有當(dāng)(2p-1)為素?cái)?shù)時(shí)才稱為梅森素?cái)?shù). 由Ep的相關(guān)性質(zhì)特點(diǎn)，我們知道: ① 偶完全數(shù)的構(gòu)造滿足公式EP=2p-1·(2p-1)； ② 偶完全數(shù)的表達(dá)結(jié)果具有2p-1～22p-2范圍的連續(xù)方冪之和； ③ 偶完全數(shù)的展開(kāi)表達(dá)式呈三角形排列，等等.

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

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

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

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

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

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時(shí)，而準(zhǔn)偶完全數(shù)序列SPEPN具有22n-2～24(n-1)范圍的連續(xù)方冪之和. 除偶完全數(shù)6外，兩者方冪個(gè)數(shù)均為奇數(shù).

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

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

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

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

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

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

令p=2n-1時(shí)，則有：

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

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

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

另證KEp，因?yàn)榉纸庖蜃邮醉?xiàng)恒為1，其余分解因子成鏡像對(duì)稱兩兩相乘等于自身偶完全數(shù)，故有本數(shù)數(shù)目KEp=[(4n-3)-1]/2=2(n-1).

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

證明 根據(jù)定理4和偶完全數(shù)分解特點(diǎn)可知，除首項(xiàng)Ep(1)=1外，其余各項(xiàng)因子成鏡像對(duì)稱兩兩相乘等于給定偶完全數(shù)本數(shù). 因此有(4n-3)-1=4(n-1)個(gè)因子構(gòu)成兩兩相乘等于給定偶完全數(shù)本數(shù)，且KEp=2(n-1). 在所有這樣本數(shù)鏡像相乘組合對(duì)存在中，唯有中間左右兩項(xiàng)展開(kāi)式因子能夠滿足鏡像相乘結(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時(shí)，則有下式成立：

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

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

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

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

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

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

npSpepn展開(kāi)形式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)????

由展開(kāi)式可知，對(duì)應(yīng)每個(gè)n，展開(kāi)式的左邊恒為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)梅森素?cái)?shù)序列，記為SMn，(其中除3外，帶*號(hào)數(shù)全為梅森素?cái)?shù)).

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

證明 由展開(kāi)式易證推論3成立.

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

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

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

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

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

2 梅森素?cái)?shù)的快速判定算法思路

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

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

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

算法2 根據(jù)準(zhǔn)梅森素?cái)?shù)序列SMn，檢驗(yàn)梅森素?cái)?shù)存在.

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

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

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

必須指出，對(duì)于p為素?cái)?shù)，但不是梅森素?cái)?shù)情形時(shí)，檢驗(yàn)是否為偶完全數(shù)Ep也很簡(jiǎn)便，只要找到一個(gè)因子不滿足偶完全數(shù)要求計(jì)算就停止. 這里不再贅述.

3 結(jié)語(yǔ)

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

[1] 蓋伊RK.數(shù)論中未解決的問(wèn)題[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] 周海中.梅森素?cái)?shù)的分布規(guī)律[J].中山大學(xué)學(xué)報(bào):自然科學(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)梅森素?cái)?shù)尋求(GIMPS)研究計(jì)劃進(jìn)展[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，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ò)與信息安全、編碼與密碼、云計(jì)算與物聯(lián)網(wǎng)安全、可信計(jì)算等研究，linbg@fzu.edu.cn

國(guó)家自然科學(xué)基金資助項(xiàng)目(61402112)

10.7631/issn.1000-2243.2015.05.0577

1000-2243(2015)05-0577-05

O156

A