別再說數學與你無關:保護網路隱私,有請「質數大軍」

別再說數學與你無關:保護網路隱私,有請「質數大軍」
Photo Credit: Depositphotos

我們想讓你知道的是

由於分解某些大數(特別是兩個大質數的乘積)很困難,所以可以把質數變成數學「掛鎖」。假設有一種利用大數N加密訊息的方法,需要知道N的質因數才能解密。

作者:瑪莉安.弗萊伯格、瑞秋.湯瑪斯

網路隱私誰保護?質數大軍!

在自然數中,2是第一個超過最低限度的數。正如在第1章說過的,我們可以把自然數想像成串在繩上的珠子,一顆珠子代表1,一顆代表2,一顆代表3,以此類推到無限大;但這樣實在無趣。如果你用不一樣的方法串珠子,譬如從2開始,就會出現比較複雜玄妙的結構。

先用一顆珠子代表2,接著串一顆代表4,然後是代表6,以此類推。最後,你會串出一條全由偶數組成的項鍊。數字3不包含在這條項鍊上,所以你再串一條新的,先串一顆代表3的珠子,接著是代表6,然後是代表9,如此串下去,直到串完3的所有倍數為止。這兩條項鍊有一些共同的珠子,即6、12、18

及2×3=6的其他倍數,所以會纏繞在一起。不在這兩條項鍊上的下一個數字是5,可以此串出第三條項鍊,項鍊上包含5及它的所有倍數,這條項鍊會在10=2×5的倍數與2的項鍊纏繞,在15=3×5的倍數與3的項鍊纏繞,而在30=2×3×5的倍數,同時與這兩條項鍊纏繞在一起。

如此一來會產生一張優雅的自然數網。在各條項鍊最開頭的那些珠子就是質數;這些數除了自身與1之外沒有別的因數。數字2之所以特別,不僅因為它是第一個質數,還因為它是唯一的偶質數。此條項鍊上的其他珠子則都在網子內,都是質數的乘積。

這張網子正是年代最久、最基本的數學結果之一,有個恰如其分的稱呼,叫做算術基本定理(Fundamental Theorem of Arithmetic):每個大於1的整數若不是質數,就是質數的乘積。西元前300年左右,歐幾里得在他的經典之作《幾何原本》中證明了這個定理。此定理還說,乘積裡的質數沒別的選擇。舉例來說,乘出20的唯一方法就是把兩個2與一個5相乘。每個自然數都是唯一一組質數的乘積。

因此質數成為算術的基本單元。就像分子是由週期表元素的唯一組合構成,自然數也是唯一的質數乘積所構成。

數字安全

幾千年來數學家一直在思量、讚歎這些算術基本單元,然而這些數的威力遠遠超出了大家的推想。例如當你使用網際網路時,質數會保障你的財產安全及隱私。

質數的祕密武器就是,質數相乘很容易,但因數分解卻很難。要找出大數的質因數,需要強大的運算能力。迄今為止最難分解的數,稱為RSA-768,這個數有232位,是兩個116位的質數的乘積。分解RSA-768總共花了上百部電腦兩年的時間,只用一部電腦的話,可能需要將近兩千年。

RSA-768

=123018668453011775513049495838496272077285356959
5334792197322452151726400507263657518745202199786
4693899564749427740638459251925573263034537315482
68507917026122142913461670429214311602221240479274
737794080665351419597459856902143413

=

334780716989568987860441698482126908177047949837
1376856891243138898288379387800228761471165253174
3087737814467999489

×

367460436667995904282446337996279526322791581643
4308764267603228381573966651127923337341714339681
0270092798736308917

由於分解某些大數(特別是兩個大質數的乘積)很困難,所以可以把質數變成數學「掛鎖」。假設有一種利用大數N加密訊息的方法,需要知道N的質因數才能解密。而你要傳送某個須加密的訊息給我,譬如你的銀行帳戶,我就先找兩個大質數相乘,做為數字N;這相當容易。然後我把數字N公開傳送給你。N就像個已打開的掛鎖,無論誰都能把它鎖上,但需要鑰匙才打得開。接著你用數字N把訊息加密,上鎖,對我而言解密輕而易舉,因為我已經知道N的因數(也就是掛鎖的鑰匙),然而其他人就得投入大把時間分解N,才能破解密碼。這個概念正是RSA公鑰密碼系統的基礎,這種密碼系統已經受到廣泛採用,可保護個人的信用卡資料與密碼。

究極的複雜度

要破解RSA系統,有兩種顯而易見的方法。其中一種是打造出更快的電腦,不過加密人員只要採用更大的質數,很容易就能反制(除非你發明出量子電腦)。另外一種可能更具破壞力:找個又快又新的因數分解方法,速度快到可以把全世界的銀行資料都手到擒來。

這樣的方法是否存在,與數學上數一數二的待解難題有關。因數分解屬於NP類的數學問題。NP問題有容易檢驗的答案,意思是電腦可以在合理的時間內驗證答案是否正確(電腦科學家很清楚他們所說的「合理」是指什麼),因數分解屬於NP問題,因為只要找到質因數,就很容易檢查因數相乘的結果是否能得出原數。在NP類的問題中,有一些也能在合理的時間內解答;這些問題稱為P類。數學家仍不知道包括因數分解在內的其他NP問題是否也有快速的解法,或者P類是否就等於NP類。這個問題稱為「P=NP問題」,在1971年提出,至今還沒有人找到答案。

