我们为何要寻找那些动辄千万位的素数?

作者: Ittay Weiss

来源: https://theconversation.com/why-do-we-need-to-know-about-prime-numbers-with-millions-of-digits-89878

发布日期: 2018-01-15

本文探讨了寻找大素数的意义,特别是梅森素数在数学和加密技术中的应用。文章指出,尽管这些大素数在实际应用中的必要性可能不大,但它们代表了数学家对未知的探索和对数学本质的追求。

素数的特别之处远不仅是只能被自己和1整除的数字,它们是数学里神秘的谜团,是自欧几里得证明它们没有终点以来就一直让数学家渴望解开的秘密。

“互联网梅森素数大搜索”(GIMPS)是一个正在进行的项目,其目的在于发现越来越多的特别罕见的素数。最近,我们找到了迄今为止已知的最大素数,共23,249,425位,这是个非常大的数字,轻轻松松就能填满9000多页纸。相比之下,在整个可观测宇宙中,原子数的总和估计不超过100位数字。

刚被发现的素数可被简写为2^77232917-1(可被写为2的p次幂减1的素数,被称为梅森素数),这是一位电气工程师耗时14年计算得来的。

或许你会问,如果一个数字超过了2300多万位,那它还具有被知道的意义吗?难道最重要的数字不是可以用来量化我们世界的那些吗?事实并非如此。我们需要了解不同数字的属性,以便让我们不仅能够继续发展我们赖以生存的技术,同时还能确保它的安全。

素数在计算方面最常见的应用之一就是RSA加密系统。1978年,Ron Rivest,Adi Shamir和Leonard Adleman将一些简单的数字相关的已知事实结合在一起,创建了RSA加密演算法。他们开发的系统确保了在线信息的安全传输,如信用卡号码。

该算法所需的第一个重要成分就是两个大的素数。数字越大,加密越安全。计数数字1、2、3、4等自然数在这里显然也非常有用。但素数是所有自然数的基础,所以更为重要。

以数字70为例,首先它是2和35的乘积;接着,35是5和7的乘积。所以70是三个较小的数字:2、5和7的乘积。这就是70可分解的所有数字,因为这些数字都无法再被进一步细分。也就是说我们找到了构成70的初始部分,得到了它的素因子分解。

将两个数字相乘,即使数字非常大、过程很单调乏味,却也可算是一个简单的任务。但寻找素因子却是非常困难的,这也正是RSA系统所利用的。

假设小红和小明要通过互联网进行秘密的通信,那么他们需要一个加密系统。如果他们先亲自见上一面,就可以事先设计一种只有他们知道的加密和解密方法,但是他们的首次接触就是通过在线网络,那么他们首先需要公开交流的就是加密系统本身——这是一件冒险的事。

但是,如果小红选择两个大的素数,计算出这两个素数的乘积,再公开的交换这个乘积的信息,那么要找出她原来选择的两个素数是一件非常艰巨的任务,因为只有她知道这两个素数。

所以小红可以把她的乘积传达给小明,并对素因数保密。小明用这个乘积来加密他要发送给小红的信息,解密这一信息必须用到只有小红才知道的素因数。所以如果有第三个人小亮在窃听,他无法破译小明的消息,除非他知道了小红最先设置的素因素,而这些素因数是从来没有进行过传播的。如果小亮还不死心,试图将乘积分解成两个原始素数,那么即使用的是最快的超级计算机,也不可能在太阳爆炸之前完成这一任务的算法。

其他密码系统也在广泛的使用大的素数。计算机的运行速度越快,能够破解的数字就越大。对于现代应用来说,测量上百位数的素数已足以完成。当然这些数字与最近发现的超级巨大的素数相比,就太微不足道了。然而,最新找到的素数是如此之大,以至于目前在计算速度方面没有任何可想象的先进技术需要用它来作为安全加密。甚至是量子计算机所带来的风险,可能都用不上这样的庞然大数来确保安全。

然而,刚发现的梅森素数既非是为了拥有更安全的密码系统,也非为了改进计算机。而是数学家们内心对揭开“素数”所蕴含的神秘的渴望,不断的激发着对素数的探求。这是一个以数1,2,3……开始,将我们推向研究前沿的原始动力。

著名的英国数学家哈代(Godfrey Harold Hardy)曾说过:“总体而言,纯数学的应用价值是高于应用数学的。‘数学技术’是这其中最为顶级的应用,而数学的技术主要通过纯数学孕育而生。”

那些庞大的素数最终是否有什么应用价值,至少对哈代来说似乎是一个无关紧要的问题。对这些数字的探索的目的在于——它不断地满足着人类对智慧的渴望,这种渴望从欧几里得证明素数无穷便已开始,至今仍在延续。

UUID: f7dc0c0d-4339-423b-abc7-3b7e8f421f7e

原始文件名: /home/andie/dev/tudou/annot/AI语料库-20240917-V2/AI语料库/原理公众号-pdf2txt/2018年/2018-01-15_我们为何要寻找那些动辄千万位的素数?.txt

是否为广告: 否

处理费用: 0.0042 元