梅森质数，是型态为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)