改變世界的質數

作為一名程式開發者，應該寫過程式求過質數吧！質數是大於1，除了自身之外，無法被其他整數整除的自然數，將某數除以所有小於它的數，不能整除就是質數（可以整除的就是合數），是個結合數學、練習迴圈及條件判斷很好的練習對象，下一步就是試著減少迴圈的檢查次數，像是只檢查至數的開根號，只檢查6n+1與6n+5就可以了（也就是不檢查2、3的倍數）。

接下來就是認識Eratosthenes篩選了，這個篩選法就連國中資訊科技課本都會介紹，也是後續一些質數篩選演算，像是分段篩選、線性篩選的基礎。

起於數學家的求知欲

從公元前300年左右以來，就不斷有數學家因為對質數的求知欲，而找到了不少質數的特性，然而沒有公式可以產生質數，尋找質數還是只能透過以重複的過程，儘量地根據質數已知的一些數學特性，逐一檢查可能是質數的數字。

質數最重大的特性之一是，越大的數字範圍內，質數越來越稀疏，不過幸運的是，公元前300年左右，歐幾里德（Euclid）就證明了質數有無限多個，這表示有無限的質數可以使用。

目前已知最大的質數是在2018年發現的2⁸²⁵⁸⁹⁹³³-1，想知道這個數字的量級概念，可以來看看2017年發現的最大質數2⁷⁷²³²⁹¹⁷-1，它就已經具有2,249425位數，日本有出版社還出了本《2017年最大質數》（2017年最大の素数），全書只印刷這個數，就用了七百多頁的篇幅（還一度賣到缺貨）。

為什麼最大質數會使用2ᵖ-1形式撰寫呢？歐幾里德其實早就發現有些質數可以寫成這個形式，馬蘭梅森（Marin Mersenne）針對p為質數且p <= 257，而2ᵖ-1是個質數列出了梅森質數（Mersenne prime），為了紀念他，2ᵖ-1形式的數稱為梅森數（Mersenne number）。

梅森曾經猜測最大的梅森質數是2²⁵⁷-1，當然這猜想早就被打破，2018年發現的已知最大質數，是第51個梅森質數，遠超過2²⁵⁷-1，雖然質數被證明有無限多個，但梅森質數目前尚未證明是不是也有無限多個，為了尋找更大的梅森質數，有人成立一個志願者協同合作的專案，名為網際網路梅森質數大搜尋（Great Internet Mersenne Prime Search，GIMPS），我們可以從中下載軟體來協助搜尋梅森質數。

測試是否為質數

除了求質數之外，還有另一個面向是給定一個數，判定它是否為質數，如果該數是個很大的數，會是個艱難的任務，因為不存在快速、有效率的質因數分解方法，退而求其次地，存在一些非確定性的質數測試方式，想認識這些質數測試方式，可以從費馬小定理開始，若p為質數，與p互質的數a，則aᵖ⁻¹≡1(mod p)。

a≡b(mod N)代表同餘式，也就是以N為模數，a mod N 與 b mod N 得到的餘數恒等；費馬小定理說的就是，若p為質數，與p互質的數a，aᵖ⁻¹ mod p會餘1，相對地，若有個數n，與n互質的數a，aⁿ⁻¹ mod n不是餘1，n不是質數。

使用費馬小定理時，要注意的是，若p為質數，與p互質的數a，aᵖ⁻¹≡1(mod p)成立，但不表示有個數n，與n互質的數a，滿足aⁿ⁻¹≡1(mod n)，n就是質數，例如3215031751並不是質數，然而可以找到a為 2、3、5、7滿足aⁿ⁻¹≡1(mod n)。

Miller–Rabin質數測試基於費馬小定理、非確定性的演算加以改良，通過Miller–Rabin測試且是質數的機率，比費馬小定理高許多，雖然通過測試並不完全保證是質數，不過這類測試的另一個價值是，未通過測試的一定不是質數。

