(2018-01-11)質數是什麼?目前發現最大的質數是多少?美國田納西州一位電機工程師,找到了一個新的「質數」M77232917。

(圖:thenewslens.com)

(2018-01-11)新年剛過,說一點輕鬆的。去年12月26日,聖誕節第二天,美國田納西州一位電機工程師 Jonathan Pace,找到了一個新的「質數」(Prime Number),又稱作「素數」,就是一個整數只能被 1 與自己整除的數目,用任何別的數目都不能整除,都會留餘數。

除了 1 以外,2、3、5、7、11、13、17、37、149、293......都是質數,但 4 就不是、因為可以被 2 整除;6 也不是、可以被 2 與 3 整除。

 

質數從 2 開始,沒有盡頭,1-100 共有25個質數,100-200 有21個,200-300 有16個,數目越大間隔越大,越費事去尋找,也越花時間去測試。質數的出現沒有一定的規律,不能用算術法推演,越發引起數學迷、甚至數學家去追求,尋找更大的質數。這位工程師找到的質數有多大呢?如果你會算的話就這麼大:

上面這個數目的讀法是「2 的 77,232,917 次方減 1」,也就是 2 自乘77,232,917次,再減 1,成為到目前為止所知道的最大質數。這個數目一共長23,249,425位數,如果從電腦印出來要印9,000頁,如果以一公分兩個數目字排列,可以排到118公里。

這一個質數讓數學迷振奮,因為是屬於非常少的M質數,也就是法國數學家 Marin Merenne(1588-1648)發明的質數模型:2 的 n 次方 - 1,這類的質數到目前為止、連這一次,才發現50個。Merenne 不但是數學家,也是樂音學家,同時也是傳教士,在大學教授神學與哲學。


最大的質數 M77232917。

為此,熱心人士設立有一個機構網際網路梅森質數大搜索(Great Internet Mersenne Prime Search, GIMPS),提供資訊、軟體,幫助有興趣的人一起來尋找這類特別的質數,最近的16個M質數,都是藉助GIMPS發現的,每發現一個,就用這個質數的方次為名,這次就稱為 M77232917。上一個質數 M74207281 是2016年1月7日發現的,長22,338,618位數,比這一次少了將近一百萬位數。

這位發現第50個M質數的工程師,51歲,有14年掘發質數歷史,這次用了4台不同電腦、每台用不同軟體,連續運轉6天,經過無數次的測試,終於在聖誕節第二天發現了M77232917,雖是遲來的聖誕禮物,但GIMPS依例發給獎金3,000美元。

怎麼找質數?小數目可以用簡單的「刪除法」,比如要找從 3 到 100 有哪些奇數質數(偶數都不是質數),先把 3 到 100 的奇數全排列出來,第一個質數是 3,所以在排列中找出所有 3 的倍數,把它們劃掉,下一個質數是 5,再找出所有 5 的倍數、劃掉,然後是 7,同樣劃掉所有 7 的倍數,下一個質數數是 11,但 11 小於 100 的平方根,劃掉的動作就停止了,排列中所有沒被劃掉的數目就全是質數。


劃掉法筆記。(圖:ntnu.edu.tw)

小數目也可以用簡單的「試除法」來檢驗是否為質數,n 是否為質數,可以用全部小於 n 平方根的質數來除,如果都不能整除 n,就是質數。例如檢驗 211 是否為質數,就用 2、3、5、7、11、以及 13 來除,結果都不能整除,所以 211 是質數。(211 的平方根是 14.5)

大數目當然不能用這種手工做法,要用許多數學方法繁複運算,也必需用電腦協助。如果有興趣但嫌麻煩,加入GIMPS是可行的方法之一,只要你有一台好的電腦,下載軟體,做一些設定,加上你的耐性,就可以與所有的GIMPS成員共同尋找下一個M質數。

每天使用的電腦資源有限,但一旦你的電腦找到了下一個M質數,電腦就會鈴聲大作,叫個不停,成為最美妙的音樂。

發現這麼大的質數,除了數學與耐性的挑戰,並沒有實際用途,但小一點質數的應用,卻成為通訊安全的重要一環。通訊傳送要加密,接收要解密,如果把兩個質數相乘的結果做為傳送密碼,接收端就要用這兩個質數之一才能解開,如果這兩個質數不教人外人知道,通訊就安全,因為傳送密碼只有兩個質數因子,要破解並不容易,而且兩個質數越大,破解越不容易。

有興趣玩這場數學遊戲?或說是挑戰?有一個叫電子前哨(Electronic Frontier)的基金會,喊出15萬美元,發給第一個發現 1 億位質數的人。

*本文取材自2018年1月10日「那福忠西海岸數位隨筆(35)」:大數遊戲:發現最大的質數
對本文有任何看法,歡迎 E-Mail:frank.na@gmail.com 給作者,分享您對本文的看法。