發現目前為止最大的質數

■美國University of Central Missouri的團隊在2016年1月7日發表他們最新的研究成果:他們找到了目前為止最大的質數, \ 2^{74,207,281} -1 ,大約有兩千兩百多萬位。

569f728fae3a9撰文|陳勁豪

質數的定義相當簡單:只能夠被1跟自己整除的比1大的正整數。所以由小排到大,最前面的幾個質數分別是2, 3, 5, 7, 11, 13, 17, 19...質數有許多特別的性質,例如所有的質數中,只有2是偶數。質數的總數有無限多個,這個性質兩千多年前就已經被偉大的希臘數學家歐基里得巧妙的證明了。所以如果質數的個數有無限多個,我們有沒有辦法更有規律的來尋找質數呢?

其中一類的質數被稱為是Mersenne質數(中文有各種稱呼,例如梅森質數,梅西尼質數,梅仙尼質數等)。這類型的質數都可以寫成(2^n-1)的形式。公式相當簡單易懂,例如n = 2, \ 2^{2} -1=3 ,是質數。n = 3, \ 2^{3} -1=7 ,也是質數。但是顯然不是每個n都可以變成一個質數,例如n = 4, \ 2^{4} -1=15=3*5 ,就不是個質數。

儘管如此,這種Mersenne質數還是相當簡潔的一個尋找質數的猜測。只是當n越來越大,要檢測這個Mersenne數是不是質數就越來越困難。理論上,要檢查這個數是不是質數,只要把由2開始的所有整數一個一個拿來除除看,看看是不是都不能整除就好。但是當數字越來越大,這種簡單的計算也會變成相當麻煩的問題。所以現在檢測質數的工作基本上都是由電腦代勞。數學家把程式寫好之後,就讓電腦一直算,以得到結果。

這次University of Central Missouri由Curtis Cooper的團隊所找到的Mersenne質數叫做M74207281,是 \ 2^{74207281} -1 ,也就是把74207281個2連續乘起來後減1。如果把這個數乘出來,那麼一共會有22,338,618位。這是第49個Mersenne質數。

相對於前任的最大質數,同時也是另外一個Mersenne質數, \ 2^{57,885,161} -1 ,M74207281足足多了約五百萬位數。對高中數學老師來說,讓學生計算M74207281的位數是學到指數與對數時一個很好的練習(當然延伸出來的題目還有這個數的最高位數會是哪個數字...)

一個兩千兩百萬位的數字到底有多長?以一個中文字的大小相當於兩個數字字元來看,大約相當於一千一百萬個中文字。大家熟知的三國演義全文大約64萬字,所以大約會是17本三國演義的厚度。

這麼一個兩千多萬位的質數有什麼應用?說實在,至少現在幾乎想不出可能的用途。但是整體來看,質數在密碼學裡面具有相當重要的應用價值。要驗證一個超長位數的整數是不是質數相當困難,同樣的,要驗證一個超長位數的整數是由哪兩個質數的乘積所構成也是一樣困難的事情,至少在古典電腦裡面是如此。這種利用質數來為資料進行加密的演算法被稱為RSA加密演算法。

下一個質數會有多大呢?可以想見可能會比這個M74207281大上不少,但是同時電腦的計算能力也更加提昇,所以或許我們很快就可以聽到第50個Mersenne被找到的消息。

原始報導:Phys.org 2016/01/20: New largest prime number found
參考資料:Mersenne.org

--
作者:陳勁豪 科教中心特約寫手,從事科普文章寫作。2011年於美國紐約州立石溪大學(SUNY at Stony Brook)取得博士學位,研究主題為相對論性重離子碰撞(Relativistic Heavy Ion Collision)。長期擔任中文科學新聞網站「科景」(Sciscape.org)總編輯。

 

加入好友

6,400 人瀏覽過