不少程式庫提供的測試函式實現原理，就是基於Miller–Rabin質數測試，例如Java的BigInteger提供的isProbablePrime方法，可以指定certainty，傳回數為質數的機率是 1-1/2ᶜᵉʳᵗᵃⁱⁿᵗʸ，另外還有probablePrime、nextProbablePrime方法，產生的數為合數的機率不會大於2⁻¹⁰⁰，相對地就是說，是質數的機率很高。

RSA密碼演算法

既然像Java這類語言，會在標準程式庫裡內建質數測試之類的API，這就表示現今質數不只是數學家求知欲下的研究對象，還更具有實質的應用，就數學而言，質數的研究推動了數論的發展，就科技發展而言，質數的尋找推動了電腦、分散式運算等的發展，而且質數也改變了整個世界的運作模式。

在《改變世界的九大演算法》第4章，談到了公鑰加密演算，沒有公鑰加密演算，你送出的密碼、信用卡資料、郵件等，就相當於在網路上裸奔了，公鑰加密演算裡最常見而耳熟能詳的是RSA演算，名稱來自三個發明者的姓氏Rivest、Shmir和Adleman首字母縮寫。

RSA演算的出發點簡單來說，找出大質數很難，判定很大的數是否為質數也很難，如果兩個很大的質數相乘得到一個數，在只知道這個數的前提下，想反過來分解這個數，找出是哪兩個質數相乘，是數學上的大難題。

基本上，RSA演算是非對稱加密，也就是它會產生一對金鑰，使用其中一把加密，只能用對應的另一把解密，因此加密用的金鑰可以公開透過網路傳遞，RSA演算的一開始，是隨機選兩個很大的質數P、Q，相乘後產生一個很大的數N，(P-1)*(Q-1)得到T，隨機選擇一個E小於T且E、T互質，這就得到了公開金鑰(N,E)，至於私鑰是推導出一個D，使得DE mod T為1，(N,D)就是私鑰。

也就是說，RSA演算過程與質數息息相關，當然演算法中兩個質數的選擇還必須滿足一些條件，例如，最基本的不能選2，畢竟相乘就會是偶數，一看就知道其中一個質因數是2，而越大的N越難找出P、Q，通常N會是1024或建議使用更長的2048位元，這樣的長度，理論上是有可能透過一些演算結合暴力破解，不過需要的運算資源與時間成本過高而不可行（768位元長度在2009年被成功分解，因此引發了1024位元的擔憂，才有了採用2048位元的建議）。

自RSA演算提出，世界意識到質數的實用性，後來被廣泛在商業交易上運用，帶動了網路的發展，說質數改變了整個世界的運作模式，一點也不為過。

不斷地探索質數

然而，目前並沒有理論能證明，破解RSA的難度等價於質因數分解，也就是說，目前RSA的安全性建立在實際經驗，也就是目前尚未找到有效的演算可以破解RSA，至於運算力更為的強大量子電腦呢？目前量子電腦尚未成熟，未來尚不可知，也許會演變成超大質數與量子電腦速度間的較勁？這是質數有無限多個的價值，也成了人們（像是GIMPS）持續追求更大質數的理由之一！

方才只是就開發者而言，聊聊質數在程式實務上，應該知道的一些特性與名詞，試著在網路搜尋「質數」，還可以找到有趣的性質，例如，就程式練習而言，也常看到如何尋找完全數，這件事跟尋找質數一樣地困難呢！

因為就目前已知的梅森質數而言，與完全數是一一對應，如果2ᵖ-1是梅森質數，2ᵖ⁻¹*(2ᵖ-1)就是個完全數，這稱為歐幾里得－歐拉定理，目前已知的梅森質數有51個，完全數也就有51個，而且全都是偶數。

看完這些，你對質數產生了更進一步的興趣嗎？考慮參與GIMPS的大搜尋？有獎金喔！因為第51個梅森質數的發現者，幸運地只花了四個月就找到，而獲得3千美元的獎勵。這感覺類似挖掘加密貨幣，還能名留歷史，或許你會是下個幸運兒！