梅森素数

梅森素数 古希腊数学家欧几里德就已证明素数有无穷多个,并提出一些素数可写成“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个国家的近一百万台计算机参与计算)。

在寻找梅森素数的过程中,并不是漫无目的的。很容易证明,如果 2P-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 个。

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

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

分享到:

发表评论

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

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>


Preview on Feedage: