当前位置: 首页 > 期刊 > 《百科知识》 > 2008年第24期
编号:12751696
大素数新纪录(1)
http://www.100md.com 2016年4月2日 期刊网 2008年第24期
     2008年8、9月,也就是刀世瞩目的奥运会和残奥会期间,另一个领域也就是数学领域的世界纪录被刷新,美国人和德国人分别发现了当前已知的最大素数——第45个和第46个梅森素数。

    让我们来解释一下什么是梅森素数。素数这个概念大家都知道,也就是一个正整数,除了1和它本身之外,没有其他因子的数。现在我们规定1不是素数。因此,最小的素数是2,它是惟一的偶素数,其他的素数均为奇数。这样10以下的素数有4个,它们是:2,3,5,7;100以下的素数有25个。大部分正整数不是素数,我们称为合数,它们总可以分解成为素数的乘积,也说是它们有除1和数本身之外的因子。例如

    21=3×7,91=7×13,显然,在一定范围之内,合数要比素数多得多,不过,欧几里得早已证明素数有无穷多。

    虽然任何素数之后肯定还有素数,可是人们并不知道一个给定的数是不是素数。理论上讲,只要你有足够的时间和精力就可以完成,也就是对于整数Ⅳ,用小于或等于根号N的素数去除它,如果都除不尽,那Ⅳ就是素数。这事看起来容易做起来难。如果Ⅳ不大,如Ⅳ只有10位,也许可以用5位以内的素数一个一个去除,看看是否除得尽。可是如果Ⅳ为100位,就根本办不到了,因为我们还不知道50位以内的素数到底有多少,实际上至今25位以内的素数有哪些,我们也不清楚。
, 百拇医药
    因此,要想摘取最大素数的桂冠,还得另觅他途。找一种特殊形式的素数,这就是梅森素数。梅森是位教士,是科学的组织者,他那时——17世纪上半世纪,没有科学期刊,每个人的工作通过书信传到他那里,然后,他再传给别人,这样大家都可以分享最新的知识。梅森自己也对数学有极大兴趣,他发现:

    如果2p-1是素数,则p一定是素数,因此后来人们就手把2p-1型的素数,称为梅森素数,常常简记为Mp。但是,这定理反过来是否对呢?也就是:

    如果p是素数,2p-1是否素数?

    梅森试了试最小的素数,当p=2,3,5,7时,2p-1分别等于3,7,31,127,恰巧都是素数,于是他猜想p=13,17,19,31,67,127,257时,2 p—l也是素数。当时,已经知道211-1不是素数,他们费了很大劲把211-1=2047分解因子成23×89。不过他的上述猜想也包含后来人们在搜寻梅森素数时的两大失误:
, 百拇医药
    1、Mp不是素数,证明这点也很困难。例如梅森猜想中,M67,M257不是素数。前者在梅森之后200多年也就是1876年才证明,后者在1927年才证明。

    2、梅森的猜想有遗漏,例如当p=61,89,107时,Mp是梅森素数。发现了一个新的梅森素数之后,是否还有比它小的梅森素数?

    这些问题看起来简单,但是找起来极难。因此,到19世纪末,只找到10个梅森素数,最大的是p=127。进入20世纪,才发现在127之前,还有p=89,107时Mp也是梅森素数,这样在1913年前p=127之前的梅森素数才找完全,它们是p=2,3,5,7,13,17,19,31,61,89,107,127。在100以下的素数25个中,只有10个素数形成梅森素数。

    人力计算到此为止了。搜寻梅森素数一直到电子计算机出现之后才又开展起来。1952年利用计算机得出5个新的梅森素数。其后就要靠当时最快的计算机了,值得一提的是,1978年美国两位18岁中学生(一男一女)发现了第25个,第二年升入大学的男生发现第26个,这两个M p,p首次超过20000。1979年到1995年,斯洛温斯基利用巨型计算机得出另外7个梅森素数,他遗漏的一个在1988年由别人找到。
, http://www.100md.com
    在大型计算面前,巨型计算机还是难以招架。1995年网络的普及,进一步推动梅森素数的探索。这年,沃尔特曼建立一个GIMPS的计划,使得搜索进度大大加快。从1996年到2000年发现了从35到38四个Mp,从2001年到2006年发现从39到44个Mp。

    2008年8月23日及9月6日,美国和德国两个小组分别发现了两个新的梅森素数:

    243112609-1及237156667-1

    前者超过1200万位,后者超过1100万位,而以前的44个梅森素数都没有超过1000万位。当然,它们也是现在所知的最大素数。在参加素数奥运的选手中,许多打破纪录的是业余爱好者,从20岁的大学生到眼科医生!

    既然找到一个梅森素数如此困难,人们为什么又乐此不疲呢?我看,它至少有三个方面的重要意义。
, http://www.100md.com
    1、计算方面。梅森素数的搜索要求对计算机及计算方法进行不断改进。

    2、应用方面。大素数有许多用处,特别是密码学。如果你能很快地进行素数判定和因子分解,则对密码设计是一个重要贡献。如果一个密码是由两个大素数相乘得到,那就在短时间内很难破译,从而保证了信息系统的安全。

    3、理论方面。梅森素数来源于一个千古未解的数学难题——完美数(也称完全数)问题。完美数这个概念来自毕达哥拉斯,它的原义是指十全十美的数。它的定义是一个自然数Ⅳ,它等于其真因子(即除自身之外的因子)之和,换句话说,如果N的所有因子之和记作σ(N),则σ(N)=2N。表面上看这个条件不是太苛刻,实际上大多数自然数并不满足这个条件。我们不妨看看下面的例子:6的因子有1,2,3,6,因此,σ(6)=1+2+3+6—12=2×6,所以6是个完美数。可是14的因子有1,2,7,14,因此,σ(14)=1+2+7+14—2.4<2×14

, 百拇医药     而口(24)=1+2+3+4+6+8+12+24=60>2×24

    可见14和24都不是完美数。6是第一个完美数,第二个完美数是28,因为

    σ(28)=1+2+4+7+14+28=56=2×28。

    后来到公元1世纪才发现在100与1000之间,1000与10000之间各有一个完美数,它们是496和8128。这4个就是古代所知的所有完美数。虽然,古代知道的完美数很少,可是,欧几里得在《几何原本》中证明一个一般的定理,它给出(偶)完美数的必要条件:

    如2n-1是素数,则2n-1(2n-1)是完美数。到17世纪,伟大的哲学家、数学家笛卡尔对, http://www.100md.com(胡作玄)
1 2下一页