大數遊戲：發現最大的質數

（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 給作者，分享您對本文的看法。