作為一名程式開發者,應該寫過程式求過質數吧!質數是大於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千美元的獎勵。這感覺類似挖掘加密貨幣,還能名留歷史,或許你會是下個幸運兒!
專欄作者
熱門新聞
2024-10-13
2024-10-13
2024-10-11
2024-10-11
2024-10-12
2024-10-11
2024-10-11