[問卦] 梅森質數能幹嘛？

梅森質數，是型態為2^n-1的質數，n>1，以法國數學家馬蘭‧梅森的名字命名
舉例: 2^3-1=7，2^5-1=31，2^7-1=127都是梅森質數

梅森質數的必要條件是2^n-1中的n為質數，但非充份條件
例如，2^11-1=2047，11是質數，但2047=23*89，不是質數

幫大家科普一下，如何判定2^n-1為梅森質數？
一般用的是盧卡斯-萊默質數判定法
有一個序列為{S_0, S_1, S_2, S_3,...}
S_0=4
對於此序列中的第i項有如下遞迴關係式 ：
S_i=(S_(i-1))^2 - 2

S_0=4,S_1=14,S_2=194,S_3=37634,.....
若2^n-1為梅森質數，則此序列中的S_(n-2)可以整除 2^n-1
這個演算法，利用遞迴關係式，每算出S_i立刻除以2^n-1，保留餘數即可。
兩個d位數的數字相乘有d(log(d))的複雜度
要算出S_(n-2)除2^n-1的餘數，必需算出此序列的第n-2項
換言之，對於特定n，要求出2^n-1是否為梅森質數，運算複雜度為n*n*log(n)
譬如一個大約10^7的n，則必需有大約2.3*10^15的運算量
(不是10^7，是大約10^7，10^7不是質數，當然2^(10^7)-1不會是質數)

盧卡斯-萊默質數判定法開啟了梅森質數的大搜尋時代
n很大的時候就很吃CPU的運算能力
每隔幾年就宣稱找到了新的梅森質數

目前找到的最大梅森質數是2^136279841-1，數字爆大。在2024年找到的。

話說回來，梅森質數能幹嘛？找到這麼大的質數要幹嘛？能吃嗎？

有卦乎？

※ 八卦板務請到 GossipPicket 檢舉板實名詢問
※ a.張貼問卦請注意，充實文章內容、是否有專板，本板並非萬能問板。
※ b.一天只能張貼 "三則" 問卦，自刪及被刪也算三篇之內，
※ 超貼者將被水桶，請注意!
※ c.本看板嚴格禁止政治問卦，發文問卦前請先仔細閱讀相關板規。
※ d.未滿30繁體中文字水桶1個月
※ 未滿20繁體中文字水桶2個月
※ 未滿10繁體中文字水桶3個月，嚴重者以鬧板論，請注意！
※ (↑看完提醒請刪除ctrl + y)

--

已經掛了，可能要觀落陰才能問他

對齁，謝謝

質數的運用很多啊！例如要計算排容的時候，就是以質數為運算單位...