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

由於分解某些大數（特別是兩個大質數的乘積）很困難，所以可以把質數變成數學「掛鎖」。假設有一種利用大數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×2^666,669–1與3,756,801,695,685×2^666,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開始說起，揭開一個有血有肉、饒富趣味的數學世界──那些與生活最相關的數字，以及背後的故事與歷史，盡皆躍然紙上。無論是無理數發現者的最終下場、龐大的質數如何成為網路加密的關鍵、大自然不同物體上的螺旋形狀暗藏的數學規律、看不見的第四維如何影響了狹義相對論，還有許多懸而未解的世紀數學之謎，都如同一把鑰匙，打開了連接過去與未來的那道門，讓你見識到數學無遠弗屆的影響力。

Photo Credit：麥田出版

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