克雷數學研究所(Clay Mathematics Institute)體認到P=NP問題的難度,在2000年把這個問題列入了七大「千禧年大獎難題」,提供一百萬美元獎金給能夠證明它為真或為假的人。雖然不是人人同意,但大多數數學家似乎認為P不等於NP,這表示NP問題真的非常難,而且只要有源源不絕、愈來愈大的質數可以製鎖,數學掛鎖將會很安全。

質數謎題

幸虧有歐幾里得《幾何原本》中的另一個結果,確保我們有源源不絕的大質數可用,這個結果就是:質數有無窮多個。他證明的方法(見下方專欄)簡單確鑿,不過並沒有指出無窮多個質數是哪些。歐幾里得的結果正說明了數學上經常遭遇的狀況:就算你可以證明某物存在(譬如質數有無窮多個),你的證明也不見得能描述這些物件;這是一種非建構性(non-constructive)的證明。

質數無窮無盡

歐幾里得對於質數無窮多的證明,非常簡單優雅。先想像質數有限,並分別標上p1到pk。接著思考考E=(p1 × p2 × ... × pk)+1。歐幾里得的算術基本定理說明了E是唯一的質數乘積,但p1到pk中的任何質數都不能整除E(因為加上了1),所以E若不是質數,就一定有另一個質數p(k+1)能整除E,而這個質數沒有包含在原來的質數集合中。不管對哪個有限的質數集合來說,同樣的論證都成立,也就是這樣的集合永遠沒辦法建構出所有的自然數。因此,質數有無窮多個。就是這樣,你是個希臘數學家!

這也許沒什麼好意外的,假如你想一一寫出質數,證明有無窮多個,不就需要花無窮盡的時間嗎?但也不盡然。如果你要我寫出所有的偶數,雖然也是無窮多個,但我只要說:偶數是形式為2n的數,其中n是自然數,所以你能輕易算出第100個偶數是2×100=200。

質數似乎沒有類似的描述。看看頭幾個質數,實在看不出有什麼可描述這幾個數的規則。數學家很快就發現,兩個質數之間的間隔並不相等:2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,67, 71, 73, 79, 83, 89, 97  

沿著數線繼續往前看,質數看似愈來愈稀疏,但在某些區段又好像比其他區段密集。舉例來說,在一千萬之前的100個數中有9個質數,但在一千萬之後的100個數中只有2個質數。

幾百年來數學家一直努力尋找質數中的模式,也有了大快人心的結果。例如,質數偶爾會成對出現,兩質數只相差2,像是3與5、5與7、11與13、29與31。100以內的25個質數中,可以找到8組像這樣的質數對。已知最大的質數對是

3,756,801,695,685×2666,669–1與3,756,801,695,685×2666,669+1,在2011年發現,兩個數都是200,700位數。

數學家認為,這種質數對有無窮多組,稱為孿生質數猜想(Twin Prime Conjecture),至今超過一百五十年一直沒有人能證明。這也說明了數論中的常見現象:假設很容易,也容易陳述,但不表示容易證明。

1740年代有個特別著名的例子,出現在德國數學家克里斯欽.哥德巴赫(Christian Goldbach)和大數學家雷翁哈德.歐拉(Leonhard Euler,下一章還會提到他)的通信內容中。哥德巴赫推測,每個大於2的偶數,都可以表示成兩個質數的總和。這對前面幾個偶數而言是對的:4=2+2,6=3+3,8=5+3,10=5+5=7+3。電腦已經檢驗到4×1017為止,都是對的,但仍欠缺一般性的證明。

哥德巴赫猜想在數學圈外也很出名,經常出現在電影、小說和電視節目中,用來彰顯故事中聲稱破解它的人物天資聰穎。

相關書摘 ►學校騙了你,三角形的三個角加起來不會永遠是180度

書籍介紹

《數學好有事:為什麼磁磚不做正5邊形、A系列影印紙長寬比要√2、向日葵和海螺有什麼共同祕密……全面影響人類生活的數學符號與定理,以及背後的故事》,麥田出版
.透過以上連結購書,《關鍵評論網》由此所得將全數捐贈兒福聯盟

作者:瑪莉安.弗萊伯格、瑞秋.湯瑪斯
譯者:畢馨云

印度最偉大的數學家婆什迦羅為了安慰嫁不出去的女兒,用女兒的名字作為書名寫了一本數學書,正是這本書裡提到了重要的「0的運算」;畢達哥拉斯學派在西元前五世紀的義大利簡直就是個幫派,而「世上只有有理數」便是幫規;牛頓和萊布尼茲分別發明了微積分,此後為了誰先誰後而展開激烈爭論,一吵就是數十年;還有更多更多在特殊數字背後的歷史軼事,數學就有了更多讓人進一步深入探索的好理由。也唯有在真正探索之後,你才可能想像,數學的邏輯多麼嚴密,竟能完美詮釋大自然和宇宙現象。

在本書裡,兩位熱愛數學的作者以淺白而幽默的筆法,從每個人最熟悉的0與1開始說起,揭開一個有血有肉、饒富趣味的數學世界──那些與生活最相關的數字,以及背後的故事與歷史,盡皆躍然紙上。無論是無理數發現者的最終下場、龐大的質數如何成為網路加密的關鍵、大自然不同物體上的螺旋形狀暗藏的數學規律、看不見的第四維如何影響了狹義相對論,還有許多懸而未解的世紀數學之謎,都如同一把鑰匙,打開了連接過去與未來的那道門,讓你見識到數學無遠弗屆的影響力。

getImage_(2)
Photo Credit:麥田出版

責任編輯:朱家儀
核稿編輯:翁世航