财新传媒
位置:博客 > 返朴 > 2021,一个平平无奇的数字

2021,一个平平无奇的数字

撰文 | 倪忆(加州理工学院数学系教授)
 
跌宕起伏的2020年终于过去,2021年来到人间。按照笔者中学时参加数学竞赛的惯例,总要分析一下2021这个数字的性质,以防竞赛中遇上包含这一数字的题目。像1997年国际数学奥林匹克,第四题里就出现了1997。
 
然而,跟2020比起来,2021实在是一个平平无奇的数字。
2020有许多有趣的分拆,比如它是5个404的和。(有位读者问:“404啥意思?” 这个嘛,大家应该都经常看到404页面是不是?)
2020=1024+996,所以2020年10月24日码农节有着特殊的意义。
2021呢,笔者尚未找到这样的分拆,难道要用2021=1024+997?那可就太绝望了!
 
素数和半素数
 
分拆不成,那么试着因数分解?我们知道,如果一个大于1的整数的因子只有1和它本身,那么这个数就被称为素数(也称质数)。2、3、5、7是最小的几个素数,1997也是素数。素数是“数论”这门数学分支里研究的基本对象,在数学里有着重要意义。如果2021是一个素数,那么从数学上看它就很有意思。可是很遗憾,
 
2021=43*47
 
所以它不是素数。
 
在上面的乘式里,43和47都是素数。如果一个正整数是两个(可以相同)素数的乘积,那么这个正整数就被称为半素数 (semiprime)。所以2021就是一个“半素数”。
 
在数论里有许多跟素数有关的问题。比如著名的哥德巴赫猜想,其内容就是任何一个大于4的偶数都能写成两个素数的和。如果两个素数彼此之间只差2,那么它们就被称为一对孪生素数。比如1997和1999就是一对孪生素数。孪生素数猜想断言存在无穷多对孪生素数。
张益唐在孪生素数猜想上作出了重大突破丨图源:北京大学新闻网
 
有的时候,数学家无法证明关于素数的猜想,就退而求其次,看看能不能证明关于半素数的相应结论。最著名的例子就是陈景润在哥德巴赫猜想上的工作,通常被记为“1+2”,其数学含义是:任何一个大于4的偶数都能写成两个数的和,其中一个数是素数,另外一个数是素数或者半素数。公众不太了解的是,陈景润在孪生素数猜想上也有类似的结果。他证明了,存在无穷多个素数,使得这个素数加上2以后是一个素数或者半素数。
著名数学家陈景润丨图源:新华网
 
半素数的一个性质是,如果把它写成两个大于1的整数的乘积,那么在不考虑顺序的情况下,这种乘式是唯一的。(读者可以思考一下,除了半素数以外,还有没有别的整数有这样的性质?)1974年,人们用阿雷西博射电望远镜向武仙座M13球状星团发射了一段共1679比特的信息。破解阿雷西博信息的第一步,就是注意到1679是一个半素数,所以可以把信息组成一个73×23的矩形。
阿雷西博信息中包括1到10的数字,DNA、人类和太阳系的信息,甚至阿雷西博望远镜本身的形象和直径。丨图源:维基百科
 
乌拉姆螺旋
 
2021本身的两个素因子是43和47,如果你是笔者这样的业余数论爱好者,多半可以一眼认出,它们是欧拉 (Leonhard Euler) 发现的一系列能用多项式生成的素数中的两个。欧拉在1772年注意到,对于二次多项式
 
 
全部是素数。这个事实可以用下面的乌拉姆螺旋(Ulam spiral)来直观地表示。从41开始,把自然数按照逆时针螺旋形写在方格纸上,然后标出其中所有的素数。我们会发现,包含41的右上至左下的对角线上连续排列着很多个素数。
从41开始的乌拉姆螺旋,其中素数标为蓝色,素数的平方标为绿色。丨图源:Twitter账户Fermat's Library
 
注:乌拉姆(Stanislaw Ulam)是一位波兰犹太裔数学家,在纳粹入侵波兰前夕移居美国。他参与了研制原子弹的曼哈顿工程,并在氢弹研制中发挥了关键作用。美英等国的氢弹构型即被命名为泰勒-乌拉姆构型。乌拉姆螺旋是他于一次会议上,听报告过程中闲得无聊,在纸上乱画时发现的。
 
欧拉的这个二次多项式不可能永远得到素数,但是接下来的很多值仍然是素数或者半素数:
 
 
1857年,俄国数学家布尼亚科夫斯基(Viktor Bunyakovsky)猜测,存在无穷多个正整数n,使得P(n)是素数。(布尼亚科夫斯基实际上对于更为一般的多项式作出了这个猜想。) 这个猜想至今尚未得到证明。1978年,波兰数学家伊万尼克(Henryk Iwaniec)证明了,存在无穷多个正整数n,使得P(n)是素数或者半素数。(伊万尼克对于一般的二次多项式证明了这个结论。)
伊万尼克从特首梁振英手中接过2015年度邵逸夫数学奖丨图源:邵逸夫奖
 
