梅森素数

mason_prime 古希腊数学家欧几里德就已证明素数有无穷多个,并提出一些素数可写成“2P-1”(其中指数 P 也是素数)的形式,其中 17 世纪法国数学家、法兰西科学院奠基人马林·梅森(Martin Mersenne)是其中成果较为卓著的一位,因此数学界将“2P-1”型的素数称为“梅森素数”。

1772 年,欧拉在双目失明的情况下,靠心算证明了 231-1(即 2147483647)是第 8 个梅森素数,这个记录一百多年内都没有人打破。下面是欧拉证明素数有无穷多个的过程,但是梅森素数是否有无穷多个还没有人能证明。

假使素数 p1,p2,p3……pn 只有那么多个,现在有新数 p=p1*p2*p3*……pn + 1,可见 p 无法被 p1,p2,p3……pn 任意一个整除,所以 p 是素数,那就和素数只有 n 个矛盾了,所以素数有无穷多个。

1996 年,乔治·沃特曼编制了一个梅森素数计算程序,后来发展成为 GIMPS(Great Internet Mersenne Prime Search,你可以从上面找到最新的第 48 个梅森素数发现的信息)项目,在超级计算机尝试之后,希望借助互联网和分布式计算的力量,寻找更大的梅森素数(现在已经有超过 180 个国家的近一百万台计算机参与计算)。

在寻找梅森素数的过程中,并不是漫无目的的。很容易证明,如果 2 P-1 是素数,则 P 也一定是素数(这样我们就首先可以列出一个“可疑梅森素数清单”,进一步的计算原理可以在 这里 找到),证明如下:

假设 2P-1 是素数的情况下,p 却是合数,那么令 p=r*s,r 和 s 都是大于 1 的正整数,那么 xrs-1 就可以拆解成 xs-1 乘以 xs(r-1) + xs(r-2) + … + xs + 1。所以,如果 p 是合数的话,2p-1 也会是合数(因为它可以拆出 2s-1 的因子来),这与假设命题不符,所以 p 就只能是素数了。

值得注意的是,对于 n>1,因为 x-1 可以整除 xn-1 ,所以如果要 xn-1 为素数的话,x-1 就必须等于 1 了,所以 x 就只能是 2 了。那么,就可以得到如下推论:

如果 a 和 n 都是大于 1 的正整数,如果 an-1 是素数的话,那么 a 就只能是 2,而且 n 必须为素数

美国中央密苏里大学数学教授 Curtis Cooper 领导的研究小组于一周前的 1 月 25 日发现了已知的最大梅森素数——257885161−1(即 2 的 57885161 次方减 1);该素数有 17425170 位,如果用普通字号将它连续打印下来,它的长度可超过 65 公里。

梅森素数的分布极不规则,连找到梅森素数的时间分布都极不规则,有时许多年未能找到一个,而有时则一下找到好几个,探索梅森素数的分布规律似乎比寻找新的梅森素数更为困难。中国的业余数学家周海中在 1992 年给出了梅森素数分布的精确表达式(“周氏猜测”):

对于素数 p 和梅森素数 Mp=2P-1 ,当 22^n<p<22^(n+1) 时,Mp 有 2n+1-1 个;

推论:当 p<22^(n+1) 时,Mp 有 2n+2-n-2 个。

梅森素数是测试计算机速度的一个有力工具,实际上寻找梅森素数的过程也推动了分布式计算的发展(数学这样的基础学科在寻找当前实际意义的时候往往如此,但是谁也无法预料对于未来的工程学科的发展能有多重大的意义),在实际领域,梅森素数也可以用来加密数据。由于把两个非常大的数相乘很容易,但是如果要把一个非常大的数分解,将是非常困难的,在这种加密设计中,要使用很大的素数,素数越大,理论上越不容易被破译。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

6,971 次阅读

发表评论

电子邮件地址不会被公开。

back to top