2021,一個平平無奇的數字


2021,一個平平無奇的數字的頭圖

2021,一個平平無奇的數字

撰文| 倪憶(加州理工學院數學系教授)

來源:普林小虎隊

跌宕起伏的2020年終於過去,2021年來到人間。按照筆者中學時參加數學競賽的慣例,總要分析一下2021這個數字的性質,以防競賽中遇上包含這一數字的題目。像1997年國際數學奧林匹克,第四題裡就出現了1997。

1997年IMO第四題,有興趣的讀者可以做做。
然而,跟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是一個素數,那麼從數學上看它就很有意思。可是很遺憾,

所以它不是素數。
在上面的乘式裡,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年註意到,對於二次多項式

當n取

0,1,2,3,……,39

時,得到的數值是

41,43,47,53,……,1601,

全部是素數。這個事實可以用下面的烏拉姆螺旋(Ulam spiral)來直觀地表示。從41開始,把自然數按照逆時針螺旋形寫在方格紙上,然後標出其中所有的素數。我們會發現,包含41的右上至左下的對角線上連續排列著很多個素數。

從41開始的烏拉姆螺旋,其中素數標為藍色,素數的平方標為綠色。丨圖源:Twitter賬戶Fermat’s Library

注:烏拉姆(Stanislaw Ulam)是一位波蘭猶太裔數學家,在納粹入侵波蘭前夕移居美國。他參與了研製原子彈的曼哈頓工程,並在氫彈研製中發揮了關鍵作用。美英等國的氫彈構型即被命名為泰勒-烏拉姆構型。烏拉姆螺旋是他於一次會議上,聽報告過程中閒得無聊,在紙上亂畫時發現的。

歐拉的這個二次多項式不可能永遠得到素數,但是接下來的很多值仍然是素數或者半素數:

其中P(44) 正是我們的年份2021!
用計算機很容易算出,要一直到n=420,我們才會得到第一個既不是素數又不是半素數的P(n):

而在從n=0到n=419的總共420個P(n)中,有281個素數,139個半素數。
1857年,俄國數學家布尼亞科夫斯基(Viktor Bunyakovsky)猜測,存在無窮多個正整數n,使得P(n)是素數。 (布尼亞科夫斯基實際上對於更為一般的多項式作出了這個猜想。)這個猜想至今尚未得到證明。 1978年,波蘭數學家伊万尼克(Henryk Iwaniec)證明了,存在無窮多個正整數n,使得P(n)是素數或者半素數。 (伊万尼克對於一般的二次多項式證明了這個結論。)

伊万尼克從特首梁振英手中接過2015年度邵逸夫數學獎丨圖源:邵逸夫獎

RSA公鑰密碼

那麼,為什麼數學家們要研究素數或者半素數呢?它們跟我們的生活有什麼關係?能吃嗎?
答案是,它們確實跟我們的生活有著密切關係。我們今天能夠開通網上銀行被巨頭割韭菜,進行網絡購物雙十一剁手,甚至上網瀏覽,都要感謝素數和半素數。究其原因,是利用瞭如下的性質:把兩個數相乘很容易,把一個數分解成乘積則很難。
我們可以看看2021這個例子。如果要計算43×47,小學三四年級的學生就能輕鬆算出結果是2021。但如果不知道其中任何一個因子,要想找出來2021是哪兩個數的乘積就不那麼容易。

另外一個著名的例子是分解

1903年,美國數學家科爾(Frank Nelson Cole)曾經在美國數學會的會議上作過一次無言的“演講”。他沉默地走上講台,用粉筆在黑板上算出

然後他繼續計算

得到的結果跟前面一樣。他的無言演講贏得了全場的起立鼓掌。有人問他是怎樣找到這一分解的,他說:“三年中的全部星期天。”

科爾丨圖源:維基百科

實際上,計算

細心的人最多五分鐘就能手算出來,——但找到這樣的分解卻花費了科爾一百多天。 (科爾的名字被用於命名美國數學會在數論和代數方面的最高獎,張益唐和許晨陽曾分別獲得這兩項科爾獎)
今天,用一台普通的計算機就能輕易分解2021或者

