快速检验梅森素数的一种新方法

林柏钢

(1. 福州大学数学与计算机科学学院，福建 福州 350116；2. 网络系统信息安全福建省高校重点实验室，福建 福州 350116)

快速检验梅森素数的一种新方法

林柏钢1,2

(1. 福州大学数学与计算机科学学院，福建 福州 350116；2. 网络系统信息安全福建省高校重点实验室，福建 福州 350116)

研究梅森素数与偶完全数的内在联系，分析偶完全数因子分解的结构特点，分别得到一个准偶完全数序列的通项公式：Sn=22n-2·(22n-1-1)，和一个准梅森素数序列的通项公式：SMn=(22n-1-1). 最后给出快速检验梅森素数新方法的算法思路.

准偶完全数序列； 通项公式； 梅森素数； 快速检验算法

0 引言

公钥密码的特点之一就是与素数紧密相关，判定素数、大数分解以及寻找最大的素数，始终是人们关注的课题[1-2]. 在我们所知道的梅森素数寻找过程中，如果说至今为止已找到的第48个梅森素数(对应确定的第48个偶完全数)，那可是花了九牛二虎之力才取得的成果[3-4]. 也就是说，从寻找第35个梅森素数开始，靠的是现代互联网技术才得以取得突破进展. 20世纪90年代中后期，在美国程序设计师沃特曼和库尔沃斯基等人的共同努力下，成立了世界上第一个基于互联网的分布式计算项目——因特网梅森素数大搜寻(GIMPS)计划[5-6]. 人们只要在GIMPS的主页上下载一个计算梅森素数的免费程序，就可以立即参加该项目来搜寻新的梅森素数. 1996年11月13日，Joel Armengaud基于GIMPS平台，找到了第35位梅森素数，对应p=1 398 269，Mp= 814 717 564…451 315 711，素数有420 921位. 2013年1月25日，美国中央密苏里大学柯蒂斯·库珀(Curtis Cooper)教授的研究小组发现了最大的素数Mp=257 885 161-1=58 188 726 623 224 644 217…46 141 988 071 724 285 951，是第48个梅森素数，对应p=57 885 161，该素数有17 425 170位. 由此可见寻找和发现更大梅森素数是多么的艰难.

尽管寻找梅森素数困难重重，但人们还是想尽各种办法解决[7-8]，包括梅森素数和偶完全数的研究历来备受人们关注，因为偶完全数的存在总是伴随和依赖着梅森素数的发现而确定，两者之间不是孪生兄弟关系，而是连体婴儿关系. 只要发现一个新梅森素数，偶完全数就是它的副产品. 本文从研究偶完全数的分布特征入手，研究偶完全数的因子展开存在规律，进而确定对应的梅森素数的存在，并给出梅森素数的定位内在联系，最后给出判定梅森素数的新方法.

1 梅森素数与偶完全数的内在联系

定义1 几个符号约定：Mp表示由正整数p所形成的梅森素数，记为Mp=2p-1；Ep表示由正整数p所形成的偶完全数，记为EP=2p-1·(2p-1)；φEp表示偶完全数的因子分解总项数;KEp表示分解因子成镜像对称两两相乘等于自身偶完全数的本数数目.

定义2 称准偶完全数序列(sequenceofpseudo-evenperfectnumber,SPEPN)是指除偶完全数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*，… . 其中带星号的整数为大于6的偶完全数.

定义3 称偶完全数序列(sequenceofevenperfectnumber,SEPN)是指包含偶完全数6在内的可能存在都是偶完全数的序列. 即： 6*，28*,496*,8 128*,33 550 336*,8 589 869 056*,137 438 691 328*，….

根据偶完全数的定义： 若p与(2p-1)为素数，则2p-1.(2p-1)为偶完全数. 同理，根据梅森素数定义，也只有当(2p-1)为素数时才称为梅森素数. 由Ep的相关性质特点，我们知道: ① 偶完全数的构造满足公式EP=2p-1·(2p-1)； ② 偶完全数的表达结果具有2p-1～22p-2范围的连续方幂之和； ③ 偶完全数的展开表达式呈三角形排列，等等.

