GIMPS:全球首个分布式计算项目

GIMPS是 Great Internet Mersenne Prime Search的英文简称,即梅森素数互联网大搜索;它是世界上第一个基于互联网的分布式计算项目。1996年初,美国数学家及程序设计师乔治·沃特曼于1996年编制了计算程序——GIMPS;其目的是对超大梅森素数进行快速、准确的搜索,为人们寻找新的梅森素数提供方便。

在谈论GIMPS之前,我们先来简要谈谈什么是梅森素数和分布式计算。2300年前,古希腊数学家欧几里德就已证明素数有无穷多个,并提出一些素数可写成“2^P-1”(其中指数P也是素数)的形式。这种特殊形式的素数,具有独特的性质和着魔般的魅力,千百年来一直吸引着众多的数学家(包括数学大师费马、笛卡尔、莱布尼兹、哥德巴赫、欧拉、高斯和图灵)和无数业余数学爱好者对它进行探究。17世纪的法国数学家、法兰西科学院的奠基人马林·梅森对“2^P-1”型的素数做过较为系统且深入的探究。为了纪念他,国际数学界19世纪末在瑞士就将这种素数命名为“梅森素数”。迄今为止,人类仅发现51个梅森素数。这种素数稀奇而迷人,故被人们称为“数海明珠”。

分布式计算是一种计算方法,和集中式计算是相对的。它将该应用分解成许多小的部分,分配给多台计算机进行处理;这样可以节约整体计算时间,大大提高计算效率。目前分布式计算项目已经被用于使用世界各地成千上万位志愿者的个人计算机的闲置计算能力,通过互联网,可以分析来自外太空的信号(如SETI@Home项目),还可以寻找并发现对抗某些病毒的更为有效的药物(如United Devices项目)等。这些项目都很庞大,需要惊人的计算量,这不是个人计算机所能完成的;另外,超级计算机的造价和维护非常的昂贵,这不是一般科研组织所能承受的。随着科学的发展,一种廉价的、高效的、维护方便的崭新计算方法应运而生——分布式计算。

GIMPS就是利用互联网上的计算机的中央处理器(CPU)的闲置处理能力来寻找梅森素数的科研项目。美国计算机专家斯科特•库尔沃斯基于1997年建立了“素数网”(PrimeNet),使分配搜索区间和向GIMPS发送报告自动化。为了激励人们寻找梅森素数和促进分布式计算技术发展,总部设在美国的电子前沿基金会(EFF)于1999年向全世界宣布了为通过GIMPS项目来寻找梅森素数而设立的“协同计算奖”。它规定向第一个找到超过100万位数的个人或机构颁发5万美元。后面的奖金依次为:超过1千万位数,10万美元;超过1亿位数,15万美元;超过10亿位数,25万美元。不过,绝大多数人参与该项目并不是为了金钱,而是出于好奇心、求知欲和荣誉感。

美国计算机专家埃德森·史密斯于2008年通过GIMPS项目,发现了第46个梅森素数——2^43112609-1;该素数有12978189位,它是当时已知的最大素数。史密斯是第一个找到超过1千万位的梅森素数的人,他获得了10万美元的奖金;年底这一重大发现被著名的美国《时代》周刊评为“2008年度50项最佳发明”之一。前不久,来自美国佛罗里达州的互联网专家及数学爱好者帕特里克·拉罗什利用GIMPS项目,成功发现第51个梅森素数——2^82589933-1;该数有24862048位,它是当今人类发现的最大素数。如果用普通字号将这个梅森素数打印下来,其长度将超过100公里!

26年来,人们通过GIMPS项目找到了17个梅森素数,其发现者分别来自美国(11)、德国(2)、英国(1)、法国(1)、挪威(1)和加拿大(1)。著名的英国《自然》杂志曾声称,GIMPS项目不仅会进一步激发人们对梅森素数探究的热情,而且会引起人们对分布式计算技术应用的高度重视。而美国数学家乔丹·埃伦伯格却认为,通过GIMPS项目“发现一个梅森素数就像是在干草堆里找一根针那样困难;这项发现在计算机工程领域的价值要远大于数学领域的价值。”目前世界上有200多个国家和地区近百万人参加GIMPS项目,并动用了超过245万核中央处理器联网来寻找新的梅森素数。

值得一提的是,虽然目前人们通过GIMPS项目寻找梅森素数非常火爆,但是对梅森素数的基础研究一直处在发展与进步中。例如在梅森素数的素性判断方面,法国数学家爱德华·鲁卡斯和美国数学家德里克·雷默都做出了重要贡献,以他们命名的“鲁卡斯-雷默方法”是检测梅森素数素性的最佳方法;奥地利计算机专家克日什托夫•皮亚特克最近在这方面取得突破,大大提高了梅森素数素性的判定。又如在梅森素数分布研究方面,中国科学家及未来学家周海中于1992年给出了梅森素数分布的精确表达式,这一研究成果被国际上命名为“周氏猜测”;美籍挪威数论大师、菲尔茨奖和沃尔夫奖得主阿特勒·塞尔伯格认为:周氏猜测具有创新性,开创了富于启发性的新方法;其创新性还表现在揭示新的规律上。

作为首个分布式计算项目,GIMPS一直是科研中最令人着迷的。完全可以相信:在GIMPS的助力下,人们一定能够找到新的、更大的梅森素数。

文/董国祥(作者单位:中国科学院大学数学科学学院)