(本文作者张晓泉,清华大学经管学院 Irwin and Joan Jacobs讲席教授)
19世纪伟大的数学家高斯曾说过:“数学是科学的皇后,数论是数学的皇后”。数论中的各种猜想犹如数学皇冠上的一颗颗璀璨明珠,而其中许多著名的未解之谜都与一类特殊的数密切相关——素数。
素数(prime number,又称质数)是只能被自身和1整除的数字,其他正整数都可以表示为素数的乘积,因此素数常被视为数学世界的“原子”。虽然“素数”的中文名称显得朴实无华,但英文名中的“prime”一词本身就带有一种重要性和优越感,直观地表明了素数在数学中的核心地位。
素数可谓是数论中的顶流。自欧几里得证明素数无穷以来,数学家们一直在探索它们的奥秘,有关素数的新发现和新突破总能成为焦点,引起广泛的关注。
这不,前几天就刚出了一个大新闻。前英伟达的员工Luke Durant发现了新的已知最大素数——2136,279,841– 1,该数字有41,024,320位,比上一个纪录多出1600多万位。如果打印出来(每页50行,每行75位数字),需要11000张纸。
这个新发现的素数也是第52个梅森素数(Mersenne prime),即满足公式Mp = 2p– 1的素数(其中p是素数),该素数因法国数学家马林·梅森(Marin Mersenne)得名。
由于梅森素数的特殊形式,使它在数学计算上有着独特的优势,尤其是在素数检验中。
简单来说,相较于其他素数,梅森素数的可操作性更强,验证效率更高。所以在寻找更大的素数时,往往优先考虑梅森素数。
即便如此,寻找梅森素数从来都不是一件轻松容易的事。
古希腊人仅发现了4个梅森素数,到1914年才累计到12个,几乎每千年才能发现6个,这个进程相当漫长。
计算机的出现带来了革命性的改变。满足梅森素数条件的计算很容易编写为程序代码,这使得计算机成为搜索梅森素数的绝对利器。
1952年,计算机首次被用于素数搜索,仅在当年就发现了5个梅森素数。不到20年的时间,计算机发现的数量已经和过去两千多年相当。1914年,最大梅森素数仅有39位数字;100年后,梅森素数的长度已经超过1700万位;如今,梅森素数的数量虽然只增加到了52个,但其位数已超过4100万。
探索梅森素数的过程显示了人类与计算机在计算能力上的巨大差距。计算机接手这一任务后,寻找梅森素数的过程也可以用来衡量新技术和算法的速度及性能。随着数字的增大,搜索难度和所需算力也随之增加。
于是,一个致力于寻找最大梅森素数的组织应运而生——Great Internet Mersenne Prime Search (GIMPS)。正是通过GIMPS提供的免费程序,Luke成功发现了目前已知的最大梅森素数。
GIMPS是一个分布式计算志愿者合作项目,创立于1996年,成立以来平均每1到2年就能发现一个新的梅森素数,最近的这次发现虽然耗时近六年,却标志着GIMPS至今已经找到了18个梅森素数,其中16个在发现时都是已知的最大素数。
GIMPS向所有人开放,任何人都可以加入成为分布式虚拟超级计算机的一部分。加入GIMPS的计算机会分配到一个待验证的大数(即2的某幂次减1),而任务就是检验它是否为素数。
这次最新发现的一个特别之处在于,它是首个通过GPU发现的梅森素数。Luke创建的“云超级计算机”由分布在17 个国家/地区的24 个数据中心区域的数千个服务器 GPU 组成,这不仅结束了长达28年由普通个人电脑寻找巨大素数的历史,也展示了GPU在人工智能领域之外,在基础数学和科学研究中的巨大潜力。
看到这里,有人可能会问:为何要费时费力地去寻找最大素数?有什么用?
一个常见的回答是,素数在信息安全和密码学中具有重要作用。
例如,RSA加密系统依赖大素数来确保安全性,素数越大,加密越安全。不过,对于现代应用,数百位的素数已经足够,而新发现的素数过于庞大,以至于现有算力难以将其用于加密安全。
难道是为了奖金?
Electronic Frontier Foundation的确通过GIMPS设立了奖金:第一个发现长度超过1000万位、1亿位和10亿位素数的人将分别获得10万美元、15万美元和25万美元。如果发现的素数小于以上条件,也会获得3000美元的奖励。
由于第一项奖金已经被领走了,所以Luke此次只拿到了3000美元。即便是最高奖金,相比于要付出的精力和成本,其实也谈不上丰厚诱人的程度,奖金显然并非驱动力。更何况,对于多数参与者而言,寻找大素数只是一项业余爱好,背后更多是出于对数学的纯粹热爱。所谓的「悬赏」,不过是锦上添花的奖励。
对这些探索者来说,过程本就充满了魅力,而发现本身就是最大的嘉奖。因为它象征着人类对无限的追寻又前进了一步。
至于有用与否,可以用英国著名数学家哈代的话来回答:“纯数学明显在总体上比应用数学更有用。纯数学家似乎在实用性和美学性方面都占优。因为最有用的是技巧,而数学技巧是由纯数学教授的。”
在探索与发现的道路上,有用和无用之间的鸿沟往往会随着时间而改变。哈代曾将数论(他自己的研究领域)归为“无用”,然而,1977 年Ron Rivest、Adi Shamir 和 Leonard Adleman三位数学家创建了RSA算法,一举奠定了数论在现代社会不可动摇的地位。
探索素数满足了人类对知识的渴求,这种渴求始于欧几里得对素数无穷性的证明,并延续至今。
本文仅代表作者观点。