由偶完全数性质不难得到：

定理1 准偶完全数序列的通项公式为：

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

证明 根据偶完全数的性质②，准偶完全数序列的每个数也可以按一定范围的连续方幂之和展开排列，具体如下(其中n≥1为顺序号)：

根据上述展开表达式，不失一般性可以给出基本表达式：

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 除偶完全数6外，偶完全数的序列SEPN是准偶完全数序列SPEPN的特列.

证明 由偶完全数的构造公式： (2p-1)·(2p-1)可知： 令p=2n-1，则有

根据偶完全数性质②可知，偶完全数具有2p-1～22p-2范围的连续方幂之和. 考虑p⊆2n-1,当p=2n-1时，而准偶完全数序列SPEPN具有22n-2～24(n-1)范围的连续方幂之和. 除偶完全数6外，两者方幂个数均为奇数.

又因为连续方幂之和： 2p-1～22p-2⊆ 22n-2～24(n-1)，所以定理2得证.

推论1 任一偶完全数Ep一定存在准偶完全数序列SPEPN中.

证明 由定理2易得本推论成立.

定理3 偶完全数的因子分解项排列结构为： 首项k0=20=1，k1项之后各因子按2n规律升幂展开，典型中项因子(包括左右两项)分别为：kml=22(n-1)，kmr=(2(2n-1)-1)； 之后各因子按对称镜像映射递减2n规律分布，尾项kend=24(n-1)-22n-3.

证明 根据偶完全数的因子展开分布，其各因子排列结构形式如下(其中p为素数)：

由偶完全数的因子展开式知道，它的一般表达式为：

令p=2n-1时，则有：

展开结果就有首项k0=20=1，前半部分大括弧中k1项之后按2n规律展开，中括弧中典型中项(包括左右两项)分别为：kml=22(n-1)，kmr=(2(2n-1)-1)； 后半部分大括弧中各因子则按对称镜像映射递减2n规律分布，结果就有尾项kend=24n-4-22n-3=24(n-1)-22n-3.

定理4 偶完全数的因子分解项恒为奇数，总项数φEp=4n-3； 满足偶完全数自身数项目数为KEp=2(n-1).

证明 因为偶完全数的因子分解特点是首项必为20=1，其余分解因子成镜像对称两两相乘等于各偶完全数，结果必为偶数，加上首项总项数恒为奇数. 另由偶完全数的因子展开式可以看出，n=1，φEp(1)=1；n=2，φEp(28)=5；n=3，φEp(496)=9； …； 以此类推，当n≥1时，每个偶完全数的因子分解总项数恒为φEp=4n-3.

另证KEp，因为分解因子首项恒为1，其余分解因子成镜像对称两两相乘等于自身偶完全数，故有本数数目KEp=[(4n-3)-1]/2=2(n-1).

定理5 在偶完全数的因子分解总项数中，第2n项位置一定是梅森素数： (2p-1).

证明 根据定理4和偶完全数分解特点可知，除首项Ep(1)=1外，其余各项因子成镜像对称两两相乘等于给定偶完全数本数. 因此有(4n-3)-1=4(n-1)个因子构成两两相乘等于给定偶完全数本数，且KEp=2(n-1). 在所有这样本数镜像相乘组合对存在中，唯有中间左右两项展开式因子能够满足镜像相乘结果，符合2p-1×(2p-1)=Ep条件，即：

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

当p=2n-1时，则有下式成立：

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

其余各项镜像相乘结果虽然也满足偶完全数的本数存在，但不符合偶完全数条件. 另根据偶完全数定义，若Ep为偶完全数，则p与(2p-1 )必定为素数. 反之，若p为素数，(2p-1)为非素数，则偶完全数不成立. 又因为Ep中的(2p-1)项加上首项，刚好落在分解展开式(2n-1)+1=2n项位置，故可确定第2n项位置一定是梅森素数： (2p-1).