但如果數字更大,分解仍然十分困難。比如我們拿兩個300位以上的素數相乘,用普通計算機可以迅速算出結果。但如果只給你這個乘積的結果,在不知道任何一個因子的情況下,即便是使用超級計算機也需要很多年才可以分解出來。
大數分解的這一特性被密碼學家用來設計公鑰密碼。密碼在各類影視文學作品裡經常出現,比如福爾摩斯探案故事裡的跳舞小人。在這個故事裡,出現了一個密鑰,就是把英文字母一一對應於各種不同形態的跳舞小人。

福爾摩斯和華生在研究跳舞小人密碼丨圖源:電視劇《神探夏洛克》
在密碼傳輸過程中有兩個需要使用密鑰的步驟。一個是發送者把正常信息加密為旁人看不懂的信息,另一個是接收者把這段旁人看不懂的信息解密為正常信息。早期人們使用的密碼都是對稱式密碼,加密和解密用的是同一個密鑰。如果你知道如何加密,自然就知道如何解密;反過來也是一樣,知道如何解密,自然就知道如何加密。

跳舞小人密鑰丨圖源:一起扣扣網
對稱式密碼適用於一對一通信,但在多對多通信的情形下就很不方便。比如說張三、李四、王五三個人互相之間用同一密碼通信,但有的時候張三想跟李四單獨通信,內容不想讓王五知道,這時再用以前的同一密碼就不合適了,只能另起爐灶採用一套新的密碼。這還只是三個人互相通信,要是全球幾十億人互相通信會更麻煩。公鑰密碼就是為了解決這一問題而設計的。
在公鑰密碼裡,每個用戶被分配了兩套密鑰,一套加密密鑰,一套解密密鑰。其中加密密鑰公開給所有人,解密密鑰則只有這個用戶本人才知道。如果張三要給李四發送信息,他只需要使用李四的加密密鑰來對原始信息加密,把加密信息發送給李四。那麼就只有李四本人才能夠用李四的解密密鑰來對加密信息解密。

用公鑰密碼還可以實現數字簽名。比如張三給李四發送一段信息,他可以先用張三自己的解密密鑰來處理原始信息,得到一號加密信息,然後再用李四的加密密鑰來對一號加密信息加密,得到二號加密信息。實際發送給李四的是二號加密信息。李四收到二號加密信息後,需要先用自己的解密密鑰來解密二號加密信息,得到一號加密信息,然後再用張三的加密密鑰來處理一下,就得到原始信息。這樣發送出來的二號加密信息,就是只有張三才能發送,並且只有李四才能解讀的。於是我們便得到了旁人無法仿造的張三的“數字簽名”。

公鑰密碼機制的關鍵在於,從加密密鑰很難推斷出解密密鑰。 1977年,三位麻省理工學院的密碼學家RonaldRivest, AdiShamir, 和LeonardAdleman提出了RSA公鑰密碼,利用大數分解的困難來實現公鑰密碼。具體而言,每個用戶被分配了兩個大素數。這兩個大素數的乘積(即一個“半素數”)被公開給了所有用戶,但只有這個用戶本身才知道是哪兩個素數。解密密鑰需要知道這兩個素數,而加密密鑰只需要使用它們的乘積。

1983年,左起Shamir, Rivest, Adleman 丨圖源:imps.mcmaster.ca
在RSA公鑰密碼裡,只要使用的兩個素數足夠大,就可以保證密碼是安全的。在網絡時代,公鑰密碼被廣泛應用於網絡銀行、電子商務等場景中。讀者可能會注意到,以前上網,瀏覽器裡的地址多半是以http://開頭,但近年來多半是以https://開頭。在https協議裡就使用了公鑰密碼,比http協議更安全。然而,在1994年,Peter Shor提出了一個用量子計算機快速進行大數分解的Shor算法。一旦可實用的量子計算機被建成,RSA公鑰密碼將不再安全。如何設計更安全的密碼,以及如何破譯已有的密碼,始終是密碼學家不懈研究的問題,而數論在其中發揮著不可代替的作用。
當然了,RSA用到的半素數都是有數百位甚至上千位的大數,不會用到2021這麼小的數。我們的年份2021,仍然只是一個平平無奇的數字。希望2021年,也像這個數字一樣平平無奇,而不像2020年那樣驚心動魄。

本文經授權轉載自微信公眾號“普林小虎隊”。