RSA公钥密码
 
那么,为什么数学家们要研究素数或者半素数呢?它们跟我们的生活有什么关系?能吃吗?
 
答案是,它们确实跟我们的生活有着密切关系。我们今天能够开通网上银行被巨头割韭菜,进行网络购物双十一剁手,甚至上网浏览,都要感谢素数和半素数。究其原因,是利用了如下的性质:把两个数相乘很容易,把一个数分解成乘积则很难。
 
我们可以看看2021这个例子。如果要计算43×47,小学三四年级的学生就能轻松算出结果是2021。但如果不知道其中任何一个因子,要想找出来2021是哪两个数的乘积就不那么容易。
 
 
科尔丨图源:维基百科
 
 
但如果数字更大,分解仍然十分困难。比如我们拿两个300位以上的素数相乘,用普通计算机可以迅速算出结果。但如果只给你这个乘积的结果,在不知道任何一个因子的情况下,即便是使用超级计算机也需要很多年才可以分解出来。
 
大数分解的这一特性被密码学家用来设计公钥密码。密码在各类影视文学作品里经常出现,比如福尔摩斯探案故事里的跳舞小人。在这个故事里,出现了一个密钥,就是把英文字母一一对应于各种不同形态的跳舞小人。
 
在密码传输过程中有两个需要使用密钥的步骤。一个是发送者把正常信息加密为旁人看不懂的信息,另一个是接收者把这段旁人看不懂的信息解密为正常信息。早期人们使用的密码都是对称式密码,加密和解密用的是同一个密钥。如果你知道如何加密,自然就知道如何解密;反过来也是一样,知道如何解密,自然就知道如何加密。
跳舞小人密钥丨图源:一起扣扣网
 
对称式密码适用于一对一通信,但在多对多通信的情形下就很不方便。比如说张三、李四、王五三个人互相之间用同一密码通信,但有的时候张三想跟李四单独通信,内容不想让王五知道,这时再用以前的同一密码就不合适了,只能另起炉灶采用一套新的密码。这还只是三个人互相通信,要是全球几十亿人互相通信会更麻烦。公钥密码就是为了解决这一问题而设计的。
 
在公钥密码里,每个用户被分配了两套密钥,一套加密密钥,一套解密密钥。其中加密密钥公开给所有人,解密密钥则只有这个用户本人才知道。如果张三要给李四发送信息,他只需要使用李四的加密密钥来对原始信息加密,把加密信息发送给李四。那么就只有李四本人才能够用李四的解密密钥来对加密信息解密。
用公钥密码还可以实现数字签名。比如张三给李四发送一段信息,他可以先用张三自己的解密密钥来处理原始信息,得到一号加密信息,然后再用李四的加密密钥来对一号加密信息加密,得到二号加密信息。实际发送给李四的是二号加密信息。李四收到二号加密信息后,需要先用自己的解密密钥来解密二号加密信息,得到一号加密信息,然后再用张三的加密密钥来处理一下,就得到原始信息。这样发送出来的二号加密信息,就是只有张三才能发送,并且只有李四才能解读的。于是我们便得到了旁人无法仿造的张三的“数字签名”。
公钥密码机制的关键在于,从加密密钥很难推断出解密密钥。1977年,三位麻省理工学院的密码学家Ronald Rivest, Adi Shamir, 和Leonard Adleman提出了RSA公钥密码,利用大数分解的困难来实现公钥密码。具体而言,每个用户被分配了两个大素数。这两个大素数的乘积(即一个“半素数”)被公开给了所有用户,但只有这个用户本身才知道是哪两个素数。解密密钥需要知道这两个素数,而加密密钥只需要使用它们的乘积。
1983年,左起Shamir, Rivest, Adleman 丨图源:imps.mcmaster.ca
 
在RSA公钥密码里,只要使用的两个素数足够大,就可以保证密码是安全的。在网络时代,公钥密码被广泛应用于网络银行、电子商务等场景中。读者可能会注意到,以前上网,浏览器里的地址多半是以http://开头,但近年来多半是以https://开头。在https协议里就使用了公钥密码,比http协议更安全。然而,在1994年,Peter Shor提出了一个用量子计算机快速进行大数分解的Shor算法。一旦可实用的量子计算机被建成,RSA公钥密码将不再安全。如何设计更安全的密码,以及如何破译已有的密码,始终是密码学家不懈研究的问题,而数论在其中发挥着不可代替的作用。
 
当然了,RSA用到的半素数都是有数百位甚至上千位的大数,不会用到2021这么小的数。我们的年份2021,仍然只是一个平平无奇的数字。希望2021年,也像这个数字一样平平无奇,而不像2020年那样惊心动魄。
 
本文经授权转载自微信公众号“普林小虎队”。



推荐 61