推论2 任一梅森素数也一定存在准偶完全数序列SPEPN中.

证明 由偶完全数和梅森素数的关系，以及定理5易证本推论成立.

引理1 当n≥1时，序列：bn=20+21+22+23+…+22n-3+22n-2的前(2n-1)项和为：

证明 根据准偶完全数特点，还可将其各因子展开如下形式排列(其中p为素数，*表示偶完全数)：

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)︙︙︙︙

由展开式可知，对应每个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*，…，称为准梅森素数序列，记为SMn，(其中除3外，带*号数全为梅森素数).

证明 当n≥1时，序列Mn中的每个数展开形式均为： 20+21+22+23+…+22n-3+22n-2

证明 由展开式易证推论3成立.

定理9 (ⅰ)若(22n-1-1)为已知数，则(2n-1)=log2(22n-1)；

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

证明 (ⅰ)已知(22n-1-1)数值给定，根据对数公式，则有下式成立：

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

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

2 梅森素数的快速判定算法思路

算法1 根据准偶完全数序列SPEPN，检验梅森素数.

1) 从准偶完全数序列SPEPN中确定偶完全数Ep；

2) 由偶完全数Ep的展开形式，判定梅森素数存在.

算法2 根据准梅森素数序列SMn，检验梅森素数存在.

算例分析 根据算法1检验梅森素数存在. 由准偶完全数序列SPEPN中检验n=10时，Spepn=137 438 691 328的数确信是梅森素数的结果.

1) 从准偶完全数序列SPEPN中确定偶完全数Ep.根据定理3分解规则，从第1项开始到2n-1项之前，按2n升幂展开(简单算法就是： 从第2项开始，2×前项到(2n-1)项为止)，2n项之后到结束项kend=24(n-1)-22n-3为止，偶完全数Ep对应分解各项按对称映射递减2n规律展开(简单算法就是： 从(2n+1)项开始，2×前项到结束项(kend=24(n-1)-22n-3)为止). 检验判定若Ep确定为偶完全数，最后可得到n=10时，偶完全数Ep=137 438 691 328的展开形式为：

2) 由偶完全数Ep的展开式，判定梅森素数存在. 根据定理5，处于展开式中第2n=20项位置一定是梅森素数：Mp=2p-1= 524 287. 另据定理9(ⅱ)，其对应素数p=log2(22n-1)=log2(22×10-1)=19.

必须指出，对于p为素数，但不是梅森素数情形时，检验是否为偶完全数Ep也很简便，只要找到一个因子不满足偶完全数要求计算就停止. 这里不再赘述.

3 结语

在网络安全日益突出的今天，在GIMPS计划平台上寻找更大的梅森素数，不仅反映计算机网络硬件的数据处理能力，同时也是综合各种计算方法的准确运用和水平的真实体现，它对基础数论研究，对计算机学科发展，尤其对密码学领域的大数分解和安全素数联系紧密的应用方面有着极其深刻的影响. 本文通过分析梅森素数和偶完全数的相关内在联系，从中找出偶完全数的基本展开规律，给出了准偶完全数序列SPEPN的通项公式和准梅森素数序列SMn的公式，最后给出快速检验梅森素数新方法的算法思路，无疑对快速寻找更大的梅森素数是一个新的研究途径.

[1] 盖伊RK.数论中未解决的问题[M].2版.张明尧，译.北京： 科学出版社，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] 周海中.梅森素数的分布规律[J].中山大学学报:自然科学版，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] 高全泉.大互联网梅森素数寻求(GIMPS)研究计划进展[J]. 数学的实践与认识，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] 张四保.关于完全数的研究[D].成都： 成都理工大学，2008.

(责任编辑： 郑美莺)

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-)，教授，博导，主要从事网络与信息安全、编码与密码、云计算与物联网安全、可信计算等研究，linbg@fzu.edu.cn

国家自然科学基金资助项目(61402112)

10.7631/issn.1000-2243.2015.05.0577

1000-2243(2015)05-0577-05

O156

A